quicksort.c

Denna kod är public domain. Om ni hittar fel eller vill ändra något i koden blir jag jätteglad om ni skickar dessa ändringar till jesper [at] fantasi [punkt] se.

/*
 * QuickSort lägger alla 'stora' tal i ena änden av listan och alla mindre
 * i den andra, delar sedan listan och gör samma sak igen med vardera delen.
 * Denna uppdelning fortsätter tills alla listor endast innehåller ett tal.
 * Efter detta sätts delarna ihop igen i rätt ordning.
 */

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

static int partition(int *numbers, int low, int high)
{
   int x = numbers[low];
   int i = low - 1;
   int j = high + 1;

   while (i < j)
   {
      do
      {
         j--;
      }
      while (numbers[j] > x);

      do
      {
         i++;
      }
      while(numbers[i] < x);

      if (i < j)
      {
         int tmp = numbers[i];
         numbers[i] = numbers[j];
         numbers[j] = tmp;
      }
      else
         break;
   }
   return j;
}

static void quickSort(int *numbers, int low, int high)
{
   if (low < high)
   {
      int middle = partition(numbers, low, high);
      quickSort(numbers, low, middle);
      quickSort(numbers, middle + 1, high);
   }
}

int main(void)
{
   int tal[20];
   int i;

   srand((unsigned int)time(NULL));
   printf("Talen innan sortering:\n");
   for (i = 0; i < 20; i++)
   {
      tal[i] = (int)((rand() / (double)RAND_MAX) * 1000);
      printf("%d ", tal[i]);
   }
   printf("\n");

   quickSort(tal, 0, 19);

   printf("Talen efter sortering:\n");
   for (i = 0; i < 20; i++)
      printf("%d ",tal[i]);
   printf("\n");

   return EXIT_SUCCESS;
}