Sıralama Algoritmaları Yarışması

Sıralama algoritmaları karışık durumdaki dizileri sıralarken bilindiği gibi farklı algoritmalar kullanırlar.

Fakat hangisinin en hızlı olduğu işte aşağıdaki kodlar yardımıyla ortaya çıkıyor. Fakat burada dikkat çekmek istediğim nokta bu algoritmaların hızlarının karşılaştırıldığı. En hızlı olanın aynı zamanda en verimli algoritma olduğu her zaman söylenemez.

Aşağıdaki kodları çalıştırılanlar 7 tane sıralama algoritmasının 100 bin elamanlı bir dizi üzerinde sıralama yaparken ne kadar zaman harcadıklarını görecekler.

Yarış başlasın :)

Not : Windows sistemleri için system("clear") komutunu system("cls") olarak değiştirin.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE        100000
#define SORTSIZE    8

typedef struct _sort {
 char name[25];
 double time;
}sort;

double calctime(double start);

int *setRandomArray(int *a, int size);
void displayArray(const int *a, int size);
void displaySort(sort *p, int size);
void sortSort(sort *p, int size);


int fcmp(const void *vp1, const void *vp2); //for qsort
void sift(int *p, int left, int right);     //for heap sort

//Sort Algorithms
void bubble_sort(int *p, int size);
void selection_sort(int *p, int size);
void shell_sort (int *p, int size);
void merge_sort (int *p, int size);
void insertion_sort(int *p, int size);
void heap_sort (int *p, int size);


int main(void)
{
 int array[SIZE];
 clock_t start;
 sort sortarray[SORTSIZE];

 srand((unsigned int)time(0));

 printf("S o r t   A l g o r i t h m s\n");
 printf("=============================\n\n");

 printf("%d element array\n", SIZE);
 printf("----------------------\n\n");



 //Selection sort
 printf("Selection sort is working\n");
 setRandomArray(array, SIZE);
 start = clock();
 selection_sort(array, SIZE);
 sprintf(sortarray[1].name, "Selection sort");
 sortarray[1].time = calctime(start);

 //Bubble sort
 printf("Bubble sort is working\n");
 setRandomArray(array, SIZE);
 start = clock();
 bubble_sort(array, SIZE);
 sprintf(sortarray[2].name, "Bubble sort");
 sortarray[2].time = calctime(start);

 //Qsort
 printf("Qsort is working\n");
 setRandomArray(array, SIZE);
 start = clock();
 qsort(array, SIZE, sizeof(int), &fcmp);
 sprintf(sortarray[3].name, "Qsort");
 sortarray[3].time = calctime(start);

 //Merge sort
 printf("Merge sort is working\n");
 setRandomArray(array, SIZE);
 start = clock();
 merge_sort(array, SIZE);
 sprintf(sortarray[4].name, "Merge sort");
 sortarray[4].time = calctime(start);

 //Insertion sort
 printf("Insertion sort is working\n");
 setRandomArray(array, SIZE);
 start = clock();
 insertion_sort(array, SIZE);
 sprintf(sortarray[5].name, "Insertion sort");
 sortarray[5].time = calctime(start);

 //Heap sort
 printf("Heap sort is working\n");
 setRandomArray(array, SIZE);
 start = clock();
 heap_sort(array, SIZE);
 sprintf(sortarray[6].name, "Heap sort");
 sortarray[6].time = calctime(start);

 //Shell sort
 printf("Shell sort is working\n");
 setRandomArray(array, SIZE);
 start = clock();
 shell_sort(array, SIZE);
 sprintf(sortarray[7].name, "Shell sort");
 sortarray[7].time = calctime(start);


 //Results
 system("clear");
 printf("S o r t   A l g o r i t h m s\n");
 printf("=============================\n\n");
 sortSort(sortarray, SORTSIZE);
 displaySort(sortarray, SORTSIZE);

 getchar();
 return 0;
}

void sortSort(sort *p, int size)
{
   int  i, j;
   sort temp;

   for (i = 0; i < size - 1; i++)
      for (j = 0; j < size - i - 1; j++)
         if (p[j].time > p[j + 1].time) {
            temp = p[j];
            p[j] = p[j + 1];
            p[j + 1] = temp;
         }

}

void displaySort(sort *p, int size)
{
    int k;

    for (k = 1; k < size; k++)
      printf("%d) %s -> %.3f\n", k, p[k].name, p[k].time);


}


int *setRandomArray(int *a, int size)
{
    int i;

    for (i = 0; i < size; i++)
        a[i] = rand() % 1000 + 100;

    return a;
}

void displayArray(const int *a, int size)
{
    int i;

    for (i = 0; i < size; i++)
        printf("%d ", a[i]);
}

double calctime(double start)
{
    clock_t end = clock();


    return (double)(end - start) / CLOCKS_PER_SEC;
}

//for Qsort
int fcmp(const void *vp1, const void *vp2)
{
 return *(const int *)vp1 -  *(const int *)vp2;
}

//for Heap sort
void sift(int *p, int left, int right)
{
   int temp, i;

   i = left +left +1;
    temp = p[left];

   do {
      if (i < right && p[i] < p[i+1])
         i++;
      if (temp >= p[i])
         break;
      p[left] = p[i];
      left = i;
      i = 2 * i + 1;
   } while (i <= right);
   p[left] = temp;
}




void bubble_sort(int *p, int size)
{
   int   i, j, temp;

   for (i = 0; i < size - 1; i++)
      for (j = 0; j < size - i - 1; j++)
         if (p[j] > p[j + 1]) {
            temp = p[j];
            p[j] = p[j + 1];
            p[j + 1] = temp;
         }
}

void selection_sort(int *p, int size)
{
   int   i, j, temp, min;

   for (i = 0; i < size - 1; i++) {
      min = i;
      for (j = i + 1; j < size; j++)
         if (p[min] > p[j])
            min = j;
      temp = p[min];
      p[min] = p[i];
      p[i] = temp;
   }
}

void shell_sort (int *p, int size)
{
   int   i, j, k, temp;

   for (k = size; k > 1; ) {
      k = (k < 5) ? 1 : ((k * 5 - 1) / 11);
      for (i = k - 1; ++i < size; ) {
         temp = p[i];
         for (j = i; p[j - k] > temp; ) {
            p[j] = p[j - k];
            if ((j -= k) < k)
               break;
         }
         p[j] = temp;
      }
   }
}

void merge_sort (int *p, int size)
{
   int *t, *q, *buf;
   int   left, len, count1, count2, source1, source2, dest;

   if (size <= 1)
      return;
   buf = q = (int *) malloc(size * sizeof(int));
   if (buf == NULL) {
      printf("not enough memory!");
      exit(EXIT_FAILURE);
   }
   len = 1;

   do {
      left = size;
      source1 = dest = 0; source2 = len;
      do {
         left -= count1 = (left >= len) ? len : left;
         left -= count2 = (left >= len) ? len : left;
         while (count1 > 0 && count2 > 0) {
            if (p[source1] < p[source2]) {
               q[dest++] = p[source1++];
               count1--;
            }
            else {
               q[dest++] = p[source2++];
               count2--;
            }
         }
         while (--count1 >= 0)
            q[dest++] = p[source1++];
         while (--count2 >= 0)
            q[dest++] = p[source2++];
         source1 += len; source2 += len;
      } while (left > 0);
      t = p;
      p = q;
      q = t;
      len *= 2;
   } while (len < size);
   if (p == buf)
      while (--size >= 0)
         q[size] = p[size];
   free(buf);
}

void insertion_sort(int *p, int size)
{
   int   i, j, t;

   for (i = 0; ++i < size; ) {
      t = p[i];
      for (j = i; p[j - 1] > t; ) {
         p[j] = p[j - 1];
            if (--j <= 0) break;
      }
      p[j] = t;
   }
}

void heap_sort (int *p, int size)
{
   int  left, right, temp;

   if (size <= 1)
      return;
   left = size / 2;
   right = size - 1;

   while (--left >= 0)
      sift(p, left, right);

   for (;;) {
      temp = p[0];
      p[0] = p[right];
      p[right] = temp;
      if (--right <= 0)
         break;
      sift(p, 0, right);
   }
}