Notes of Reading Introduction to Algorithm —— Quicksort

Just as Mergesort, Quicksort also applies Divide and Conquer. But in some cases, the time to call Quicksort can be $\Theta (n^2)$Θ(n2), just like Insertionsort, which is different from Mergesort. In most cases, however, the time to call Quicksort is $\Theta (n\lg n)$Θ(nlgn), and the constant factor is smaller. Moreover, it also has the advantage of sorting in place.

Partition

First, we should find a pivot. In the code below, we choose the last element to be the pivot. However, in the next part, we will randomize the partition, which will choose the pivot at random.

After choosing the pivot, we will divide the array into three parts. In part 1, all the elements are larger than or equal to the pivot. In part 2, all the elements are smaller than the pivot. Part 3 is just the pivot.

int Partition(int *A, int p, int r)
{
    int i = p - 1, q = p;
    for (; q < r; q++)
    {
    	if (A[q] <= A[r])
    	{
	        i++;
        	int temp;
        	temp = A[q]; A[q] = A[i]; A[i] = temp;
    	}
    }
    i++;
    int temp;
    temp = A[r]; A[r] = A[i]; A[i] = temp;
    return i;
}

Obviously, the time to call Partition is $\Theta(n)$Θ(n), $n = r-p+1$n=r−p+1.

Divide & Conquer

The array has been divide into three parts, then we “conquer” part 1 and part 2. As the elements are just in place, we needn’t combine.

void Quicksort(int *A, int p, int r)
{
    if (p < r)
    {
        int q = Partition(A, p, r);
        Quicksort(A, p, q-1);
        Quicksort(A, q+1, r);
    }
}

Performance of Quicksort

The time to call the Quicksort depends on the input array.

The Worst Case

Just think about this case, the numbers in the array are sorted, like 0, 1, 2, 3, … .

In this case, $T(n)=T(n-1) + \Theta (n)$T(n)=T(n−1)+Θ(n). We can work out that the time complexity is $\Theta(n^2)$Θ(n2). In this case, the time complexity of Insertionsort is only $\Theta(n)$Θ(n).

The Best Case

The best case turns up when part 1 and part 2 have the same number of elements for every partition. At this time, $T(n)<2T(\frac{n}{2})+\Theta(n)$T(n)<2T(2n​)+Θ(n). Therefore, the time complexity is $\Theta(n\lg n)$Θ(nlgn).

Analysis

In most cases, the time to call Quicksort is much closer to the best case other than the worst case. The two pictures below can help us to understand this.

Picture 1 shows that the unbalanced cases also have the time complexity of $O(n\lg n)$O(nlgn). Picture 2 shows that the worst case plus the best case has the same time complexity with the best case.

Randomized Version of Quicksort

In this version, we will choose the pivot at random. Then we have the reason to expect the split of the input to be balanced on average.

int RandomizedPartition(int *A, int p, int r)
{
    int i = rand() % (r - p + 1) + p;
    int temp;
    temp = A[i]; A[i] = A[r]; A[r] = temp;
    return Partition(A, p, r);
}

void RandomizedQuicksort(int *A, int p, int r)
{
    if (p < r)
    {
        int q = RandomizedPartition(A, p, r);
        RandomizedQuicksort(A, p, q-1);
        RandomizedQuicksort(A, q+1, r);
    }
}

Analysis of Quicksort

Obviously, the upper bound of Quicksort is $O(n)$O(n).

In the function of Quicksort, we need to call RandomizedQuicksort for at most n times. And in every RandomizedQuicksort we will call RandomizedPartition , and then the Partition . Therefore, the time we cost is related to how much time we will cost in the function Partition.

Moreover, the time of calling Partition is related to the times we compare a pair of numbers, because the loop in the function includes the comparison.

We define $X_{ij}=I$Xij​=I {$z_i$zi​ is compared to $z_j$zj​} , and all the times we compare equals $X=\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}X_{ij}$X=i=1∑n−1​j=i+1∑n​Xij​. $E(X)=E(\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}X_{ij})=\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}E(X_{ij})=\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}\Pr$E(X)=E(i=1∑n−1​j=i+1∑n​Xij​)=i=1∑n−1​j=i+1∑n​E(Xij​)=i=1∑n−1​j=i+1∑n​Pr{$z_i$zi​ is compared to $z_j$zj​} .

$\Pr$Pr{$z_i$zi​ is compared to $z_j$zj​}$=$=$\Pr$Pr{$z_i$zi​ or $z_j$zj​ is the first pivot to be chosen from the elements indexed from $i$i to $j$j}$=\frac{2}{j-i+1}$=j−i+12​.Then we can work out that $E(X)<O(n\lg n)$E(X)<O(nlgn).

In conclusion, the average time we call RandomizedQuicksort has an upper bound —— $O(n\lg n)$O(nlgn).

All my codes along with Heapsort are shown below:

#include <iostream>
#include <cstdlib>

#define MaxLength 50
#define INFINITY 65535
#define MaxNum 2000

using namespace std;

struct MaxHeap
{
    int numbers[MaxLength + 1];
    int capacity = MaxLength + 1;
    int size;
};

int PARENT(int i)
{
    return i/2;
}
int LEFT(int i)
{
    return 2*i;
}
int RIGHT(int i)
{
    return 2*i+1;
}

void MaxHeapify(MaxHeap *A, int i)
{
    int l, r, largest;
    l = LEFT(i);
    r = RIGHT(i);
    if (l <= A->size && A->numbers[l] > A->numbers[i]) {
        largest = l;
    }
    else largest = i;
    if (r <= A->size && A->numbers[r] > A->numbers[largest]) {
        largest = r;
    }
    if (largest != i) {
        int temp;
        temp = A->numbers[i]; A->numbers[i] = A->numbers[largest]; A->numbers[largest] = temp;
        MaxHeapify(A, largest);
    }
}

void BuildMaxHeap(MaxHeap *A)
{
    A->numbers[0] = INFINITY;
    int i = A->size / 2;
    for (; i > 0; i--) {
        MaxHeapify(A, i);
    }
}

void Heapsort(MaxHeap *A)
{
    BuildMaxHeap(A);
    for (int i = A->size; i > 1; i--) {
        int temp;
        temp = A->numbers[i];
        A->numbers[i] = A->numbers[1];
        A->numbers[1] = temp;
        A->size--;
        MaxHeapify(A, 1);
    }
}

int Partition(int *A, int p, int r)
{
    int i = p - 1, q = p;
    for (; q < r; q++)
    {
    if (A[q] <= A[r])
    {
        i++;
        int temp;
        temp = A[q]; A[q] = A[i]; A[i] = temp;
    }
    }
    i++;
    int temp;
    temp = A[r]; A[r] = A[i]; A[i] = temp;
    return i;
}

int RandomizedPartition(int *A, int p, int r)
{
    int i = rand() % (r - p + 1) + p;
    int temp;
    temp = A[i]; A[i] = A[r]; A[r] = temp;
    return Partition(A, p, r);
}

void RandomizedQuicksort(int *A, int p, int r)
{
    if (p < r)
    {
        int q = RandomizedPartition(A, p, r);
        RandomizedQuicksort(A, p, q-1);
        RandomizedQuicksort(A, q+1, r);
    }
}

int main()
{
    MaxHeap *A = new MaxHeap;
    A->size = 0;
    A->capacity = MaxLength + 1;
    int *B;
    B = new int(MaxLength + 1);
    B[0] = INFINITY;
    for (int i = 1; i < A->capacity; i++) {
        A->numbers[i] = B[i] = rand() % MaxNum;
        A->size++;
    }

    for (int i = 1; i < MaxLength + 1; i++) {
        cout << A->numbers[i] << '\t';
    }
    cout << endl;

    Heapsort(A);
    RandomizedQuicksort(B, 1, MaxLength+1);

    for (int i = 1; i < A->capacity; i++) {
        cout << A->numbers[i] << '\t';
    }
    cout << endl;

    for (int i = 1; i < MaxLength + 1; i++) {
        cout << B[i] << '\t';
    }
    cout << endl;
}

Reference: Introduction to Algorithm