Questions tagged [sorting]

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

Filter by
Sorted by
Tagged with
336
votes
11answers
310k views

Why is quicksort better than other sorting algorithms in practice?

In a standard algorithms course we are taught that quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ ...
88
votes
2answers
63k views

Quicksort Partitioning: Hoare vs. Lomuto

There are two quicksort partition methods mentioned in Cormen: (the argument A is the array, and [p, r] is the range, inclusive,...
55
votes
8answers
173k views

What is a the fastest sorting algorithm for an array of integers?

I have come across many sorting algorithms during my high school studies. However, I never know which is the fastest (for a random array of integers). So my questions are: Which is the fastest ...
53
votes
5answers
7k views

How is this sorting algorithm Θ(n³) and not Θ(n²), worst-case?

I just starting taking a course on Data Structures and Algorithms and my teaching assistant gave us the following pseudo-code for sorting an array of integers: ...
36
votes
4answers
7k views

Worst case $O(n \ln n)$ in place stable sort?

I am having trouble finding good resources that give a worst case $O(n \ln n)$ in place stable sorting algorithm. Does anyone know of any good resources? Just a reminder, in place means it uses the ...
34
votes
4answers
3k views

How to measure “sortedness”

I'm wondering if there is a standard way of measuring the "sortedness" of an array? Would an array which has the median number of possible inversions be considered maximally unsorted? By that I mean ...
31
votes
5answers
51k views

Adding elements to a sorted array

What would be the fastest way of doing this (from an algorithmic perspective, as well as a practical matter)? I was thinking something along the following lines. I could add to the end of an array ...
29
votes
3answers
60k views

Why is selection sort faster than bubble sort?

It is written on Wikipedia that "... selection sort almost always outperforms bubble sort and gnome sort." Can anybody please explain to me why is selection sort considered faster than bubble sort ...
28
votes
1answer
5k views

Sorting as a linear program

A surprising number of problems have fairly natural reductions to linear programming (LP). See Chapter 7 of [1] for examples such as network flows, bipartite matching, zero-sum games, shortest paths, ...
28
votes
7answers
23k views

Algorithm to distribute items “evenly”

I'm searching for an algorithm to distribute values from a list so that the resulting list is as "balanced" or "evenly distributed" as possible (in quotes because I'm not sure these are the best ways ...
23
votes
3answers
21k views

Why is Radix Sort $O(n)$?

In radix sort we first sort by least significant digit then we sort by second least significant digit and so on and end up with sorted list. Now if we have list of $n$ numbers we need $\log n$ bits ...
23
votes
4answers
19k views

Least number of comparisons needed to sort (order) 5 elements

Find the least number of comparisons needed to sort (order) five elements and devise an algorithm that sorts these elements using this number of comparisons. Solution: There are 5! = 120 possible ...
22
votes
4answers
3k views

Sorting algorithms which accept a random comparator

Generic sorting algorithms generally take a set of data to sort and a comparator function which can compare two individual elements. If the comparator is an order relation¹, then the output of the ...
22
votes
4answers
1k views

Is there no sorting algorithm with all specific desired properties?

On the Sorting Algorithms website, the following claim is made: The ideal sorting algorithm would have the following properties: Stable: Equal keys aren't reordered. Operates in place, ...
20
votes
3answers
9k views

Practical Applications of Radix Sort

Radix sort is theoretically very fast when you know that the keys are in a certain limited range, say $n$ values in the range $[0\dots n^k -1]$ for example. If $k<\lg n$ you just convert the ...
19
votes
2answers
6k views

Sort array of 5 integers with a max of 7 compares

How can I sort a list of 5 integers such that in the worst case it takes 7 compares? I don't care about how many other operations are performed. I don't know anything particular about the integers. ...
19
votes
2answers
627 views

Deterministic linear time algorithm to check if one array is a sorted version of the other

Consider the following problem: Input: two arrays $A$ and $B$ of length $n$, where $B$ is in sorted order. Query: do $A$ and $B$ contain the same items (with their multiplicity)? What is the ...
19
votes
3answers
5k views

What is the most efficient constant-space sorting algorithm?

I'm looking for a sorting algorithm for int arrays that doesn't allocate any byte other than the size of the array, and is limited to two instructions: SWAP: swap the next index with the current one; ...
18
votes
4answers
51k views

Why does Randomized Quicksort have O(n log n) worst-case runtime cost

Randomized Quick Sort is an extension of Quick Sort in which the pivot element is chosen randomly. What can be the worst case time complexity of this algorithm. According to me, it should be $O(n^2)$, ...
18
votes
2answers
7k views

What is the advantage of Randomized Quicksort?

In their book Randomized Algorithms, Motwani and Raghavan open the introduction with a description of their RandQS function -- Randomized quicksort -- where the pivot, used for partitioning the set ...
16
votes
4answers
10k views

Quicksort explained to kids

Last year, I was reading a fantastic paper on “Quantum Mechanics for Kindergarden”. It was not easy paper. Now, I wonder how to explain quicksort in the simplest words possible. How can I prove (or ...
16
votes
4answers
7k views

Why don't we use quick sort on a linked list?

Quick sort algorithm can be divided into following steps Identify pivot. Partition the linked list based on pivot. Divide the linked list recursively into 2 parts. Now, if I always choose last ...
15
votes
2answers
155 views

Efficiently inserting into list keeping number of inversions minimal

Assume two lists of comparable items: u and s. Let INV(u) be the number of inversions in u. I am looking for an efficient algorithm to insert the items of s into u with a minimal increase of INV(u). ...
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 ...
14
votes
4answers
4k views

Is transitivity required for a sorting algorithm

Is it possible to use a sorting algorithm with a non-transitive comparison, and if yes, why is transitivity listed as a requirement for sorting comparators? Background: A sorting algorithm generally ...
14
votes
1answer
12k views

Expected number of swaps in bubble sort

Given an array $A$ of $N$ integers, each element in the array can be increased by a fixed number $b$ with some probability $p[i]$, $0 \leq i < n$. I have to find the expected number of swaps that ...
14
votes
1answer
472 views

Interesting problem on sorting

Given a tube with numbered balls (random). The tube has holes to remove a ball. Consider the following steps for one operation: You can pick one or more balls from the holes and remember the order in ...
13
votes
2answers
2k views

Can the “divide” step in a merge sort be avoided?

So merge sort is a divide and conquer algorithm. While I was looking at the above diagram, I was thinking if it was possible to basically bypass all the divide steps. If you iterated over the ...
11
votes
4answers
23k views

Evaluating the average time complexity of a given bubblesort algorithm.

Considering this pseudo-code of a bubblesort: ...
10
votes
5answers
15k views

Word Frequency with Ordering in O(n) Complexity

During an interview for a Java developer position, I was asked the following: Write a function that takes two params: a String representing a text document and an integer providing the ...
10
votes
2answers
2k views

Why do we need so many sorting algorithms? [duplicate]

We have some best sorting methods like quick sort, merge sort etc., then why we need other sorting methods which perform poor?
10
votes
2answers
156 views

Name of this rearranging/sorting problem?

You are given an array of length $n$. Each element of the array belongs to one of $K$ classes. You are supposed to rearrange the array using minimum number of swap operations so that all elements from ...
9
votes
3answers
2k views

Does Quicksort always have quadratic runtime if you choose a maximum element as pivot?

If you have a quick-sort algorithm, and you always select the smallest (or largest) element as your pivot; am I right in assuming that if you provide an already sorted data set, you will always get ...
9
votes
3answers
2k views

How do I tell if a comparison network sorts?

I am presented with a comparison network. How can I determine if the comparison network is a sorting network? In the image below there is an example of a selection sort and insertion sort network. The ...
9
votes
2answers
400 views

Minimum number of swaps in sorting sequence

Given an array of N integer elements (not necessarily distinct), what is the minimum number of swaps (not necessarily adjacent) needed to sort the array? I've been struggling with this problem for a ...
9
votes
1answer
3k views

Why does introsort use heapsort rather than mergesort?

As part of a homework assignment covering implementation of introsort I'm asked why heapsort is used rather than mergesort (or other $O(n\log(n))$ algorithms for that matter). Introsort is a ...
9
votes
2answers
872 views

Is there a “sorting” algorithm which returns a random permutation when using a coin-flip comparator?

Inspired by this question in which the asker wants to know if the running time changes when the comparator used in a standard search algorithm is replaced by a fair coin-flip, and also Microsoft's ...
9
votes
1answer
21k views

Recurrence for recursive insertion sort

I tried this problem from CLRS (Page 39, 2.3-4) We can express insertion sort as a recursive procedure as follows. In order to sort A[1... n], we recursively ...
9
votes
2answers
460 views

Is integer sorting possible in O(n) in the transdichotomous model?

To my knowledge there doesn't exist a $O(n)$ worst-case algorithm that solves the following problem: Given a sequence of length $n$ consisting of finite integers, find the permutation where every ...
9
votes
1answer
310 views

What Measure of Disorder to use when Analysing Quicksort

I'm trying to understand why quicksort using Lomuto partition and a fixed pivot is performing erratically, but overall poorly, on randomly generated inputs. I'm thinking that even though the inputs ...
9
votes
1answer
2k views

Removing duplicates efficiently and with a low memory overhead

I want to filter efficiently a list of integers for duplicates in a way that only the resulting set needs to be stored. One way this can be seen: we have a range of integers $S = \{1, \dots{}, N\}$ ...
8
votes
2answers
412 views

Sort an array of $n$ elements when only $\log n$ are not in place

I'm trying to understand how can I sort an array of $n$ elements when only $\log n$ are not in place. I heard that sorting an array with at most $I$ inversions has complexity $O(n\log(I/n))$. Because ...
8
votes
1answer
6k views

Finding a worst case of heap sort

I'm working on problem H in the ACM ICPC 2004–2005 Northeastern European contest. The problem is basically to find the worst case that produces a maximal number of exchanges in the algorithm (sift ...
8
votes
2answers
4k views

Sorting a list of strings in lexicographic order of sorted strings

Let $A$ be a collection of strings over the alphabet $\{0,\ldots,m-1\}$ that in total contain $n$ symbols. Your task is to sort each of the strings internally, and then sort the resulting strings ...
8
votes
0answers
887 views

Complexity of Sorting Integers on a Multitape Turing Machine

How expensive is sorting integers on a Multitape Turing Machine? Well known sorting algorithms, like quicksort, tend to rely on jumping / indirect-access being cheap. But MTMs have no indirect access.....
8
votes
1answer
111k views

Complexities of basic operations of searching and sorting algorithms [closed]

Wiki has a good cheat sheet, but however it does not involve no. of comparisons or swaps. (though no. of swaps is usually decides its complexity). So I created the following. Is the following info is ...
7
votes
2answers
9k views

Why is Quicksort described as “in-place” if the sublists take up quite a bit of memory? Surely only something like bubble sort is in-place?

Quicksort is described as "in-place" but using an implementation such as: ...
7
votes
4answers
10k views

QuickSort Dijkstra 3-Way Partitioning: why the extra swapping?

Given the algorithm above (taken from the slides (p. 35) of the Coursera course “Algorithms Part I” by Robert Sedgewick and Kevin Wayne), look at the scenario where i is at "X", the following happens: ...
7
votes
1answer
698 views

Can partial sorting help with lookup cost in arrays?

Looking something up in an unsorted list is a task with time complexity $O(n)$. However, if the list is sorted, the time complexity is $O(\log(n))$. That means it is sometimes worthwhile to sort an ...
7
votes
2answers
3k views

Why is the time complexity of insertion sort not brought down even if we use binary sort for the comparisons?

There are two factors that decide the running time of the insertion sort algorithm : the number of comparisons, and the number of movements. In the case of number of comparisons, the sorted part (left ...

1
2 3 4 5
14