Quicksort

Quicksort is a fast sorting algorithm, which is used not only for educational purposes, but widely applied in practice. On the average, it has O(n log n) complexity, making quicksort suitable for sorting big data volumes. The idea of the algorithm is quite simple and once you realize it, you can write quicksort as fast as bubble sort.

Algorithm

The divide-and-conquer strategy is used in quicksort. Below the recursion step is described:

1. Choose a pivot value. We take the value of the middle element as pivot value, but it can be any value, which is in range of sorted values, even if it doesn't present in the array.
2. 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 all elements greater than the pivot, go to the right part of the array. Values equal to the pivot can stay in any part of the array. Notice, that array may be divided in non-equal parts.
3. Sort both parts. Apply quicksort algorithm recursively to the left and the right parts.

Partition algorithm in detail

There are two indices i and j and at the very beginning of the partition algorithm i points to the first element in the array andj points to the last one. Then algorithm moves i forward, until an element with value greater or equal to the pivot is found. Index j is moved backward, until an element with value lesser or equal to the pivot is found. If i ≤ j then they are swapped and i steps to the next position (i + 1), j steps to the previous one (j - 1). Algorithm stops, when i becomes greater than j.

After partition, all values before i-th element are less or equal than the pivot and all values after j-th element are greater or equal to the pivot.

Example. Sort {1, 12, 5, 26, 7, 14, 3, 7, 2} using quicksort.

Notice, that we show here only the first recursion step, in order not to make example too long. But, in fact, {1, 2, 5, 7, 3} and {14, 7, 26, 12} are sorted then recursively.

Why does it work?

On the partition step algorithm divides the array into two parts and every element a from the left part is less or equal than every element b from the right part. Also a and b satisfy a ≤ pivot ≤ b inequality. After completion of the recursion calls both of the parts become sorted and, taking into account arguments stated above, the whole array is sorted.

Complexity analysis

On the average quicksort has O(n log n) complexity, but strong proof of this fact is not trivial and not presented here. Still, you can find the proof in [1]. In worst case, quicksort runs O(n²) time, but on the most "practical" data it works just fine and outperforms other O(n log n) sorting algorithms.

Code snippets

Java

int partition(int arr[], int left, int right)

{

     int i = left;

     int j = right;

     int temp;

    int  pivot = arr[(left+right)>>1];

     while(i<=j){

        while(arr[i]>=pivot){

            i++;

        }

        while(arr[j]<=pivot){

            j--;

       }

       if(i<=j){

           temp = arr[i];

           arr[i] = arr[j];

           arr[j] = temp;

           i++;

           j--;

       }

    }

    return i

}

 

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); 

      }

}

python

def quickSort(L,left,right) {

      i = left

      j = right

      if right-left <=1:

            return L

      pivot = L[(left + right) >>1];

      /* partition */

      while (i <= j) {

            while (L[i] < pivot)

                  i++;

            while (L[j] > pivot)

                  j--;

            if (i <= j) {

                  L[i],L[j] = L[j],L[i]

                  i++;

                  j--;

            }

      };

      /* recursion */

      if (left < j)

            quickSort(L, left, j);

      if (i < right)

            quickSort(L, i, right);

}

Insertion Sort

Insertion sort belongs to the O(n²) sorting algorithms. Unlike many sorting algorithms with quadratic complexity, it is actually applied in practice for sorting small arrays of data. For instance, it is used to improve quicksort routine. Some sources notice, that people use same algorithm ordering items, for example, hand of cards.

Algorithm

Insertion sort algorithm somewhat resembles selection sort. Array is imaginary divided into two parts - sorted one andunsorted one. At the beginning, sorted part contains first element of the array and unsorted one contains the rest. At every step, algorithm takes first element in the unsorted part and inserts it to the right place of the sorted one. Whenunsorted part becomes empty, algorithm stops. Sketchy, insertion sort algorithm step looks like this:

becomes

The idea of the sketch was originaly posted here.

Let us see an example of insertion sort routine to make the idea of algorithm clearer.

Example. Sort {7, -5, 2, 16, 4} using insertion sort.

The ideas of insertion

The main operation of the algorithm is insertion. The task is to insert a value into the sorted part of the array. Let us see the variants of how we can do it.

"Sifting down" using swaps

The simplest way to insert next element into the sorted part is to sift it down, until it occupies correct position. Initially the element stays right after the sorted part. At each step algorithm compares the element with one before it and, if they stay in reversed order, swap them. Let us see an illustration.

This approach writes sifted element to temporary position many times. Next implementation eliminates those unnecessary writes.

Shifting instead of swapping

We can modify previous algorithm, so it will write sifted element only to the final correct position. Let us see an illustration.

It is the most commonly used modification of the insertion sort.

Using binary search

It is reasonable to use binary search algorithm to find a proper place for insertion. This variant of the insertion sort is calledbinary insertion sort. After position for insertion is found, algorithm shifts the part of the array and inserts the element. This version has lower number of comparisons, but overall average complexity remains O(n²). From a practical point of view this improvement is not very important, because insertion sort is used on quite small data sets.

Complexity analysis

Insertion sort's overall complexity is O(n²) on average, regardless of the method of insertion. On the almost sorted arrays insertion sort shows better performance, up to O(n) in case of applying insertion sort to a sorted array. Number of writes is O(n²) on average, but number of comparisons may vary depending on the insertion algorithm. It is O(n²) when shifting or swapping methods are used and O(n log n) for binary insertion sort.

From the point of view of practical application, an average complexity of the insertion sort is not so important. As it was mentioned above, insertion sort is applied to quite small data sets (from 8 to 12 elements). Therefore, first of all, a "practical performance" should be considered. In practice insertion sort outperforms most of the quadratic sorting algorithms, like selection sort or bubble sort.

Insertion sort properties

• adaptive (performance adapts to the initial order of elements);
• stable (insertion sort retains relative order of the same elements);
• in-place (requires constant amount of additional space);
• online (new elements can be added during the sort).

Code snippets

We show the idea of insertion with shifts in Java implementation and the idea of insertion using python code snippet.

Java implementation

void insertionSort(int[] arr) {

      int i,j,newValue;

      for(i=1;i<arr.length;i++){

           newValue = arr[i];

           j=i;

           while(j>0&&arr[j-1]>newValue){

               arr[j] = arr[j-1];

               j--;

           }

           arr[j] = newValue;

}

Python implementation

void insertionSort(L) {

      for i in range(l,len(L)):

            j = i

            newValue = L[i]

            while j > 0 and  L[j - 1] >L[j]:

                 L[j] = L[j - 1]

                  j = j-1

            }

            L[j] = newValue

      }

}