Algorithm Note 03: Quick Sort

// Quick sort
void exch(int arr[], int i, int j)
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}


int partition(int arr[], int left, int right)
{
	// partition
    int i = left;
    int j = right + 1;
    int pivot = arr[left];

    while (true) 
    {
    	// scan from left to right
    	while (arr[++i] < pivot)
    		if (i == right) break;
    	// scan from right to left
    	while (arr[--j] > pivot)
    		if (j == left) break;
    	if (i > = j) break;
    	exch(arr, i, j);
    }

    exch(arr, left, j);
    return j;
}	
    		
void quickSort(int arr[], int left, int right)
{
	if (left >= right) return;
	int j = partition(arr, left, right); // partition
	quickSort(arr, left, j - 1); // sort left part a[left,...,j -1]
	quickSort(arr, j + 1, right); // sort right part a[j+1,...,right]
}

void sort(int arr[], const int len)
{
	shuffle(arr); // random shuffle the input
	quickSort(arr, 0, len - 1);
}