Sorting Algorithms

Quick overview of simple sorting algorithms. We cannot simple ignore them as the form the base of many algorithms.

Using binary comparisons we have n! sub sets and hence we need n lg n to reach the leaf node of the binary tree. Integer sorting does not uses binary comparisons and can achieve O(n) for sorting n numbers.
Avoiding overflow when looking middle element: int mid = first + (last - first) / 2;

Bubble Sort - After every pass the biggest* element is sifted to end. Lot of swaps since each element is compared with next element.

Insertion Sort - Similar to human arranging cards. Elements are inserted into the sorted array [0 to k-1] and swap happens from inserted element to A[k]. We can use binary search to find position of kth element in [0 to k-1] sorted array. However actual insertion may cause k-1 swaps.

Selection Sort - Minimizes number of swaps. For every iteration k, find the smallest element in A [k to k-1] and swap at the end of iteration.

Quick Sort - Uses divide-and-conquer strategy, below are the recursion steps

Choose a pivot value. Pick a random element k or middle element as pivot value.
Partition. Rearrange elements in such a way, that all elements which are lesser than the pivot go to the left part of the array and vice-versa.
Sort both parts. Apply quicksort recursively to the left and the right parts.

Counting or Bucket Sort

We can implement a simple counting sort using array[k] when sorting 1…k numbers. We need an ARRAY[k] to hold frequency of each number occurrence and then merge at end.

When to use Counting sort ? When k is smaller than n ( k<<n )

e.g. Suppose you want to sort 10000 people by birthday; n=10000, k=366, so time = O(n) and memory O(k).

Radix sort - How to efficiently sort a big list dates in 20’s

What to do when k is large ?

Think about the decimal representation of a number. For any number we need log(number) digits.

x = a + 10 b + 100 c + 1000 d + … where a, b, c etc all in range 0..9.

radix sort(L):

{

bucket sort by a; bucket sort by b; bucket sort by c

...
}

We do k passes where k is the number of digit. Hence we would need 10 passes in 32 bit number.
Start from LSD so in last pass we handle the MSB and it is when all numbers settle in the final place. For MSB first we would need recursion similar to merge sort. By contrast to bucket sort, radix sorting never splits up the list; it just applies bucket sorting several times to the same list.

Sorting floating point numbers

Floating point represents numbers roughly in the form x = a * 2^b. If all numbers had same value of b, we could just bucket sort by a. Different b's complicate the picture but basically b is more important than a so sort by a first (radix sort) then one more bucket sort by b.

Stability - Any comparison based sorting algorithm can be made stable by modifying the comparisons to break ties according to the original positions of the objects, but few are automatically stable.

Bucket sort? Yes. We add items to the lists Y[i] in order, and concatenating them preserves that order.
Heap sort? No. The act of placing objects into a heap (and heapifying them) destroys any initial ordering they might have.
Merge sort? Maybe. It depends on how we divide lists into two, and on how we merge them. For instance if we divide by choosing every other element to go into each list, it is unlikely to be stable. If we divide by splitting a list at its midpoint, and break ties when merging in favor of the first list, then the algorithm can be stable.
Quick sort? Again, maybe. It depends on how you do the partition step.

https://en.wikipedia.org/wiki/Sorting_algorithm

http://www.sorting-algorithms.com/

http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html