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 (void* Base, int Lo, int Hi, size_t Size,
  14                        int (*Compare)(const void*, const void*))
  15 /* Internal recursive function. Works with ints, but this shouldn't be
  16  * a problem.
  17  */
  18 {
  19     int I, J;
  20
  21     /* Get a char pointer */
  22     unsigned char* B = Base;
  23
  24     /* Quicksort */
  25     while (Hi > Lo) {
  26         I = Lo + Size;
  27         J = Hi;
  28         while (I <= J) {
  29             while (I <= J && Compare (B + Lo, B + I) >= 0) {
  30                 I += Size;
  31             }
  32             while (I <= J && Compare (B + Lo, B + J) < 0) {
  33                 J -= Size;
  34             }
  35             if (I <= J) {
  36                 _swap (B + I, B + J, Size);
  37                 I += Size;
  38                 J -= Size;
  39             }
  40         }
  41         if (J != Lo) {
  42             _swap (B + J, B + Lo, Size);
  43         }
  44         if (((unsigned) J) * 2 > (Hi + Lo)) {
  45             QuickSort (Base, J + Size, Hi, Size, Compare);
  46             Hi = J - Size;
  47         } else {
  48             QuickSort (Base, Lo, J - Size, Size, Compare);
  49             Lo = J + Size;
  50         }
  51     }
  52 }
  53
  54
  55
  56 void __fastcall__ qsort (void* base, size_t nmemb, size_t size,
  57                          int (*compare)(const void*, const void*))
  58 /* Quicksort implementation */
  59 {
  60     if (nmemb > 1) {
  61         QuickSort (base, 0, (nmemb-1) * size, size, compare);
  62     }
  63 }
  64
  65
  66
  67
  68