Sorting Algorithms

Table of Contents

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(n²)

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)

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email:	(Your email is not shared with anybody)

Comment:

Facebook comments:

Site Owner: Sachin Goyal