Learning Algorithm(1): QuickSort

Posted on

Introduction

Quick Sort is a classical divide-and-conquer algorithm. The basic idea is: in each phase, we choose one from an array and divide this array into two subarray. All elements in first one are smaller than this number and the other’s are all bigger than this number then do the same for both parts again. Finally, we merge all and get a sorted array. Quick sort’s average time-complexity is O(nlogn) and space complexity is only O(1). Although its worst-case is up to O(n^2), it’s often the best practical choice for its remarkable average efficiency.

Core Concepts

  1. Quick Sort Algorithm Description;
  2. Complexity Analysis

Description of Quick Sort

Two steps should be took for sorting an array A[p…r]

(1) Divide

Partition the array into two subarrays A[p…q-1] and A[q+1…r] such that each element in A[p…q-1] is less than or equal to A[q], which is, less than or equal to each element in A[p…q-1].

(2) Conquer

Sort two subarrays by recursively call quick sort;

Implementation

So we can implement Quick sort by Java code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Arrays {

    public static void sort(int[] array) {
        sort(array, 0, array.length - 1);
    }

    public static void sort(int[] array, int p, int r) {
        if (p < r) {
            int q = partition(array, p, r);
            sort(array, p, q - 1);
            sort(array, q + 1, r);
        }
    }

}

The key to quick sort is Partition procedure. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int partition(int[] array, int p, int r) {
    int x = array[r];
    int i = p - 1;
    for (int j = p;j <= r;j++) {
        if (array[j] <= x) {
            i++;
            swap(array, i, j);
        }
    }
    swap(array, i + 1, r);
    return i + 1;
}

public static void swap (int[] array, int a, int b) {
    int temp = array[b];
    array[b] = array[a];array[a] = temp;
}

PARTITION always select a number x = array[r] as pivot, then our job is to split the array into two subarray by traversing this array only once, one’s each element is smaller than pivot and another’s element is bigger than pivot.

After PARTITION, we have two subarrays then we do the same progress recursively util the length of subarrays are zero. Because we do all operations on the same array, conquer has been done automatically so that we get the sorted array.

Complexity Analysis

Worst-case Analysis

The worst case happens when we partition the array, one is with n - 1 elements and the other with 0 elements. So the recurrence for the running time is: T(n) = T(n-1) + O(n) = O(n^2)

Best-Case Analysis

In most even possible split, PARTITION produces two subproblems, each of size is no more than n/2. In this case, the recurrence of running time is: T(n) = 2T(n/2) + O(n)