The ups and downs of sorting out data
★ 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 ★ 

ALEATOIRE gives you a lift with understanding quick search algorithms

ANY years ago when computers were mysterious giants that filled up a ballroom and required a dozen people shovelling coal and flicking switches to make them work there were no random access devices. Everything that the machines were fed or regurgitated was sequential, usually on paper or magnetic tape.

Consequently a great deal of time and effort was spent in devising efficient sorting, hence quick searching, algorithms. One of the biggest problems was that computers had very limited memory, or main store, compared with the size of the data records to be sorted, and this gave rise to the elevator puzzle.

Imagine a building with F floors, each holding exactly P people but with the majority of them on the wrong floor. There is a single elevator that can carry, at most, E people and E (the computer memory) is smaller than P. the maximum number of people or records that you want to shift.

The elevator always starts at the ground floor. It can move up and down, loading and dropping people until everyone is where they should be - the elevator then returns to the ground floor.

The problem is how to sort all the people in the minimum number of moves, where a move is up or down a floor, that is we want to minimise the distance the elevator has to travel.

Program I will allow you to practice and learn how to solve this classic problem. To make it easier to visualise I have named the seven families (three members each) and the seven floors of the building after the colours of the rainbow with the Reds living at the top and the Violets at the bottom.

To test that it is working remove, or ignore, (ines 110-170 and you should find that the families start in the reverse order — that is. Reds at the bottom, Violets at the top - and that you have exactly 40 moves to sort them all out. See Figure I.

7. Red V V V
6. Orange I I I
5. Yellow B B B
4. Green G G G
3. Blue Y Y Y
2. Indigo O O O
1. Violet R R R
Figure I. The starting pattern of the program test. Sort all the colours back to their correct levels in 40 moves.

The number of moves is the correct and absolute minimum required and is calculated by lines 190-260. The program will check that you do not exceed this limit, but has no idea itself, nor gives any clue, about how to solve the puzzle.

To further test that the program is working you should note that you (playing the elevator) are "empty” at the start (contain two Whites), that you can "see” three Reds and that entering U or D does actually move you up and down the levels correctly.

To swop, hence sort, colours just enter the first letter of a colour you have followed by the first letter of a colour you can see at the current level. For instance, at the start of the test entering WR will swop a White for a RED. Note that a swop does not count as a move. Only U and D are counted.

If all this is working, replace lines 110-170 and the program will mix up the colours randomly, calculate the minimum number of moves to sort them out, obey your commands and check your progress.

If you have never seen this sort of problem before it is very unlikely that you will be able to solve any of the literally thousands of starting patterns it can generate.

You may imagine that you must need to know where all the colours
are before you can start. This is true for the program because it has to calculate the number of moves, but you can solve the problem every time without this prior knowledge by using the following, simple algorithm.

You, the elevator, start in the UP state.

1: If in the UP state and anyone needs to go up. then get the two that need to go highest and move up one floor. Otherwise change to the DOWN state.

2: If in the DOWN state, pick the two who need to go lowest and move down one floor. If no one at this new floor, or below this floor, needs to go to a higher floor, change to the UP state.

If you follow these rules exactly and without thinking - just like a computer - you will always succeed in sorting out any pattern.

The things to notice are that at the start you will always go straight up to the 7th level and inevitably drop the two Reds that you will have found on the way.

If you go wrong later on. and take too many moves, you have almost certainly broken the second part of rule 2. that is you have moved down when no one below needed to come higher than the current floor.

With practice the puzzle becomes trivial, but note that the algorithm will work for any number of levels and any number of people, providing the number of people exceeds the size of the elevator.

How it does this is quite spooky. You will notice that occasionally people are taken from their correct level and even made to travel in the wrong direction.

This is because the system is communist, in that it does the greatest good for the greatest number and the rights of the individual are totally ignored.

The elevating moral of this sort story is that rights and privileges do not make the world go round and actually get in the way of it going up or down.


★ PUBLISHER: Computing with the Amstrad
★ YEARS: 1985 , 1986
★ AUTHOR: Roland Waddilove


  » Sort  the  Rainbow    (Computing  with  the  Amstrad)    ENGLISHDATE: 2020-07-23
DL: 2 fois
NOTE: 40 Cyls

★ AMSTRAD CPC ★ A voir aussi sur CPCrulez , les sujets suivants pourront vous intéresser...

» Applications » Sort the Rainbow (Computing With the Amstrad)
» Applications » Machine Code Shell Sort (Computing with the Amstrad)
» Applications » Qsort (CPC Amstrad International)
» Applications » Disc-Sorter (RSE Software)
» Applications » Disc - Sorter
» Applications » Alphabetical Sorting (Amstrad Computer User)


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 240 millisecondes et consultée 30 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.