Today almost all languages have their built-in sort functions. And sorting a list
can be accomplised by a single command. But as programmers go, not knowing how a
sort works is not a good thing. Also the in-line sort might not always meet your
needs. Making you familiar with how to make a sort is the goal of this text.
There are many sort algoritms available to choose from. You might even try to think
of your own, although most likely your invention wont be the first it is always
good to get the answer yourself. Each algorithm tries to sort a list by making as
few comparisons as posssible. This is not an issue today as it was ten years ago.
Even the slowest sort rutine can sort 10000 rows in a few seconds or less with
todays power in computers, at the time of the XT bubble sorting a big list was a
good excuse to go watch a movie and later take a trip into the woods.
I will start showing bubble sort and later go on to a little faster search. Also as
a history lesson when looking into old search algorithms you should think of that
not only was processor speed a problem but also you had very limited memory and
swaping back and forth on a harddisk with 500rpm instead of 10000rpm was not very
fast. So programmers had to make programs that would run fast and also use the
little memory as efficiently as possible.
The bubble sort is a very memory concervative way, but from the processor point of
view it makes alot of operations.
Lets create a list to sort
Dog
Cat
Fish
Bird
Bubble sort as the name says is similar to bubbles in water, the words move
upwards. The sort orignally is about two nested loops but i'll make a little change
to up the speed by nesting it in a repeat loop instead. Speed here of course
depends on the orignal order of the word list. The more the list is partially
sorted the less operations it will take to totally sort it.
The first code we will work is on the bubble loop it is as follows
1 2 1: for C := 1 to MaxLines-1 do3 2: begin4 3: if WordList[C]>WordList[C+1] then5 4: begin6 5: Temp := WordList[C];
7 6: WordList[C] := WordList[C+1];
8 7: WordList[C+1] := Temp;
9 8: end;
10 9: end;
Ok now lets walk through the code. The loop is set to loop from the first line in
our list all the way to the end minus one. Why this is so can be seen on line 3. In
programming languages you can compare number with the operators > < =. You can also
compare words with the same operators. This might seem strange at first. But for
the computer the letter A is actually an ascii charcter its numeric definition is
65 similiarly B is 66 and so on. The non captial letters have larger values then
their captial conturpart. And thus in a sorted list Atlas will place itself above
atlas, although this same makes it move above "zero" too. Too sort lists regardless
of their letters case is beyond this tutorial.
If we turn our attention to the code again we see that on line 3 we are comparing
words in our list. The first comparison is Dog bigger than Cat. The result is true
so the program will now run the codes on line 5, 6 and 7. If you think back to the
bubbles that move upwards Cat now has to move above Dog as it is lighter. To
replace the positions we first copy Dog into a tempory string, then we say Dog
should be Cat, and on line 7 we Replace Cat with Dog.
On the next step of this loop this time Dog and Fish is compared. It is not Cat and
Fish. Why? Because the loop already swaped Cat and Dog. Our condition checks to see
if Dog is more heavy than Fish and it says no. The condition is false our loop
continues. This time Fish and Bird are compared and since Bird is more heavy than
Fish they swap position. And this is also the last check of our loop.
Our new list is now:
Cat
Dog
Bird
Fish
As you can clearly see the bubbles are moving and our list is getting more
alphabetic. Our next step is to show the program when the sort is done. Since
dissorder in the list results in swaping of words, when all words are in alphabetic
order our loop will be out of work. I will set a boolean variable to true at the
begining of the loop and once a swap occures it will be set to false, thus the
program will now be able to tell when no bubble motion happens and the outer repeat
will stop repeating. Outer repeat? Oh i haven't written that yet so here it is.
Also to lengthen the document here is a complete pascal program for you to digest.
11 12 1: var13 2: List : array[1..10] ofstring[50];
14 3: Maxlines,C : Integer;
15 4: Temp : string;
16 5: ImOutOfWork : Boolean;
17 7:
18 6: begin19 8: List[1] := 'Dog';
20 9: List[2] := 'Cat';
21 10: List[3] := 'Fish';
22 11: List[4] := 'Bird';
23 12: MaxLines := 4;
24 13: repeat25 14: ImOutOfWork := TRUE;
26 15: for C := 1 to MaxLines-1 do27 16: begin28 17: if WordList[C]>WordList[C+1] then29 18: begin30 19: Temp := WordList[C];
31 20: WordList[C] := WordList[C+1];
32 21: WordList[C+1] := Temp;
33 22: ImOutOfWork := FALSE;
34 23: end;
35 24: end;
36 25: until ImOutOfWork;
37 26: end.
Conclusion: Our program now can sort anything you throw at it. The speed is slow
compared to other algorithms. The reason is if you have a word say "Anger" at the
end it will be boiling in anger as it can only move on step up at each loop. If the
list had 1000 words Anger would have to move up aboud 950 times.
There are many ways to optimize sort algoritms. One way would be to seperate words
according to their first letter and sort them seperatly. So instead of movin Anger
through the whole alphabet you could limit it to A words. This would speed up the
process upto 100 times faster the longer the word list the more speed would be
gained. But alas if you had to sort a phone book with thousands of folks name
starting with the letter A B C and so on this way would not be enough optimization.
But we could create a sub program that sepereated words staring with AA AB AC AD ..
till ZZ and thus minimizing each list considerably and wola phone book sorting with
bubble sort!
Another option is to add some human intelegence into the soup. The computer dosent
know the alphabet as good as us. And we could assume that the number of words for
each letter is mostly equal. Anyway finding a word starting with A at the end of
the list we could automatically throw this to begining of the list no need to se if
A is bigger the B C D E F etc.
In my next tutorial about sorting i will tell you about Quick Sort. Although no
matter what sort rutin you use a simple program to seperate the list into A words B
words etc. would create a very significant speed step. A bubble sort that is
seperated could work faster than Quick Sort. So don't take things for granted dwell
upon them you can always tweak it to perform better.
EOF Tutorial
