Computer science is incomplete without sorting algorithms.
Here we give a summary of the most common algorithms in vogue today.
Properties of sorting:
In-Place Sort:
Means no extra space is needed. At most, O(1) or O(logN) space is needed.
Stable Sort:
Stable sorts guarantee that input order is preserved for elements with equal keys.
Parallelizable:
If the algorithm can be run on multiple machines, it is parallelizable.
Commonly used sorting algorithms
Bubble Sort:
Make passes through the array till it is sorted.
In each pass, swap two contiguous integers which are not in order.
Worst case - list was in fully wrong order.
So need to make 'n' passes and n comparisons in each pass which makes it O(n2)
Insertion Sort:
In each pass through the array, take an element and insert it into elements sorted till now.
Shell Sort:
Elements placed at regular intervals are logically grouped to form buckets.
Thus bucket 1 will have 1st, kth, 2*kth element.
Bucket 2 will have 2nd, (k+1)th and so on.
Each bucket is sorted using insertion sort.
Interval k is reduced and the above steps are repeated.
In the last step, the interval size k equals 1 and sorting at this step sorts the input completely.
Theory behind reducing group intervals is that
at each step the sorting algorithm deals with more and
more sorted data due to which number of comparisons are lesser.
However, it is possible to input data such that worst case for this algorithm is also O(n^2)
Merge Sort:
Divide
input in two parts, sort the two parts and merge.
Do it recursively.
Recursion will form a stack LogN levels deep and at every level there will be a merge operation in 2^level elements.
This gives a worst case performance of O(n Log n)
Quick Sort:
Choose a pivot and put it in its proper position such that elements to its
right are bigger and elements to left are smaller.
void partition(int[] array, int left, int right, int pivotIndex)
{
int pivotValue = array[pivotIndex];
swap (array, pivotIndex, right); // Move pivot to end
int storeIndex = left;
// One pass needed from left to right to put the pivot in its proper place
for (int i=left; i<right-1; i++)
{
if (array[i] ≤ pivotValue) // if smaller than pivot
{
swap (array, i, storeIndex); // move to the left
storeIndex++;
}
}
swap (array, storeIndex, right); // Move pivot to its final place
return storeIndex;
}
The above algorithm can also be written in a slightly different way as follows:
int partition(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i <= j)
{
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j)
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
return i;
}
// And finally the recursive quicksort function that
// uses partition() to divide and recurse
void quickSort(int arr[], int left, int right)
{
int index = partition(arr, left, right);
if (left < index - 1)
quickSort(arr, left, index - 1);
if (index > right)
quickSort(arr, index, right);
}
Like merge sort, quick sort can also be easily parallelized.
So if p processors are used to parallelize this, order becomes
(n/p)log(n/p) instead of n.log(n)
Intro Sort (1997):
If the list is full sorted in inverse order, quick sort will always
choose the worst possible pivot and give an O(n^2) order.
This was fixed by Intro Sort which switches quick sort to
heap sort after a particular limit is reached in recursion thus
bringing worst case scenario of quick sort to n.log(n)
Flash Sort (1998):
Very good sorting algo with order O(n) if the range of data is known
beforehand.
If range is known, then in a first-pass, all elements can be distributed
by the following formula:
Pos(i)
= 1 + (N-1)* ((Ele(i) - Ele(min))/(Ele(max) - Ele(min))
After this first pass distribution, elements are almost sorted and can be
sorted by any algo.
This can give an O(n) sort.
Counting Sort:
Sorting by putting numbers into an array when it is known that the range of
numbers is not too large.
Runs in O(n) always but needs auxiliary space of the order of O(Ele(max) - Ele(min)
Got a thought to share or found a bug in the code? We'd love to hear from you: