Sorting Algorithms

1. Bin Sort
2. Bubble Sort
3. Comb Sort 11
4. Counting Sort
5. Heap Sort
6. Insertion Sort
7. Merge Sort
8. N log log N Sort
9. Odd-Even Transposition Sort
10. Quick Sort
11. Radix Sort
12. Radix Exchange Sort
13. Selection Sort
14. Shaker Sort
15. Shear Sort
16. Shell Sort
17. Compare Times...

Introduction

This is a collection of sorting algorithms, including explanations (as best as I can), and an implementation
of them all in C++. There are your everyday sorts in here, such as the Bubble Sort, QuickSort, and Insertion
Sort, but there are also some lesser known ones such as the Bin Sort, Counting Sort, and Shear Sort.
I also included a 'best-case' and 'worst-case' scenario for each; best-case just means that this is the type
of data where the sort will be used to its full potential. Enjoy!
*    = O(N²) sort.
**   = O(N log N) sort.
***  = O(N log log N) (or better) sort.
**** = O(N) sort.
Also note that this page is currently under construction!!

Bin Sort **

The bin sort is one of the best sorts. Not only is it simple, but it is one of the fastest sorts.
Its complexity is O(5 * N). The 5 comes from the fact that for 5-digit numbers, each number is
used 5 times. It is very similiar to the radix sort, and in fact, the radix sort
is simply a modification of this sort. The basic idea behind a bin sort is this: start with a list
of numbers. Going through the list, put each number in a different "bin" according to its least
significant digit (0 - 9). Go through the bins and collect them back (in the order they are placed in the bins)
and put them back in the list. Do this for each digit of the numbers. Note that if a number does not have
that certain digit (i.e. 21 has no hundreds digit), then it is put in the zero ("0") bin. Once the final
pass is made through the bins and the numbers are recollected, they will be in order.
Best case: Large, random numbers
Worst case: Small numbers
Download code for the bin sort

Bubble Sort *

The bubble sort is one of the simplest of sorts, and, as a result, is one of the simplest to code.
For a size N list, the bubble sort makes N passes and compares N - 1 elements
on each of the passes. Thus, its complexity is O(N²). For each pass of the sort, the
sort compares each two adjacent elements and if the higher value comes before the lower, it swaps them.
The bubble sort is a compact, yet inefficient sort. It is one of the slowest, and has little to show
for itself, besides the incredible simplicity in coding. It is so simple that it is very easy to
recall from memory and requires only but a minute to complete it.
Best case: In-order; slightly out of order
Worst case: Reverse order
Download code for the bubble sort

Comb Sort 11 **

To me, the Comb Sort 11 is one of the neatest sorting algorithms. It is basically a fancy, modified
bubble sort, but its speed is many, many times faster than the bubble sort. You could almost call
it a "smart" bubble sort. For an N sized list, it begins comparing a gap of N numbers, and divides
the gap by 1.3 each time, this seeming to be the number that gives the best results in the long run.
It, too, compares two elements next to each other and swaps if necessary, but it changes the "gap"
that it checks each time. What gives it the "11" in its name, is that if a gap of 9 or 10 is found
it changes the gap to 11, as this seems to be more efficient. Its complexity is approximately
O(N log N).
Best case: In order; slightly out of order
Worst case: Reverse order
Download code for the comb sort

Counting Sort ****

The Counting sort is not so much a "sort," as much as it is a histogram. In fact, that's a better explanation.
For a size N list, with the largest number in the list being M, an auxiliary array of
size M is created, and each subscript is set to zero. The list is then traversed, and each
subscript in the auxiliary array is incremented for each value in the original array. Then the original
array is filled with the amount of each number from the original array. Its complexity is O(N).
Best case: Compact data with many repeated values
Worst case: Spread-out data with zero or one of each possible value from 0 to M.
Download code for the Counting sort

Heap Sort **

The heap sort begins by, as it name implies, creating a heap of the numbers in the array. It then
"removes" the largest element from the heap and places it at the end of the array. Each time the
"reheap" function is called, it restores the array back into a heap, minus the already sorted items
at the end of the array. By guaranteeing that the largest element is in the array position 1 every
time "reheap" is called, it is easy to swap the array position 1 (largest) with wherever the next spot
is at the end of the array. Its complexity is approximately O(N log N).
Best case: None.
Worst case: None. The heap sort performs equally well under nearly all conditions.
Download code for the heap sort

Insertion Sort *

The insertion sort is one of the best sorting algorithms if the data is nearly in-order. Its complexity
for these is very low, but for typical random data, the insertion sort is a standard O(N²).
However, it is one of the fastest O(N²) sorts. The insertion sort works like this: Going through
the list of numbers, each number is inserted into the "sorted" part of the list, which starts out as the first number.
As each number is inserted into its proper place, that part of the list is considered "sorted." It is said that
this sort is how humans inherently sort, by inserting objects in lexicographical order. Also, this sort works
exceptionally well in a linked list, because to "insert" in an array, each value must be shifted over, but in a
linked list, only a few pointers are reassigned, and this increases efficiency.
Best case: In-order; one of the BEST for slightly out-of-order data.
Worst case: Reverse order.
Download code for the insertion sort

Compare Times

*Note: All times are on an 800 MHz Pentium III with 320 MB of RAM.

10,000 Randomly chosen integers between 1 and 32,767

Sorting algorithm	Time	Complexity
Bin Sort	0 sec.	O(5 * N)
Bubble Sort	1.281 sec.	O(N * N)
CombSort11	0.01 sec.	O(N log N)
Counting Sort	0 sec.	O(N)
Double Storage Merge Sort	0.01 sec.	O(N log N)
HeapSort	0.01 sec.	O(N log N)
Insertion Sort	0.4 sec.	O(N * N)
Merge Sort	0.22 sec.	O(N log N)
N log log N	0.02 sec.	O(N log log N)
Odd-Even Sort	1.331 sec.	O(N * N)
QuickSort	0 sec.	O(N log N)
Radix Sort	0 sec.	O(5 * N)
Radix Exchange Sort	0.41 sec.	O(5 * N)
Selection Sort	0.51 sec.	O(N * N)
Shaker Sort	1.191 sec.	O(N * N)
Shear Sort	0.13 sec.	O(N log N)
Shell Sort	0.03 sec.	O(N log N)

100,000 Randomly chosen integers between 1 and 32,767

Sorting algorithm	Time
Bin Sort	0.08 sec.
BubbleSort	174.29 sec. (2:54)
CombSort11	0.16 sec.
Counting Sort	0.01 sec.
Double Storage Merge Sort	0.09 sec.
HeapSort	0.37 sec.
Insertion Sort	47.768 sec.
Merge Sort	23.163 sec.
N log log N	0.19 sec.
Odd-Even Sort	335.692 sec. (5:35)
QuickSort	0.04 sec.
Radix Sort	0.03 sec.
Radix Exchange Sort	53.196 sec.
Selection Sort	98.641 sec. (1:38)
Shaker Sort	129.716 sec. (2:09)
Shear Sort	15.232 sec.
Shell Sort	0.54 sec.

1,000,000 Randomly chosen integers between 1 and 32,767

Sorting algorithm	Time
Bin Sort	0.91 sec.
CombSort11	2.113 sec.
Counting Sort	0.07 sec.
Double Storage Merge Sort	1.25 sec.
HeapSort	1.372 sec.
N log log N	1.10 sec.
QuickSort	0.591 sec.
Radix Sort	0.311 sec.
Shell Sort	9.173 sec.

10,000,000 Randomly chosen integers between 1 and 32,767

Sorting algorithm	Time
Bin Sort	8.993 sec.
CombSort11	25.767 sec.
Counting Sort	0.661 sec.
Double Storage Merge Sort	15.25 sec.
HeapSort	22.522 sec.
N log log N	11.41 sec.
QuickSort	7.721 sec.
Radix Sort	3.104 sec.