APPLICATIONSDIVERS ★ SELECTION SORT|COMPUTING WITH THE AMSTRAD) ★

LET'S SORT IT ALL OUT... (Computing with the Amstrad)Bubble quickly or shell out? (Computing with the Amstrad)
★ 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 ★ 

SIMON MONK and SUE BRADSHAW begin a two-part article on sorting data in Basic

A COMPUTER program, be it a word processor, database, or game, is about processing data. Often a vital part of the processing is sorting the data into order, and this was one of the first tasks to which computers were put in their early days.

Sorting by computer is well understood, and many methods - or algorithms - have been developed. The majority are refinements of older techniques, but five fundamental types have emerged which have been around for some time now.

It is unlikely that any more will be developed in the near future, unless they appear riding on the back of technological advances like parallel processing as found in the transputer.

We will be showing you how these sorting techniques can be used on your CPC, and how to decide on one for particular circumstances. Even if you have no immediate use for sorting, you should find this an interesting avenue for exploration if you're just getting to grips with Basic

The choice of sorting method depends on three things:

  • How much information is to be sorted. Some algorithms work very quickly for a small amount of data, but rapidly get bogged down if more than a few hundred items need to be sorted.
    These algorithms are often referred to as n squared types because the time they take to sort is related to the square of the number of items. For instance, if 100 items take 1 second to be sorted, 500 items do not take 5 seconds, but 25 seconds.
    On the other hand, some algorithms take a relatively long time to sort a few numbers, but do not take a great deal longer to sort many.
  • Data already partly in order will make some algorithms perform much faster, but will have little effect on others.
  • The amount of work needed to program the algorithm must be considered. There is no point in writing a super-fast 300 line sorting routine to deal with a list of 10 numbers.

Accompanying this article are examples in Basic of the main sorting algorithms. We have tried to make them as general purpose as possible so they can be used in your own programs without too much modification.

If the sort needs to be written in another language, first go through the algorithms by hand and make sure you understand what they are doing.

In this connection we find a pack of cards very useful or, if you like, cut up squares of paper and write a number on each. You can then move them around to follow what is going on.

The examples all assume integers are being sorted into ascending order. To sort strings, change the array to an array of strings, and any variables used to hold an element of the array into string variables. Altering the routines to sort in descending order is not difficult if you can follow how the algorithm works.

To use the programs, first load the test program - Program I - and then merge the sorting routine of your choice. CPC464 owners with disc drives should save the modules as Ascii (use the ,a save option) to avoid a bug in the disc operating system rearing its head.

The test program should be self-explanatory once you run it. It generates a list of random numbers, puts them in the array a, and sorts them into order using the chosen method.

One point worth mentioning is that you'll be asked for a random number seed. If you specify the same one with different algorithms, you will get the same list of random numbers. This means you can do valid time comparisons, because the amount of sorting required will be the same in each case.

With different seeds you'll get different lists of random numbers which may be more (or less) out of order, and therefore not be a fair contest.

Selection sort

This is a very widely-used method. It is quick for a small number of items, easy to program, and easy to understand. This algorithm sorts the data from the left and keeps a marker to show where the sorted part of the data stops and the unsorted part starts.

1: The unsorted marker is put at the first item of data.

2: The smallest number in the unsorted section is found and exchanged with the first number in the unsorted section.

3: The unsorted marker is moved one step to the right so that it now points to what was the smallest number in the unsorted section.

4: Repeat steps two to four until the unsorted marker points to the last number.

Here's an example:

10 3 8 5 9 6
*

10 is the first unsorted number, so swap it with the smallest unsorted number which is 3. Then move the marker right one:

3 10 8 5 9 6
*

Now 5 is the smallest unsorted number so swap it with the first unsorted which is 10. Move the marker right one:

3 5 8 10 9 6
*

Next swap 6 with 8:

3 5 6 10 9 8
    *

Now 8 with 10:

3 5 6 8 9 10
      *

Now the smallest number in the unsorted section is 9, which is also the first number in the unsorted section. So we swap 9 with 9 which is a bit silly but perfectly possible. We therefore end up with:

3 5 6 8 9 10
          *

Program II is an implementation of the selection sort algorithm. Just merge it with the test program and you'll be able to see it in action. To help you see how it relates to the description. Table I lists the variables used and their functions.

unsorted:
smallest:
i:
Marks the edge of the unsorted region
Position of smallest unsorted item
Loop counter
Table I: Variables used in selection sort subroutine

Insertion Sort

This algorithm has the advantage of working more quickly if the data is already partly in order. It is more difficult to program than selection sort, but is quicker even if the data is random.

Like selection sort, the insertion method keeps a marker to show where the unsorted part of the data starts, and works from left to right.

1: The smallest number in the data set is swapped with the first number. This is done only once.
2: The marker is moved to the second item of data.
3: The first unsorted number is inserted into its correct position in the sorted section. This enlarges the sorted section by one, so the marker is moved one place to the right.
4: Step three is repeated until the data is sorted.

An example:

10 3 8 5 9 6

10 is swapped with the smallest number (3), and the unsorted marker is placed at the second number:

3 10 8 5 9 6
*

10 is inserted in its correct position in the sorted section, which does not involve its moving. However the marker must be moved:

3 10 8 5 9 6
  *

Now it is the turn of 8 to be inserted. It goes between 3 and 10 so after the marker has been moved we get:

3 8 10 5 9 6
     *

Next 5 is inserted between 3 and 8:

3 5 8 10 9 6
        *

Now 9 is inserted between 8 and 10:

3 5 8 9 10 6
           *

Finally 6 is inserted between 5 and 8:

3 5 6 8 9 10
          *

unsorted:
minimum:
smallest:
i:
elem:
aux:
temp:
Marks the edge of the unsorted region.
Minimum value in the array.
Pointer to the minimum element.
Loop variable.
Contains an element of the array.
Auxiliary pointer to the array.
Temporary variable.
Table II: Variables used in insertion sort subroutine

Marks the edge of the unsorted region.
Minimum value in the array.
Pointer to the minimum element.
Loop variable.
Contains an element of the array.
Auxiliary pointer to the array.
Temporary variable.

Program III is the subroutine to merge with Program I for a demonstration, and Table II lists the variables used.

  • So that's two ways of sorting data. Next time we'll have a look at other powerful techniques, and see how the various algorithms compare for speed.

CWTA

★ PUBLISHER: Computing with the Amstrad
★ YEAR: 1988
★ CONFIG: 64K + AMSDOS
★ LANGUAGE:
★ LICENCE: LISTING
★ AUTHORS: SIMON MONK and SUE BRADSHAW

★ AMSTRAD CPC ★ DOWNLOAD ★

Type-in/Listing:
» Selection  Sort    (Computing  with  the  Amstrad)    ENGLISHDATE: 2020-07-31
DL: 11 fois
TYPE: ZIP
SIZE: 6Ko
NOTE: 40 Cyls
.HFE: NON

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 » Tri Turbo (Microstrad)
» Applications » Tri (AM-Mag)
» Applications » Video Club 1.500 películas
» Applications » Alphabetical Sorting (Amstrad Computer User)
» Applications » Tri pour BankManager
» Applications » Machine Code Shell Sort (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 243 millisecondes et consultée 168 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.