quicksort, quickselect, partition

quicksort.cp

// various ways of partition function
// see: http://www.liacs.nl/~graaf/STUDENTENSEMINARIUM/quicksorthistorical.pdf
// read the chapter 3 in book: Beautiful Code. It shows how to simplify quicksort to count average comparison numbers. (9/2/2014)

#include <iostream>
using namespace std;


/*
Given an array nums of integers and an int k, partition the array (i.e move the elements in "nums") such that:

All elements < k are moved to the left
All elements >= k are moved to the right
Return the partitioning index, i.e the first index i nums[i] >= k.
*/
// 下面这段代码的好处是，k 不是数组的某个元素，就避免了选轴值
// 也非常好理解：数组里如果某值比k小，直接跳到下一个。
// 如果大，就跟数组尾交换，尾缩短。
// 我认为它可以变成后面所有partition函数的一个子函数。
    int partitionArray(vector<int> &nums, int k) {
        // write your code here
        int N = nums.size();
        int left = 0, right = N-1;
        while (left <= right) {
            if (nums[left] < k) {
                left++;
            }
            else {
                swap(nums[left], nums[right]);
                right--;
            }
        }
        return left++;
    }


// ======================================================
// use one runner. easy to understand.
// edit 8/20/2015 其实感觉还是有点不太容易理解和掌握的。可以先参考上面的代码
// 段，再来试图理解这个。本质上，有异曲同工之妙

int partition(int A[], int l, int h) {
	int p = h;
	int boundry = l;
	for(int i=l; i<h; i++) {
		if(A[i] < A[p])
			swap(A[i], A[boundry++]);	
	}
	swap(A[p], A[boundry]);
	return boundry;
}

// use two runners, had to understand fully
int partition2(int A[], int l, int h) {
	int p = l;
	int i = l, j = h;
	while(i < j) {
		while(i < h && A[i] <= A[p]) i++;
		while(j >= l && A[j] > A[p]) j--;
		if(i < j) swap(A[i++], A[j--]);
	}
	swap(A[j], A[p]);
	return j;
}

// use two runners, version 2. easy to understand
int partition3(int A[], int l, int h) {
	int p = l;
	int i = l, j = h+1;
	while(true) {
		while(A[++i] < A[p]) if(i == h) break;
		while(A[p] < A[--j]) if(j == l) break;
		if(i >= j) break;
		swap(A[i], A[j]);
	}
	swap(A[j], A[p]);
	return j;
}

// quicksort with three-way partition.
// used for arrays with many equal keys
void quicksort3way(int A[], int l, int h) {
	if(l >= h) return;
	int lt = l, i = l+1, gt = h;
	int v = A[l];
	while(i <= gt) {
		if(A[i] < v) swap(A[lt++], A[i++]);
		else if(A[i] > v) swap(A[i], A[gt--]);
		else i++;
	}
	quicksort3way(A, l, lt-1);
	quicksort3way(A, gt+1, h);
}

void quicksort(int A[], int l, int h) {
	if(l >= h) return;
	int p = partition2(A, l, h);
	quicksort(A, l, p-1);
	quicksort(A, p+1, h);
}

int quickselect(int A[], int N, int k) {
	//shuffle(A, N);
	int l = 0, h = N-1;
	while(l < h) {
		int p = partition(A, l, h);
		if(p == k) return A[k];
		else if(p < k) l = p + 1;
		else if(p > k) h = p - 1;
	}
	return A[k];
}

int main() {
	int A[] = {2,9,2,4,2,4,1,7,-1,0,3,8};
	quicksort(A, 0, 11);
	for(int i=0; i<12; i++)
		cout << A[i] << " ";
}

// my another version: maybe not right
int partition4(int A[], int low, int high) {
    int p = low;
    int i=low, j = high;
    while(i < j) {
        while(i <= high && A[i] <= A[p]) i++;
        while(j >= low && A[j] > A[p]) j--;
        if(i < j) swap(A[i++], A[j--]);
    }
    swap(A[j], A[p]);
    return j;
}