El algoritmo quicksort, con un ejemplo de implementación:
#include <stdio.h>
#include <stdlib.h>
#define MAX_ITM 500000
void qsort (int*,int,int);
void swap(int&,int&);
int rdtsc();
int main() {
int arr[MAX_ITM];
for (int i=0;i < MAX_ITM;i++) {
srand(rdtsc());
arr[i] = rand();
}
printf("List initialized. Press enter to sort it...");getchar();
qsort(arr,0,MAX_ITM-1);
printf("List sorted. Press enter to print it...");getchar();
for (int i=0;i < MAX_ITM;i++)
printf ("%d\t",arr[i]);
getchar();
return 0;
}
int rdtsc() {__asm__ __volatile__("rdtsc");}
void swap(int &n, int &m) {int t=n;n=m;m=t;}
void qsort (int arr[],int p,int q) {
if(q <= p)
return;
int piv = arr[p];
int i=p+1, j=q;
while(true) {
while( (i < q) && (arr[i] <= piv) ) i++;
while( (j > p) && (arr[j] > piv) ) j--;
if(j <= i)
break;
else
swap(arr[i],arr[j]);
}
swap(arr[p],arr[j]);
qsort(arr,p,j-1);
qsort(arr,j+1,q);
}
Ahora el Insertsort:
#include <stdio.h>
#include <stdlib.h>
#define MAX_ITM 500000
void isort(int*,int);
int rdtsc();
int main() {
int arr[MAX_ITM];
for (int i=0;i < MAX_ITM;i++) {
srand(rdtsc());
arr[i] = rand();
}
printf("List initialized. Press enter to sort it...");getchar();
isort(arr,MAX_ITM);
printf("List sorted. Press enter to print it...");getchar();
for (int i=0;i < MAX_ITM;i++)
printf ("%d\t",arr[i]);
getchar();
return 0;
}
int rdtsc() {__asm__ __volatile__("rdtsc");}
void isort(int array[], int n) {
for(int i = 1; i < n; i++) {
int v = array[i], j = i - 1;
while(j >=0 && array[j] > v)
array[j + 1] = array[j--];
array[j + 1] = v;
}
}