# Questions tagged [sorting]

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

694 questions
Filter by
Sorted by
Tagged with
3k views

### Insertion sort Proof by Induction

I am reading Algorithm design manual by Skiena. It gives proof of Insertion sort by Induction. I am giving the proof described in the below. Consider the correctness of insertion sort, which we ...
10k 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 ...
636 views

### Why does Shellsort work well on Sorted and Reverse ordered lists?

I've ran some tests and found that Shellsort runs much faster on ordered and reversed lists compared to random lists and almost ordered lists. ...
330 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 ...
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 ...
5k views

### Best case analysis for Shell sort

The exercises in a textbook I studied asks about the best case for Shell sort. I have scribbled a derivation for the same along the margins almost two years ago. Basically I don't know if this was my ...
194 views

### Sorting Problem

I have come across the following problem. You have $N$ registers, numbered $1,2,\dots, N$, each of which can hold an integer value. You are given the initial values of the registers, which have the ...
65k 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,...
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 ...
7k 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. ...
732 views

### Lower bound for sorting n arrays of size k each

Given $n$ arrays of size $k$ each, we want to show that at least $\Omega(nk \log k)$ comparisons are needed to sort all arrays (indepentent of each other). My proof is a simple modification of the ...
2k views

### A procedure for Topological sort, proof for its correctness

Definition: A preserved invariant of a state machine is a predicate, $P$, on states, such that whenever $P(q)$ is true of a state, $q$, and $q \rightarrow r$ for some state, $r$, then $P(r)$ holds. ...
910 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 ...
6k views

### Why does bubble sort do $\Theta(n^2)$ comparisons on an $n$ element list?

I have a quick question on the bubble sort algorithm. Why does it perform $\Theta(n^2)$ comparisons on an $n$ element list? I looked at the Wikipedia page and it does not seem to tell me. I know that ...
233 views

### When can one use a $O(n)$ time sorting algorithm?

Some sorting algorithms like counting sort/insertion sort can work in $O(n)$ time while other algorithms such as quicksort require $O(n \log n)$ time. As I understand it, it's not always possible to ...
5k views

### Worst case analysis of bucket sort using insertion sort for the buckets

Suppose I am using the Bucket-Sort algorithm, and on each bucket/list I sort with insertion sort (replace nextSort with insertion sort in the wikipedia pseudocode). In the worst case, this would ...
3k views

### Counting Inversions Using Merge Sort

In Corman, Introduction To Algorithms, 3rd edition, question 2-4 it asks to count the number of inversions in a list of numbers in $\theta( n \lg n )$ time. He uses a modified Merge Sort to ...
584 views

### Can someone help me understand cache conscience radix sort? (excerpt from journal article attached)

Article: CC-Radix: a Cache Conscious Sorting Based on Radix sort (IEEE 2003) I'm trying to figure out what the author means by this section: Explanation of CC-Radix For clarity reasons, we ...
474 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 ...
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 ...
2k views

### If I have a large random array of 0s and 1s that I want to sort what kind of an algorithm and data structures should I consider?

What are the types of things that need to be considered if I need to sort a large random array of 0s and 1s? You can assume large array is in the order of million or billions. I understand there ...
1k views

I'm trying to understand a proof regarding radix-sort but to no avail. I'll first write down a brief summary of the proof and then assign some questions which I hope will be clarified enough. ...
3k views

### how does the parallel radix sort work?

I'm currently learning computer science, and there is a slide of notes brief described the parallel radix sort under data parallelism. ...
4k views

### Counting sort on non-integers - why not possible?

What is it about the structure of counting sort that only makes it work on integers? Surely strings can be counted? ...
794 views

### Generalizing the Comparison Sorting Lower Bound Proof

Let's start with the comparison sorting lower bound proof, which I'll summarize as follows: For $n$ distinct numbers, there are $n!$ possible orderings. There is only one correct sorted sequence of ...
2k views

13k 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 ...
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 ...
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 ...
7k 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 ...
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 ...
8k views

### Quicksort vs. insertion sort on linked list: performance

I have written a program to sort Linked Lists and I noticed that my insertion sort works much better than my quicksort algorithm. Does anyone have any idea why this is? Insertion sort has a ...
54k 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 ...
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)$ ...