O(n) Selection

จาก Theory Wiki
รุ่นแก้ไขเมื่อ 08:07, 18 ตุลาคม 2551 โดย 202.29.77.2 (คุย) (สร้างหน้าใหม่: <pre> #include <stdio.h> #include <stdlib.h> #define min(a,b) (((a)<(b))?(a):(b)) void swap(int &x, int &y) { int temp = x; x = y; y = temp; } void sel...)
(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)
ไปยังการนำทาง ไปยังการค้นหา
#include <stdio.h>
#include <stdlib.h>

#define min(a,b) (((a)<(b))?(a):(b))

void swap(int &x, int &y)
{
	int temp = x;
	x = y;
	y = temp;
}

void selection_sort(int *x, int n)
{
	for(int k=0;k<n-1;k++)
	{
		int min_position = k;
		for(int i=k;i<n;i++)
			if (x[min_position] > x[i])
				min_position = i;
		swap(x[min_position], x[k]);
	}
}

int select(int *x, int n, int k);

int choose_pivot(int *x, int n)
{
	for(int start=0;start<n;start+=5)
		selection_sort(x+start, min(5, n-start));
	for(int i=0;i<n/5;i++)
	{
		int start = i*5;
		int end = min(n-1, start+5-1);
		int mid = (start+end)/2;
		swap(x[i], x[mid]);
	}
	return select(x, n/5, n/10);
}

int partition(int *x, int n)
{
	int pivot_position = choose_pivot(x, n);
	swap(x[pivot_position], x[0]);
	int last = 1;
	for(int i=1;i<n;i++)
		if (x[0] >= x[i])
		{
			swap(x[last], x[i]);
			last++;
		}
	swap(x[last-1], x[0]);
	return last-1;
}

int select(int *x, int n, int k)
{
	if (n <= 1)
		return 0;
	else
	{
		int mid = partition(x, n);
		if (k == mid)
			return mid;
		else if (k < mid)
			return select(x, mid, k);
		else
			return select(x+mid+1, n-mid-1, k-mid-1);
	}
}

int a[10000];

#define FOR(__i, __times) for(int __i=0;__i<__times;__i++)

int main()
{
	FOR(i, 10000)
		a[i] = rand() % 32767;
	int answer = select(a, 10000, 5000);
	printf("%d\n", answer);
	return 0;
}