#include <stdio.h>
#include <stdlib.h>
// Pivot point :
void qsortCentral(int[],int,int);// last element
void qsortFirst(int[],int,int); // first element
void qsortLast(int[],int,int); // last element
void qsortRadom(int[],int,int); // random element
int main(int argc, char** argv)
{
int tab[10000];
int i;
long double x;
for(i = 0; i < 10000; i++) { tab[i] = 10000 - i; } // printf("%d ", tab[i]); if(i%20 == 0) printf("\n"); }
// for(i = 0; i < 2500000; i++) { tab[i] = rand() % 3000000; } //printf("%d ", tab[i]); if(i%20 == 0) printf("\n"); }
printf("\n\n");
qsortLast(tab,0,9999);
for(i = 0; i < 10000; i++) { printf("%d ", tab[i]); if(i%20 == 0) printf("\n"); }
return 0;
}
void qsortCentral(int t[], int low ,int high)
{
int i,j;
int x, temp;
i = low;
j = high;
x = t[(low+high)/2];
while(i < j) {
while(t[i] < x) i++;
while(t[j] > x) j--;
if(i <= j) {
temp = t[i];
t[i] = t[j];
t[j] = temp;
i++;
j--;
}
}
if(low < j) qsortCentral(t,low,j);
if(high > i) qsortCentral(t,i,high);
}
void qsortFirst(int t[], int low ,int high)
{
int i,j;
int x, temp;
i = low;
j = high;
x = t[low];
while(i < j) {
while(t[i] < x) i++;
while(t[j] > x) j--;
if(i <= j) {
temp = t[i];
t[i] = t[j];
t[j] = temp;
i++;
j--;
}
}
if(low < j) qsortFirst(t,low,j);
if(high > i) qsortFirst(t,i,high);
}
void qsortLast(int t[], int low ,int high)
{
int i,j;
int x, temp;
i = low;
j = high;
x = t[high];
while(i < j) {
while(t[i] < x) i++;
while(t[j] > x) j--;
if(i <= j) {
temp = t[i];
t[i] = t[j];
t[j] = temp;
i++;
j--;
}
}
if(low < j) qsortLast(t,low,j);
if(high > i) qsortLast(t,i,high);
}
void qsortRadom(int t[], int low ,int high)
{
int i,j;
int x, temp;
i = low;
j = high;
// x = t[rand() % (high + 1) + low];
x = t[(rand() % (high - low )) + low];
while(i < j) {
while(t[i] < x) i++;
while(t[j] > x) j--;
if(i <= j) {
temp = t[i];
t[i] = t[j];
t[j] = temp;
i++;
j--;
}
}
if(low < j) qsortRadom(t,low,j);
if(high > i) qsortRadom(t,i,high);
}
0 Comments