Help on fastest sorting method for a linked list of records. 
Author Message
 Help on fastest sorting method for a linked list of records.

Hi All ;)

I'm trying to make a Directory-Browser for a program, but need some help on
the fastest way to sort a linked list of records.

Right now I'm using the BobbelSort method, but it's way to slow !!!

Can someone please post some working code for the fastest way !

The linked list Record looks like this:

TYPE
        TheDir = ^DirList;
        DirList = RECORD
                        Number          :   WORD;
                        FileType        :   CHAR;
                        FileName        :   Str12; { STRING[12] }
                        ShowStr :   Str38; { STRING[38] }
                        HighLight       :   BOOLEAN;
                        Link            :   TheDIr;
                END;

The sorting procedure should use FileName in the record for the boolean test.

Can you help ?

Cya...

 Tonny "TOB" Bjoern


Fido: 2:236/111.185



Fri, 04 Dec 1998 03:00:00 GMT  
 Help on fastest sorting method for a linked list of records.

Quote:

> Hi All ;)

> I'm trying to make a Directory-Browser for a program, but need some help on
> the fastest way to sort a linked list of records.

> Right now I'm using the BobbelSort method, but it's way to slow !!!

> Can someone please post some working code for the fastest way !

> The linked list Record looks like this:

> TYPE
>         TheDir = ^DirList;
>         DirList = RECORD
>                         Number          :   WORD;
>                         FileType        :   CHAR;
>                         FileName        :   Str12; { STRING[12] }
>                         ShowStr :   Str38; { STRING[38] }
>                         HighLight       :   BOOLEAN;
>                         Link            :   TheDIr;
>                 END;

> The sorting procedure should use FileName in the record for the boolean test.

> Can you help ?

> Cya...

>  Tonny "TOB" Bjoern

You could try the selection sort called "Straight selection" or the
insertion sort called "Linear Insertion". But of the three sorts
(including Bubble Sort which is an exchange sort), Bubble sort is the
fastest.

Email me for the code for any of the three sorts.



Fri, 04 Dec 1998 03:00:00 GMT  
 Help on fastest sorting method for a linked list of records.

Quote:


>> Hi All ;)

>> I'm trying to make a Directory-Browser for a program, but need some help on
>> the fastest way to sort a linked list of records.

>> Right now I'm using the BobbelSort method, but it's way to slow !!!

>> Can someone please post some working code for the fastest way !

>> Can you help ?

>> Cya...

>>  Tonny "TOB" Bjoern
>You could try the selection sort called "Straight selection" or the
>insertion sort called "Linear Insertion". But of the three sorts
>(including Bubble Sort which is an exchange sort), Bubble sort is the
>fastest.
>Email me for the code for any of the three sorts.

Are you serious? Did Hoare{*filter*}up?


Sat, 05 Dec 1998 03:00:00 GMT  
 Help on fastest sorting method for a linked list of records.

Quote:

>Hi All ;)

>I'm trying to make a Directory-Browser for a program, but need some help on
>the fastest way to sort a linked list of records.

>Right now I'm using the BobbelSort method, but it's way to slow !!!

>Can someone please post some working code for the fastest way !

>The linked list Record looks like this:

>TYPE
>    TheDir = ^DirList;
>    DirList = RECORD
>                    Number          :   WORD;
>                    FileType        :   CHAR;
>                    FileName        :   Str12; { STRING[12] }
>                    ShowStr :   Str38; { STRING[38] }
>                    HighLight       :   BOOLEAN;
>                    Link            :   TheDIr;
>            END;

>The sorting procedure should use FileName in the record for the boolean test.

>Can you help ?

Have you considered using a tree instead of a list?

If you want to sort a list, the merge sort is a good way to do. Just
create a list of n lists of which each holds just one of the elements
you have (i.e. while making the list of lists, you set the links to
nil).
After you have done that repeat while there are more than one list in
the list of lists. Go through the list and merge two lists next to each
other. (Warning, merge two separate lists, do not merge two lists and
merge another to the product). If there is an odd list, you at the end
you can forget it.

Now when you have done this, you'll have a sorted list and it only takes
O(n*log n) time.

Osmo



Sun, 06 Dec 1998 03:00:00 GMT  
 Help on fastest sorting method for a linked list of records.

<<
 Right now I'm using the BobbelSort method, but it's way to slow !!!
 Can someone please post some working code for the fastest way !
 The linked list Record looks like this:

 TYPE
         TheDir = ^DirList;
         DirList = RECORD
                         Number          :   WORD;
                         FileType        :   CHAR;
                         FileName        :   Str12; { STRING[12] }
                         ShowStr :   Str38; { STRING[38] }
                         HighLight       :   BOOLEAN;
                         Link            :   TheDIr;
                 END;

 The sorting procedure should use FileName in the record for the boolean test.

The slowness is due to your using a linked list. I have written such
browsers before and have always used an array of filenames, and a
Shell sort. Here is one example:

type StringPtr= ^string;
var list: array[1..2000] of StringPtr;

procedure ShellSort(n: integer);
var  i,j,k,m: integer; swap: boolean; tmp: stringPtr;
begin  m:=1;
       while m<=n do m:=m+m; m:=(m-1) DIV 2;
       while m>0 do
       begin  for j:=1 TO n-m do
         begin  i:=j; k:=i+m; swap:=true;
           repeat if list[k]^<list[i]^ then
             begin  tmp:=list[i];
               list[i]:=list[k];
               list[k]:=tmp; i:=i-m; k:=i+m;
                  swap:=i>0;
             end else swap:=false
           until not swap
         end;
         m:=m DIV 2
       end;
end;

var N,i: integer;
begin  (* load your, say, N strings first, then sort them: *)
       ShellSort(N);
end.

Now, do not use New to to load those strings: that would use up 256
bytes every time. Rather, do this:

GetMem(list[i],length(myString)+1 {for the length byte} );
list[i]^:=myString;

Then when you are finished, deallocate memory:

for i:=N downto 1 do FreeMem(list[i],length(list[i]^)+1);

(mmm, I was assuming long file names. Of course, if they
are limited to 12 characters, you need only declare an
array of pointers to records such as you have declared as DirList,
but without a link pointing to the next record)



Mon, 07 Dec 1998 03:00:00 GMT  
 Help on fastest sorting method for a linked list of records.

Quote:

>Hi All ;)
>I'm trying to make a Directory-Browser for a program, but need some help on
>the fastest way to sort a linked list of records.
>Right now I'm using the BobbelSort method, but it's way to slow !!!
>Can someone please post some working code for the fastest way !
>The linked list Record looks like this:
>TYPE
>    TheDir = ^DirList;
>    DirList = RECORD
>                    Number          :   WORD;
>                    FileType        :   CHAR;
>                    FileName        :   Str12; { STRING[12] }
>                    ShowStr :   Str38; { STRING[38] }
>                    HighLight       :   BOOLEAN;
>                    Link            :   TheDIr;
>            END;
>The sorting procedure should use FileName in the record for the boolean test.
>Can you help ?

I had written a sort procedure using a binary tree. So you don't need
to know the length of the list to sort and it is one of the fastest
way to sort .

It was tested, it's running.

Procedure Sort_List (var list : TheDir);
{ with a binary tree }
{ With the help of Nicklaus Wirth, who wrote Algorithms + Data
Structures = Programs, edited by Prentice-Hall }

type ref = ^ leaf;
     leaf = record pdl : TheDir;
                   left, right : ref
            end;
     comparaison_result = (less,equal,greater);

var root : ref; k : TheDir;

Function Compare (a, b : Str12) : comparaison_result;
var position : 1..(12+1);
begin
if length(a) > length(b) then for position:=length(b)+1 to length(a)
do b:=b+chr(0) else
if length(b) > length(a) then for position:=length(a)+1 to length(b)
do a:=a+chr(0);
position:=1;
while (position <= length(a)) and (a[position] = b[position]) do
inc(position);
if a[position] = b[position]
   then Compare:=equal
   else if a[position] < b[position]
           then Compare:=less
           else Compare:=greater
end { Compare };

Procedure Search (x : TheDir; var p : ref);
begin
if p = nil
   then begin { insert }
        new(p);
        with p^ do begin pdl:=x; left:=nil; right:=nil end
        end
   else with p^ do
        if Compare(x^.FileName,pdl^.FileName) = less then
Search(x,left) else
        if Compare(x^.FileName,pdl^.FileName) = greater then
Search(x,right) else
        begin writeln('Error: At least two files have the same name');
Halt(1) end
end { Search };

Function PrintTree (w : ref) : TheDir;
var in_list, temp : TheDir;

Procedure insert (var list, w : TheDir);
var pointeur : TheDir;
begin
if list = nil
   then list:=w
   else begin
        pointeur:=list;
        while pointeur^.Link <> nil do pointeur:=pointeur^.Link;
        pointeur^.Link:=w
        end
end { insert };

begin { PrintTree }
in_list:=nil;
if w <> nil then with w^ do
   begin
   temp:=PrintTree(left);insert(in_list,temp);
   insert(in_list,pdl);
   temp:=PrintTree(right);insert(in_list,temp)
   end;
PrintTree:=in_list
end { PrintTree };

Function KillTree (root : ref) : ref;
begin
if root <> nil then
   begin
   with root^ do
        begin
        left:=KillTree(left);
        right:=KillTree(right)
        end;
   dispose(root); root:=nil
   end;
KillTree:=root
end { KillTree };

begin { Sort_List }
root:=nil;
while list <> nil do
      begin
      k:=list; list:=list^.Link; k^.Link:=nil;
      Search(k,root)
      end;
list:=PrintTree(root);
root:=KillTree(root)
end { Sort_List };

---
Roger Gariepy                            Be :-) even if you feel :-(

Je parle Francais.



Tue, 08 Dec 1998 03:00:00 GMT  
 Help on fastest sorting method for a linked list of records.



Quote:

><<
> Right now I'm using the BobbelSort method, but it's way to slow !!!
> Can someone please post some working code for the fastest way !
> The linked list Record looks like this:

> TYPE
>         TheDir = ^DirList;
>         DirList = RECORD
>                         Number          :   WORD;
>                         FileType        :   CHAR;
>                         FileName        :   Str12; { STRING[12] }
>                         ShowStr :   Str38; { STRING[38] }
>                         HighLight       :   BOOLEAN;
>                         Link            :   TheDIr;
>                 END;

> The sorting procedure should use FileName in the record for the boolean test.

>The slowness is due to your using a linked list. I have written such
>browsers before and have always used an array of filenames, and a
>Shell sort. Here is one example:

Shell sort is only moderately fast sort. It it is something like
O(n*n*log n) or O(n^1.5). (I think it has not bee fully analyzed.). For
a really fast solution you need an O(n*log n) solution. Those are for
example merge sort, heap sort or quick sort. I use the first one for
lists. The problem in using arrays is that those have limited sizes.

Osmo



Tue, 08 Dec 1998 03:00:00 GMT  
 Help on fastest sorting method for a linked list of records.

Quote:

> I'm trying to make a Directory-Browser for a program, but need
> some help on the fastest way to sort a linked list of records.
> Right now I'm using the BobbelSort method, but it's way to slow
> !!! Can someone please post some working code for the fastest
> way ! The sorting procedure should use FileName in the record
> for the boolean test.

================================================================
No sorting algorithm is the fastest in every possible situation.
Parameters such as number of items to be sorted, how "unsorted" the
list is to begin with, as well as the data structure being used can
affect a sort's speed. Since a linked list is specified, you may
want to use an algorithm which can easily work with that structure.
For example, try a radix distribution sort (sometimes called a
bucket sort) like the one listed below.
----------------------------------
procedure radixsort(var lp:TheDir);
var bucket:array[1..2,0..255] of TheDir;
ip:TheDir;            {array element [1,n] points to 1st entry }
i,j:integer;          {in bucket n, [2,n] to last entry        }
begin
  for i:=12 downto 1 do  
    begin                
      for j:=0 to 255 do
        bucket[1,j]:=nil;
      while lp<>nil do   {This loop puts entries into the appro- }
        begin            {priate bucket based on the character at}
          if bucket[1,ord(lp^.filename[i])]=nil  {position i     }
             then bucket[1,ord(lp^.filename[i])]:=lp
             else bucket[2,ord(lp^.filename[i])]^.link:=lp;
          bucket[2,ord(lp^.filename[i])]:=lp;
          lp:=lp^.link
        end;
      ip:=nil;
      for j:=0 to 255 do           {Once the entries have all   }
        begin                      {been distributed to the ap- }
          if bucket[1,j]<>nil      {propriate buckets, the list }
             then                  {is reformed by concatenating}
               begin               {the sublists in each bucket }
                 if ip=nil
                    then
                      begin
                        lp:=bucket[1,j];
                        ip:=bucket[2,j]
                      end
                    else
                      begin
                        ip^.link:=bucket[1,j];
                        ip:=bucket[2,j]
                      end
               end;
          ip^.link:=nil
        end
    end
end;
----------------------------------
If the filename string is a standard DOS format (CCCCCCCC.CCC) then
sorting could be done using only the first 8 letters. This would
reduce the sort time by a third.  Changing the number of buckets to
match the valid string characters would also improve the speed of
sorting.  If the valid character set is small enough, the radix can
be changed to take 2 characters at a time, cutting sort time almost
in half.
==================================================================
Derek Asari



Fri, 11 Dec 1998 03:00:00 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. Help on fastest sorting method for a linked list of records.

2. Help on fastest sorting method for a linked list of records.

3. Student help--records, linked lists, sorting

4. Fast copying records in sorted order / was Sorting

5. HELP: Sorting linked list structures

6. Help Sorting Linked List

7. Help Sorting with Pointers and Linked Lists

8. need help with sorting linked list

9. HELP: Sorting Linked List Data Structures

10. Record Link List Help please

11. Sorting a linked list by multiple criteria

12. Sorting linked lists, a comparison

 

 
Powered by phpBB® Forum Software