Questions tagged [sorting]

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

Filter by
Sorted by
Tagged with
2
votes
0answers
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 ...
20
votes
3answers
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 ...
2
votes
0answers
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. ...
9
votes
1answer
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 ...
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 ...
3
votes
2answers
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 ...
3
votes
1answer
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 ...
89
votes
2answers
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,...
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 ...
19
votes
2answers
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. ...
5
votes
1answer
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 ...
8
votes
1answer
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. ...
9
votes
2answers
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 ...
6
votes
2answers
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
1answer
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 ...
14
votes
1answer
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 ...
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 ...
2
votes
4answers
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 ...
1
vote
1answer
1k views

Radix sort exercise

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. ...
5
votes
2answers
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. ...
6
votes
1answer
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? ...
6
votes
1answer
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 ...
5
votes
1answer
2k views

Minimum space needed to sort a stream of integers

This question has gotten a lot of attention on SO: Sorting 1 million 8-digit numbers in 1MB of RAM The problem is to sort a stream of 1 million 8-digit numbers (integers in the range $[0,\: 99\...
23
votes
3answers
22k 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 ...
2
votes
1answer
2k views

Complexity of optimized bubblesort [closed]

What is the runtime complexity of the following implementation of Bubblesort (for integers)? ...
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, ...
5
votes
1answer
92 views

Upper-bounding the number of comparisons for Sorting to $\Theta(n)$ using a physically big number like Number of Particles in the Universe

I recently read an article Scott Aaronson - Big Numbers . That has made me think about the effective upper-bound for sorting. According to the article, some of the big numbers like the number of ...
6
votes
2answers
6k views

Why does heapsort run in $\Theta(n \log n)$ instead of $\Theta(n^2 \log n)$ time?

I am reading section 6.4 on Heapsort algorithm in CLRS, page 160. ...
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\}$ ...
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 ...
0
votes
1answer
1k views

How to calculate the depth of sorting networks?

I have trouble understanding how to calculate the depth of a sorting network on $n$ inputs. For example, in case of selection sort, we have: $\qquad \displaystyle D(n)=D(n-1)+2\\\qquad D(2)=1$ ...
5
votes
1answer
358 views

Is it possible to always construct a hamiltonian path on a tournament graph by sorting?

Is it possible to always construct a hamiltonian path on a tournament graph $G=(V,E)$ by sorting (using any sorting algorithm) with the following total order: $\qquad \displaystyle a \leq b \iff (a,b)...
14
votes
1answer
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 ...
37
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 ...
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 ...
8
votes
1answer
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 ...
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 ...
6
votes
3answers
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 ...
32
votes
5answers
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 ...
11
votes
4answers
24k views

Evaluating the average time complexity of a given bubblesort algorithm.

Considering this pseudo-code of a bubblesort: ...
344
votes
11answers
315k 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)$ ...

1
10 11 12 13
14