Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!apple!lins
From: lins@Apple.COM (Chuck Lins)
Newsgroups: comp.lang.modula2
Subject: Re: Sorts
Keywords: Sorting Lists
Message-ID: <34664@apple.Apple.COM>
Date: 12 Sep 89 16:25:40 GMT
References: <heilpern@VAX1.ACS.UDEL.EDU> <INFO-M2%89091120313809@UCF1VM>
Organization: Apple Computer Inc, Cupertino, CA
Lines: 56

In article <INFO-M2%89091120313809@UCF1VM> Modula2 List <INFO-M2%UCF1VM.bitnet@jade.berkeley.edu> writes:
>
>    Bubble sort is a little bit too slow for my application.  I need to sort
>  a linked list in memory.  The algorithm I want must not use or
>  require a FIXED array to sort, as the list is dynamic.
>    Lists are not like arrays either, if you go swapping elements in the list
>  pointers become mixed up and you end up trying to sort the interrupt table
>  or screen (which isnt't very good).
>    For the time being I have to use a fixed ARRAY OF POINTERS and then sort
>  the array using a comparison routine that checks the information
>  that the pointers are pointing to, which suprisingly works, but strikes me
>  as being a rather ridiculous way to sort the list.  Besides, the array
>  limits the amount of information I can store, which I don't want to do.
>

Alex,

There are several alternative approaches you can take:
1. use quicksort for lists. Originally developed by Dalia Motzkin, in an
article that appeared in Communications of the ACM I think in the mid-70's. A
Pascal implementation appears in G.H. Gonnet's book "Handbook of Algorithms
and Data Structures", Addison-Wesley, 1983.

2. Use a dynamically allocated array of pointers instead of a fixed size one.
An outline of how this could be done follows:

MDOULE SortPointers;

TYPE ptrData = POINTER TO Data;
TYPE arrayOfPtrs = ARRAY [0..100000] OF ptrData;
     (* or some other very large number for the maximum index *)

VAR  myArray : POINTER TO arrayOfPtrs;

BEGIN
  (* allocate an array of the size you need *)
  Allocate(myArray, SIZE(ptrData) * "number of pointers in the array");

  (* fill the array with the pointers *)

  (* sort it *)
  (* do whatever else you need to do with the sorted data *)

  (* get rid of the array of pointers when done *)
  Deallocate(myArray, SIZE(ptrData) * "number of pointers");
END SortPointers.

The only limitation depends on the compiler - will it allow a very large index
or does it limit the data space used for arrays (e.g., 32/64K limits on arrays
that appear in microcomputer Modula and Pascal compilers).

-- 
Chuck Lins                      | "Exit right to funway."
Internet:   lins@apple.com      | AppleLink: LINS
Snail Mail: 20525 Mariani Ave. M/S: 41-K Cupertino, CA 95014
"I like the future - I'm in it." - Firesign Theater