October 2010 - VR+AR+CG+CV+HCI

Quick Sort This is used in research code when built-in qsort does not satisfy the demands.

void qs(int l, int r){
	int p, mid, i, j;

	i = l; j = r; mid = avg[(l + r) >> 1];
	do {
		while (avg[i] < mid) ++i;
		while (avg[j] > mid) --j;
		if (i <= j){
			swap(avg[i], avg[j]);
			swap(order[i], order[j]);
			++i;
			--j;
		}
	} while (i <= j);
	if (l < j) qs(l, j);
	if (i < r) qs(i, r);
}

void qs(int l, int r){

int p, mid, i, j;

i = l; j = r; mid = avg[(l + r) >> 1];

do {

while (avg[i] < mid) ++i;

while (avg[j] > mid) --j;

if (i <= j){

swap(avg[i], avg[j]);

swap(order[i], order[j]);

++i;

--j;

}

} while (i <= j);

if (l < j) qs(l, j);

if (i < r) qs(i, r);

}

K-th element Qsort can be used to find the Kth smallest element a[k]:

void Kth(int l,int r,int k)
{
	int i = l,j = r,mid= a [(i + j) >> 1];
	while (i <= j) {
		while (a[i] < mid) ++i;
		while (a[j] > mid) --j;
		if (i<=j) {
			int t = a[i]; a[i] = a[j]; a[j] = t;
			++i;--j;
		}
	}
	if (k >= i && k<= r) Kth(i, r, k);
	if (k >= l && k<= j) Kth(l, j, k);
}

void Kth(int l,int r,int k)

{

int i = l,j = r,mid= a [(i + j) >> 1];

while (i <= j) {

while (a[i] < mid) ++i;

while (a[j] > mid) --j;

if (i<=j) {

int t = a[i]; a[i] = a[j]; a[j] = t;

++i;--j;

}

if (k >= i && k<= r) Kth(i, r, k);

if (k >= l && k<= j) Kth(l, j, k);

}

Use partition to sort 0, 0, 0, 1, 1, 2, 2, 2…

void Solutions::sortColors(vector<int>& nums) {
	partition(
		partition(nums.begin(), nums.end(), bind1st(equal_to<int>(), 0)),
		nums.end(), bind1st(equal_to<int>(), 1)
		);
}