Questions tagged [sorting]

the algorithmic problem of ordering a set of elements with respect to some ordering relation.

Filter by
Sorted by
Tagged with
0
votes
0answers
5 views

How to define the stability (or convergence) of a ordering of a list of node

I have a problem which requires ordering nodes in a graph based on some given statistics. However, the given statistics of each node may be very hard to compute. Thus, I will use some sampling ...
1
vote
1answer
18 views

Weird implementation of quicksort

I met a wired question from the algorithm test of my school. For the first time I thought it is a normal quick-sort problem and feel confident to solve it but as I read the algorithm carefully, it is ...
-3
votes
0answers
24 views

Number of swaps and comparisons in sorting algorithms [on hold]

i was reading the comparison algorithms(bubble,insertion and selection). i followed this linklink1,but if someone asks what is the number of comparison and swap in these algorithms, what should i say ?...
0
votes
0answers
14 views

Recurrence Formula for Bitonic Sorter Runtime

A Bitonic sorter takes a bitonic sequence as an input and the output is a sorted list. I want to analyse Bitonic Sorter by knowing its depth/runtime. Can anyone give an idea on its recurreence formula?...
0
votes
2answers
19 views

How to do a reverse topological sort using depth first search?

I'm doing a replacement for the venerable make utility that will support, among other things, automatic cleaning. The utility figures out automatically what files ...
1
vote
1answer
15 views

Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations)

I need some help understanding how to calculate the lower bound on the time complexity of merging $m$ sorted arrays of length $n$. The bound should be $nm \lg(m)$. I need to prove this using a ...
0
votes
1answer
37 views

Selection Sort vs Insertion Sort For Reversed Array

I had a question in a test, which asked me the following question: Selection sort runs faster than Insertion sort for an array in reverse order. Now, according to my knowledge, both of them have a ...
1
vote
1answer
48 views

Recursive Bubble Sort Complexity

I have this code for a recursive bubble sort: ...
-1
votes
2answers
30 views

Any array takes at least log(n!) compairs to be sorted [duplicate]

I have to prove that there is no comparison based algorithem that can sort a randomly given array in less than log(n!) steps. Lets say the array has 5 elements, it is impossible to sort it (using ...
1
vote
1answer
52 views

Is there a linear-time algorithm to determine if an array has duplicate entries that uses only constant extra space?

Determining whether or not an array has duplicate entries has two straightforward solutions: Build a hashset of entries, then search for elements in this hashset. This takes $\mathcal O(n)$ time and $...
1
vote
1answer
28 views

Algorithm Analysis of Insertion Sort

Why is the recurrence formula for insertion sort is T(n-1) + n? I understand the T(n-1) part but the why does the cost for ...
0
votes
1answer
44 views

Question about how can i determine if counting sort is the right option over other sorting algorithms

So, an exam's exercise asks me to find an alghoritm that can determine if counting sort is the best solution, otherwise use another optimal sorting algorithm. Now i find that solutions for that ...
2
votes
1answer
56 views

Sorting an array of strings by length in linear complexity

I am trying to find an algorithm to sort an array of strings by length in O(n) time complexity, and O(1) space complexity. The max length of the strings is known. Because of that, I tried using ...
2
votes
1answer
16 views

Analysis of straight insertion

I'm currently reading through N. Wirths': Algorithms + Data Structures = Programs. I'm not sure, but I think there might be an error in the analysis of the provided straight insertion sort. Screenshot ...
0
votes
0answers
34 views

How to find the “odd one out” in a list of numbers

I have an array of numbers [x1, x2, x3, etc] that is size is over 20 elements and I'm trying to put together an algorithm to sort the elements based on the "oddness" they have relative to the rest of ...
1
vote
2answers
188 views

What is the name of this sorting algorithm?

I have typeset in a Wikipedia draft this sorting algorithm. It is a comparison sort, yet can handle only numeric arrays. Basically, it marches through the input array and for each new array ...
0
votes
0answers
49 views

Number of comparisons in array where each element appears n/k times [duplicate]

Given an array of $n$ elements with $k$ distinct elements, each appearing $n/k$ times, how can I show that the number of comparisons to the sort the array in the worst case is in $\Omega(n \log k)$?
1
vote
0answers
25 views

time complexity of k-bubble sort [duplicate]

I'm a student. today I answered a question wrong, the question is this: Spouse we have a k-bubble sort, which means except sorting 2 elements each time, it has a magical function that can sort $k$ ...
2
votes
1answer
28 views

Does Google's PageRank count as a sorting algorithm?

Is it correct to assume that PageRank is a sorting algorithm or does it fall in any other category?
1
vote
0answers
16 views

Randomized Quick Selects' time complexity dependence on k - the index to be selected

I was analyzing Randomized Quick Selects' time complexity, as a function of n - the size of the input, and k - the index of the element that needs to be selected. The time complexity dependence on n ...
1
vote
0answers
25 views

Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks

I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact ...
4
votes
2answers
67 views

sorting with noisy but persistent answers

Given a set of elements $A$ and a probability of noise $p<0.5$. For any two elements $x,y\in A$ we can ask the oracle $O$ to know where $x$ stands w.r.t $y$ (0 means $x$ is smaller than $y$ and 1 ...
3
votes
1answer
38 views

Lower Bound for Time Complexity of Pairing Problem

Given an array X and array Y both of length n, the pairing algorithm will return the elements of the arrays matched so that the smallest element in X will be matched with the smallest element of Y, ...
3
votes
2answers
47 views

Is finding Kth largest element using selection algorithm taking O(n) only if K is fixed?

Wikipedia here https://en.m.wikipedia.org/wiki/Selection_algorithm shows an algorithm using sort of quicksort.. in order to find Kth largest or smallest element taking O(n) time only on average. The ...
3
votes
2answers
52 views

Minimum depth of a leaf in a tree that corresponds to a comparison-based sorting algorithm

The lower bound of comparisons in a comparison-based sorting algorithm is $\log_2 n!=Θ(n\log n)$. Yet there can be less comparisons needed in an algorithm. If you take a sorted array, it will take $n-...
0
votes
0answers
26 views

Least distance sorting [duplicate]

There are 10 Egyptian stone statues standing in a row in an art gallery hall. A new curator wants to move them so that the statues are ordered by their height. How should this be done to minimize the ...
2
votes
2answers
123 views

Minimum number of comparisons in comparison-based sorting algorithms [duplicate]

I've seen that every comparison-based sorting algorithm must perform at least $\log_{2}(n!)=\Omega(nlog(n))$ comparisons on some input (n being the size of the input). Why is the minimum number of ...
0
votes
0answers
33 views

Proof that this sorting algorithm sorts the input

I'm given this "sorting" algorithm and now I'm supposed to prove, that if given an array of integers of length $n$, sort(A,0,n-1) will sort it. ...
0
votes
2answers
28 views

Quicksort Algorithm with Pivot element as Median

I have read that when pivot element is choosen as Median, then QS Algorithm gets nearly balanced splits and have time complexity of O(nlogn), but my doubt is what if all the elements of the input are ...
1
vote
2answers
42 views

Quicksort where element comparison outcome is random. Probability of element being in a certain position

So we have this block of pseudocode: Monsters = [M1,M2,M3,M4,M5,M6,M7,M8]; qsort(Monsters,rand_compare); qsort() sorts the ...
1
vote
1answer
50 views

AVL Tree - Print ascending using in-order

Trying to understand how to write proof of correctness. Searched over the internet on how to write proof of correctness but can't find a good solution for it. The following sorting algorithm is ...
0
votes
1answer
39 views

Quick sort worst case complexity improvement [closed]

Can the worst case time complexity of quick sort be changed from $O(n^2)$ to $O(n\log n)$ by modifying it?
14
votes
1answer
1k views

Can the sorting of a list be verified without comparing neighbors?

A $n$-item list can be verified as sorted by comparing every item to its neighbor. In my application, I will not be able to compare every item with its neighbor: instead, the comparisons will ...
1
vote
1answer
37 views

Self-balancing binary search tree optimized for insertion

I've written a "quiz" that prompts the user for comparisons between two items of subjective value, and once the position of all of the items is determined, displays an ordered list from most valuable ...
0
votes
1answer
225 views

Can this “double pop” Heapsort variation speed up sorting on average?

For classic Heapsort (in this example using a maxheap), only the root node is extracted (popped) at each iteration and the last element in the heap is swapped into its place and then the tree is "re-...
0
votes
2answers
80 views

Is this a new sorting algorithm?

I just came up with a simple sorting algorithm that is faster than ShellSort when the range of values is smaller than the number of elements. Is this new? And if so, what should I do with it? https:/...
0
votes
0answers
61 views

Given n strings, how to output their order after k phases of the radix sort (huge constraints)?

Disclaimer This is not from an ongoing contest, this is from my course of ITMO on edx.org, which is a paid code so I cannot give you a direct link to the course. Problem You are given $\...
1
vote
1answer
25 views

Kth smallest element in an arra [duplicate]

What would be an efficient method to find the kth smallest element in an array with worst case time complexity being $ O(n) $?
0
votes
1answer
93 views

radix-sort with different bases

So i understand how to use radix-sort in base 10 and utilize mod 10 to go through the numbers. But not sure about 2,8 or 16. Does it follow the same idea? and i read somewhere that i need to pass ...
2
votes
2answers
189 views

Is there a sorting algorithm of order $n + k \log{k}$?

I'm given an integer vector which is said to contain many duplicate values (total of k distinct integers), for example ...
0
votes
0answers
30 views

Sorting using AI / neural net

I have a search operation taking place on a server that essentially queries images using OpenCV against other images from a database. Since each image query ...
2
votes
1answer
55 views

How to reduce number of move operations in an array?

Say I have an array of numbers, e.g. [0, 1, 2, 3, 4, 5] and I want to end up with an array, e.g. [2, 1, 4, 0, 5, 3]. At my ...
0
votes
0answers
30 views

Does this algorithm exhibit the same behavior as Selection Sort?

This is a homework question. I have been asked to identify what sort this code below implements. ...
1
vote
0answers
38 views

A binning (sorting) algorithm

Rules: A conveyor belt is giving you little boxes. They are labeled for your convenience: Box $1$, Box $2$,... For your inconvenience, though, you can't see the number (from $1...n$) hidden in it. You ...
3
votes
1answer
71 views

Why is finding minimum number of comparisons to sort $n$ elements so difficult?

In The Art of Computer Programming 2nd Ed, Vol 3, Section 5.3.1 then discuss a function $S(n)$ which is define as: $S(n)$ : The minimum number of comparisons that suffice to sort $n$ elements. ...
1
vote
1answer
27 views

Recurrence Relation Mergesort

I was reading Algorithms 4th Edition by Sedgewick et al. and I found this statement when discussing about the analysis of mergesort: The number of compares is at most n and no less than $\lfloor n/...
0
votes
1answer
45 views

How to find examples of best cases for sorting algorithms?

I am asked to give a table of 8 elements that are to be sorted by the following algorithms and to produce their best cases. 1) Selection sort 2) Bubble sort 3) Insertion sort 4) Fusion sort If I give ...
2
votes
1answer
29 views

Consensus/ranked ordering algorithm

Say I have a set of numbers, for example {1, 2, 3, 4, 5}. Is there an algorithm that allows these numbers to be put into a consensus ordering based on a ranked vote?...
2
votes
1answer
65 views

Expected number of iterations for bozo sort opt algorithm

I'm trying to figure out the upper bound for the number of iterations of the bozo sort opt algorithm, described in this paper on section 3.2: http://www.hermann-gruber.com/pdf/fun07-final.html I know ...
0
votes
1answer
43 views

Whats the best way to sort a dataset into groups by using a facial recognition algorithm that compares only 2 images at a time?

I have a facial recognition algorithm that compares two images A and B and returns the likelihood that they match. I also have 50,000 images, and I would like to sort these images into groups. Here'...