APPLICATIONSDIVERS ★ Shelling out for strings ★

Machine Code Shell Sort (Computing with the Amstrad)Applications Divers
★ Ce texte vous est présenté dans sa version originale ★ 
 ★ This text is presented to you in its original version ★ 
 ★ Este texto se presenta en su versión original ★ 
 ★ Dieser Text wird in seiner Originalfassung präsentiert ★ 

Sort character arrays in a flash with MIKE MEE's clever utility

AFTER reading the excellent series in the June and July issues on sorting data, you may be frustrated by the speed - or lack of it - at which Basic can deal with such tasks. When a large amount of information is involved, it's definitely a case of patience being a virtue. Fortunately, with my utility you can throw said virtue out the window.

Anyone who has, or is developing, a Basic program that stores and manipulates string array data - for instance a mailing list, club membership register, or accounting system - will find Program I invaluable. It installs some machine code which is capable of sorting a string array into ascending or descending order. It also gives a quick - literally -demonstration of its power.

After running the program, the syntax for using the facility is:

CALL sort,sort,ord,@array$(first),last-first

That may look complicated, but in practice it is quite straightforward. Say you have a string array called fred$. It has 100 elements numbered 0-99, and you want them in descending order.

Your program will have incorporated Program I, so the variable sort will already be set up with the correct value - the address of the sort routine. If you are sure what you are doing, you can alter the value of sort in the
loader so that the machine code lives wherever you want it to. If you don't understand that, don't fiddle with it!

The variable ord tells the routine whether it has to sort in ascending or descending order - 56 or 48 respectively. first and last are the first and last elements of the array to be included in the sort. In this case they will be 0 and 99, but you can work on any subsection of the array you want:

CALL sort,sort,48,@fred$(0),99

One point to note is that value of last must be greater or equal than two, and first must be less than or equal to last-2. This program will only work on string arrays, so you must convert numeric data to string format using the STR$ command.

And that's all you need to use the utility, but for those interested in the nuts and bolts here is some background information. Sorting is one of the most common operations in applications programming, and a
great deal of research has gone into the development of efficient algorithms. Previous articles have explained how most of these work, so I'm not going to go into great detail. However, I would like to explain why I chose the shell sort.

Three non-job specific methods were narrowed down as contenders, namely the quick, selection and shell sorts. Quick sort, as the name implies, is fast. However it was ruled out because it requires dynamic array space in which to store its partition pointers. Or more simply put, it needs two extra arrays for intermediate results, which in turn consumes precious memory.

Selection sort was put aside due to the fact that the same number of compares and swaps is made if the list is random, or if only one element is out of order, therefore making it quite slow.

Shell sort, however, is pretty fast for random lists and does not require extra arrays. As you will remember, shell sort works by applying half the array size as a gap, and successively comparing and swapping elements as necessary. The gap is halved with each repetition until finally adjacent elements are compared. At this stage the array is sorted.

In general purpose Basic the algorithm looks like this:

10 first=0:last=100:gap=last:DIM array$(last)
20 if gap=1 THEN END ELSE gap=INT(gap/2)
30 swapflag=0:limit=last-gap
40 FOR lo=start TO limit
50 hi=lo*gap
60 IF array$(lo) < = array$(hi) THEN 90
70 SWAP array$(lo) , array$(hi)
80 swapflag=1
90 NEXT lo
100 IF swapflags1 THEN 30 ELSE 20

Of course there isn't a SWAP command in Amstrad Basic to exchange the values in the array elements, but I put it like that to make the method clear. Do not type this example in, it is for explanatory purposes only!

To see a working version I suggest you refer back to the Sort it Out series published in the June and July issues and compare the timings to those produced by the machine code. You'll be astounded at the results - it's about 25 times faster.

CWTA

★ PUBLISHER: Computing with the Amstrad
★ YEAR: 1988
★ CONFIG: 64K + AMSDOS
★ LANGUAGE:
★ LICENCE: LISTING
★ AUTHOR: Mike Mee

★ AMSTRAD CPC ★ DOWNLOAD ★

Type-in/Listing:
  » Machine  Code  Shell  Sort    (Computing  with  the  Amstrad)    ENGLISH    LISTINGDATE: 2020-07-31
DL: 1 fois
TYPE: PDF
SIZE: 60Ko
NOTE: 1 page/PDFlib v1.6

Je participe au site:
» Newfile(s) upload/Envoye de fichier(s)
★ AMSTRAD CPC ★ A voir aussi sur CPCrulez , les sujets suivants pourront vous intéresser...

Lien(s):
» Applications » RSX Disksort (Schneider Magazin)
» Applications » All sorted out (Popular Computing Weekly)
» Applications » Disksort Star (CPC Amstrad International)
» Applications » Sort-Pack (Schneider Magazin)
» Applications » Qsort (CPC Amstrad International)
» Applications » Sort the Rainbow (Computing With the Amstrad)

QUE DIT LA LOI FRANÇAISE:

L'alinéa 8 de l'article L122-5 du Code de la propriété intellectuelle explique que « Lorsque l'œuvre a été divulguée, l'auteur ne peut interdire la reproduction d'une œuvre et sa représentation effectuées à des fins de conservation ou destinées à préserver les conditions de sa consultation à des fins de recherche ou détudes privées par des particuliers, dans les locaux de l'établissement et sur des terminaux dédiés par des bibliothèques accessibles au public, par des musées ou par des services d'archives, sous réserve que ceux-ci ne recherchent aucun avantage économique ou commercial ». Pas de problème donc pour nous!

CPCrulez[Content Management System] v8.7-desktop/cache
Page créée en 113 millisecondes et consultée 17 fois

L'Amstrad CPC est une machine 8 bits à base d'un Z80 à 4MHz. Le premier de la gamme fut le CPC 464 en 1984, équipé d'un lecteur de cassettes intégré il se plaçait en concurrent  du Commodore C64 beaucoup plus compliqué à utiliser et plus cher. Ce fut un réel succès et sorti cette même années le CPC 664 équipé d'un lecteur de disquettes trois pouces intégré. Sa vie fut de courte durée puisqu'en 1985 il fut remplacé par le CPC 6128 qui était plus compact, plus soigné et surtout qui avait 128Ko de RAM au lieu de 64Ko.