Quicksort

Quicksort is a very fast unstable sorting algorithm based on divide and conquer principle. It's asymptotic complexity is $O(n^{2})$ , but the expected complexity is only $O(n\\cdot \\log{n})$ and quicksort usually outperforms other algorithms in this complexity class such as heapsort or merge sort.

Quicksort was devised in 1960 by Sir Charles Antony Richard Hoare.

Description

Quicksort - pivot is the first element

Algorithm picks one random element of the input array (pivot). In next steps it reorganizes the array in such a way, that all elements with higher value than the pivot are located before the pivot and all elements with lower value than the pivot are after it. We can see that the pivot itself is located at the correct position (i.e. it is already sorted).

Algorithm now repeats the procedure described above on both (unsorted) halves of the array. When the algorithm reaches all the subproblems of size 1, which are solved trivially (one element itself is already sorted), the whole array is sorted in descending order.

Performance of the algorithm

The performance of quicksort is determined by the choice of the pivot. If we choose a good value, the array will be split into two halves of the exactly same size, thus we will need only $\\log_{2}{n}$ recursive calls of the algorithm, each moving at maximum elements of the array, so the final complexity of the sort will be $O(n \\cdot \\log_{2}{n})$ .

On the other hand, we may not be so lucky. If we choose in every recursive call the lowest or the highest element, the array won't get parted (only the pivot will be placed at correct place). Each step will consume checks whether the element should be moved (and possibly moves), and we will need recursive call – the final complexity of this instance is $O(n^{2})$ .

Behavior on small arrays

We can also see, that it is very probable that quicksort won't split the array ideally if there are only few elements to be sorted ( $n \\leq 10$ ), because there are only few good candidates. It is wise to use Shell sort or insertion sort, which behave better on small inputs, as a subroutine to order subarrays of smaller sizes.

Choice of the pivot

There are several strategies to choose a pivot. The first strategy is to choose element at fixed position (first, last, in the middle). This strategy is very inefficient on partially sorted arrays, because it is probable that it will choose improper value. To overcome this issue we may select median of the first, last and middle element.

Another strategy might be to choose random element. The drawback is that we must guarantee the randomness of our choice, because if we run into some patters of the random generator, the strategy degrades to a more complicated fixed position choice. But in the real world the pseudorandom generator would be sufficient for our purpose.

Visualization

Code

 procedure quicksort(List values)
     if values.size <= 1 then
         return values
 
     pivot = random element of values
 
     Divide values into the following lists
         list1 = { elements with value higher than the pivot }
         list2 = { pivot }
         list3 = { elements with value lower than the pivot }
     
     return quicksort(list1) + list2 + quicksort(list3)

     /**
      * Quicksort - pivot is the first element, descending order
      * @param array array to be sorted
      * @param left index of the first element which we can touch
      * @param right index of the first element which we can't touch
      */
     public static void quicksort(int[] array, int left, int right) {
         if (left < right) { 
             int boundary = left;
             for (int i = left + 1; i < right; i++) { 
                 if (array[i] > array[left]) { 
                     swap(array, i, ++boundary);
                 }
             }
             swap(array, left, boundary);
             quicksort(array, left, boundary);
             quicksort(array, boundary + 1, right);
         }     
     }
 
     /**
      * Swaps the elements of the array
      * @param array array
      * @param left index of the first element
      * @param right index of the second element
      */
     private static void swap(int[] array, int left, int right) {
         int tmp = array[right]; 
         array[right] = array[left];
         array[left] = tmp;
     }

 /**
  * Quicksort - pivot is the first element, descending order
  * @param array array to be sorted
  * @param left index of the first element which we can touch
  * @param right index of the first element which we can't touch
  */
 void quicksort(int array[], int left, int right) {
     if(left < right) { 
         int boundary = left;
         for (int i = left + 1; i < right; i++) { 
             if (array[i] > array[left]) { 
                 swap(array, i, ++boundary);
             }
         }
         swap(array, left, boundary);
         quicksort(array, left, boundary);
         quicksort(array, boundary + 1, right);
     }     
 }
 
 /**
  * Swaps the elements of the array
  * @param array array
  * @param left index of the first element
  * @param right index of the second element
  */
 void swap(int array[], int left, int right) {
     int tmp = array[right]; 
     array[right] = array[left];
     array[left] = tmp;         
 }

         /**
          * Quicksort - pivot is the first element, descending order
          * @param array array to be sorted
          * @param left index of the first element which we can touch
          * @param right index of the first element which we can't touch
          */
         public static void Quicksort(int[] array, int left, int right)
         {
             if (left < right)
             {
                 int boundary = left;
                 for (int i = left + 1; i < right; i++)
                 {
                     if (array[i] > array[left])
                     {
                         Swap(array, i, ++boundary);
                     }
                 }
                 Swap(array, left, boundary);
                 Quicksort(array, left, boundary);
                 Quicksort(array, boundary + 1, right);
             }
         }
 
         /**
          * Swaps the elements of the array
          * @param array array
          * @param left index of the first element
          * @param right index of the second element
          */
         private static void Swap(int[] array, int left, int right)
         {
             int tmp = array[right];
             array[right] = array[left];
             array[left] = tmp;
         }