[Back to SORTING SWAG index]  [Back to Main SWAG index]  [Original]

> Could someone please post some code on using a quick
> sort to sort an array of strings?

   I can do even better than that. I can give you some code on a general qsort
routine that works like in C (if you're familiar with that). I. e. you can sort
any type of arrays, if only you supply the correct compare function. Here

unit QSort;
 *                     QSORT.PAS                         *
 *           C-like QuickSort implementation             *
 *     Written 931118 by Bj”rn Felten @ 2:203/208        *
 *           After an idea by Pontus Rydin               *
type CompFunc = function(Item1, Item2 : word) : integer;

procedure QuickSort(
    var Data;
{An array. Must be [0..Count-1] and not [1..Count] or anything else! }
{Number of elements in the array}
    Size    : word;
{Size in bytes of a single element -- e.g. 2 for integers or words,
4 for longints, 256 for strings and so on }
    Compare : CompFunc);
{The function that decides which element is "greater" or "less". Must
return an integer that's < 0 if the first element is less, 0 if they're
equal and > 0 if the first element is greater. A simple Compare for
words can look like this:

 function WordCompare(Item1, Item2: word): integer;
     WordCompare := MyArray[Item1] - MyArray[Item2]

NB. It's not the =indices= that shall be compared, it's the elements that
the supplied indices points to! Very important to remember!
Also note that the array may be sorted in descending order just by
means of a simple swap of Item1 and Item2 in the example.}

procedure QuickSort;

  procedure Swap(Item1, Item2 : word);
  var  P1, P2 : ^byte; I : word;
     if Item1 <> Item2 then
          I  := Size;
          P1 := @Data; inc(P1, Item1 * Size);
          P2 := @Data; inc(P2, Item2 * Size);
            mov  cx,I      { Size }
            les  di,P1
            push ds
            lds  si,P2
            mov  ah,es:[di]
            mov  [si-1],ah
            loop @L
            pop  ds

  procedure Sort(Left, Right: integer);
  var  i, j, x, y : integer;
     i := Left; j := Right; x := (Left+Right) div 2;
        while compare(i, x) < 0 do inc(i);
        while compare(x, j) < 0 do dec(j);
        if i <= j then
           swap(i, j); inc(i); dec(j)
     until i > j;
     if Left < j then Sort(Left, j);
     if i < Right then Sort(i, Right)

begin Sort(0, Count) end;

end. { of unit }

{ A simple testprogram can look like this: }

program QS_Test; {Test QuickSort   la C}
uses qsort;
var v: array[0..9999] of word;
    i: word;

{$F+} {Must be compiled as FAR calls!}
function cmpr(a, b: word): integer;
begin cmpr := v[a] - v[b] end;

function cmpr2(a, b: word): integer;
begin cmpr2 := v[b] - v[a] end;

 for i := 0 to 9999 do v[i] := random(20000);
 quicksort(v, 10000, 2, cmpr);  {in order lo to hi}
 quicksort(v, 10000, 2, cmpr2); {we now have a sorted list, sort it in
                                {reverse -- nasty for qsort!}
 quicksort(v, 10000, 2, cmpr);  {and reverse again}
 quicksort(v, 10000, 2, cmpr);  {sort a sorted list -- also not very popular}

[Back to SORTING SWAG index]  [Back to Main SWAG index]  [Original]