[ACE] Quick Sort

QuickSort

---

In Merge Sort, the ‘divide’ is simple and the ‘merge’ is relatively complicated.
Can we make the ‘merge’ simple? Yes, and to make ‘merge’ becomes concatenate.

Concept

Quick-sort is a randomized sorting algorithm based on the divide-and-conquer paradigm:

• Divide: pick a random element x (called pivot) and partition S into L(elements less than x), E(elements equal to x) and G(elements greater than x)
• Recur: sort L and G
• Conquer: join L, E and G

implement using Java

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int [] a = {5, 2, 4, 7, 1, 3, 2, 6};
        quick_sort_v1(a, 0, a.length-1);
        System.out.println(Arrays.toString(a));
        quick_sort_v2(a, 0, a.length-1);
        System.out.println(Arrays.toString(a));
    }

    /*
     * This version of quick_sort is recursively copy the value of i to j then copy j to i.
     */
    public static void quick_sort_v1(int a[], int l, int r){
        int i, j, x;
        if(l < r){
            i = l;
            j = r;
            x = a[i];
            while(i < j){
                while(i < j && a[j] > x){
                    j--;
                }
                if(i < j){
                    a[i++] = a[j]; 
                }
                while(i < j && a[i] < x){
                    i++;
                }
                if(i < j){
                    a[j--] = a[i];
                }
            }
            a[i] = x;
            quick_sort_v1(a, l, i-1);
            quick_sort_v1(a, i+1, r);
        }
    }

    /*
     * This version of quick sort is to swap i and j;
     */
    public static void quick_sort_v2(int[] arr, int low, int high) {
        if (arr == null || arr.length == 0)
            return;

        if (low >= high)
            return;

        // pick the pivot
        int middle = low + (high - low) / 2;
        int pivot = arr[middle];//random number

        // Partition: make left < pivot and right > pivot
        int i = low, j = high;
        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }

            while (arr[j] > pivot) {
                j--;
            }

            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }

        // recursively sort two sub parts
        if (low < j)
            quick_sort_v2(arr, low, j);

        if (high > i)
            quick_sort_v2(arr, i, high);
    }
}

I use two different ways to implement but the concept is similar.

analysis

As what we did in merge sort, we create a quick-sort tree. However, due to the different situation in quick sort, the tree will not always be a perfect binary tree but a normal binary tree.

As for running time, we need to discuss in different cases:
Worst-case running time:

The worst case for quick-sort occurs when the pivot is the unique minimum or maximum element
One of L and G has size n-1 and the other has size 0
The runing time is proportional to the sum n+ (n-1) + …+ 2+ 1
Thus, the worst-case running time of quick-sort is O(n^2)

Best-case running time:

The best case for quick sort occurs when the pivot is the median element
The L and G parts are equal- the sequence is split in halves like in merge sort
Thus, the best-case running time of quick-sort is O(n log n)

Averge-case running time

The average case for quick-sort: half of the times, the pivot is roughly in the middle.
Thus, the averge-case running time is O(n logn) again

The stability? Again, it is depends on how you implement it.

Comparison sorting

A sorting algorithm is a comparison sorting algorithm if it uses comparisons between elements in the sequence to determine in which order to place them

• Examples of comparison sorts: bubble sort, selection sort, insertion sort, heap sort, merge sort, quicksort.
• Example of not a comparison sort: bucket sort (Ch. 11.4). Runs in O(n), relies on knowing the range of values in the sequence (e.g. integers between 1 and 1000).
  What is bucket sort?
  It works by distributing the elements of an array into a number of buckets. Then output as the buckets sequence which has O(n)

Also, there is a lower bounder for comparison sort runtime.
Think about the comparison sorting to a binary decision tree.

And for n numbers, there will be n! possibilities.
If a binary tree has n! leaves, than the minimal number of levels( assuming the tree is perfect) is (log2 n!)+1
It has the same growth rate as nlog2 n

Thus, comparison-based sorting cannot do better than O(n log n)