202.29.77.2: สร้างหน้าใหม่:

 #include  #include   #define min(a,b) (((a)<(b))?(a):(b))  void swap(int &x, int &y) { 	int temp = x; 	x = y; 	y = temp; }  void sel...

2008-10-18T08:07:16Z

สร้างหน้าใหม่: <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...

หน้าใหม่

<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 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;
}
</pre>

O(n) Selection - ประวัติรุ่นแก้ไข

202.29.77.2: สร้างหน้าใหม่:
#include #include #define min(a,b) (((a)<(b))?(a):(b)) void swap(int &x, int &y) { int temp = x; x = y; y = temp; } void sel...