Mega Code Archive
Bubble sorting in delphi-pascal
<![CDATA[
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: for C := 1 to MaxLines-1 do
2: begin
3: if WordList[C]>WordList[C+1] then
4: begin
5: Temp := WordList[C];
6: WordList[C] := WordList[C+1];
7: WordList[C+1] := Temp;
8: end;
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.
1: var
2: List : array[1..10] of string[50];
3: Maxlines,C : Integer;
4: Temp : string;
5: ImOutOfWork : Boolean;
7:
6: begin
8: List[1] := 'Dog';
9: List[2] := 'Cat';
10: List[3] := 'Fish';
11: List[4] := 'Bird';
12: MaxLines := 4;
13: repeat
14: ImOutOfWork := TRUE;
15: for C := 1 to MaxLines-1 do
16: begin
17: if WordList[C]>WordList[C+1] then
18: begin
19: Temp := WordList[C];
20: WordList[C] := WordList[C+1];
21: WordList[C+1] := Temp;
22: ImOutOfWork := FALSE;
23: end;
24: end;
25: until ImOutOfWork;
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
]]>