git.sur5r.net Git - cc65/blob - libsrc/common/qsort.c

   1 /*
   2  * qsort.c
   3  *
   4  * Ullrich von Bassewitz, 09.12.1998
   5  */
   6
   7
   8
   9 #include <stdlib.h>
  10
  11
  12
  13 static void QuickSort (register unsigned char* Base, int Lo, int Hi,
  14                        register size_t Size,
  15                        int (*Compare)(const void*, const void*))
  16 /* Internal recursive function. Works with ints, but this shouldn't be
  17  * a problem.
  18  */
  19 {
  20     int I, J;
  21
  22     /* Quicksort */
  23     while (Hi > Lo) {
  24         I = Lo + Size;
  25         J = Hi;
  26         while (I <= J) {
  27             while (I <= J && Compare (Base + Lo, Base + I) >= 0) {
  28                 I += Size;
  29             }
  30             while (I <= J && Compare (Base + Lo, Base + J) < 0) {
  31                 J -= Size;
  32             }
  33             if (I <= J) {
  34                 _swap (Base + I, Base + J, Size);
  35                 I += Size;
  36                 J -= Size;
  37             }
  38         }
  39         if (J != Lo) {
  40             _swap (Base + J, Base + Lo, Size);
  41         }
  42         if (((unsigned) J) * 2 > (Hi + Lo)) {
  43             QuickSort (Base, J + Size, Hi, Size, Compare);
  44             Hi = J - Size;
  45         } else {
  46             QuickSort (Base, Lo, J - Size, Size, Compare);
  47             Lo = J + Size;
  48         }
  49     }
  50 }
  51
  52
  53
  54 void __fastcall__ qsort (void* base, size_t nmemb, size_t size,
  55                          int (*compare)(const void*, const void*))
  56 /* Quicksort implementation */
  57 {
  58     if (nmemb > 1) {
  59         QuickSort (base, 0, (nmemb-1) * size, size, compare);
  60     }
  61 }
  62
  63
  64
  65
  66