Articles   Members Online:
-Article/Tip Search
-News Group Search over 21 Million news group articles.
-Delphi/Pascal
-CBuilder/C++
-C#Builder/C#
-JBuilder/Java
-Kylix
Member Area
-Home
-Account Center
-Top 10 NEW!!
-Submit Article/Tip
-Forums Upgraded!!
-My Articles
-Edit Information
-Login/Logout
-Become a Member
-Why sign up!
-Newsletter
-Chat Online!
-Indexes NEW!!
Employment
-Build your resume
-Find a job
-Post a job
-Resume Search
Contacts
-Contacts
-Feedbacks
-Link to us
-Privacy/Disclaimer
Embarcadero
Visit Embarcadero
Embarcadero Community
JEDI
Links
Bubble Sorting in Delphi/Pascal Turn on/off line numbers in source code. Switch to Orginial background IDE or DSP color Comment or reply to this aritlce/tip for discussion. Bookmark this article to my favorite article(s). Print this article
28-Mar-05
Category
Algorithm
Language
Delphi All Versions
Views
401
User Rating
9
# Votes
1
Replies
0
Publisher:
Yardimli, Ekim
Reference URL:
			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 do
3    2:  begin
4    3:   if WordList[C]>WordList[C+1] then
5    4:   begin
6    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: var
13  2:   List : array[1..10] of string[50];
14  3:   Maxlines,C : Integer;
15  4:   Temp : string;
16  5:   ImOutOfWork : Boolean;
17  7:
18  6:   begin
19  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:   repeat
25  14:     ImOutOfWork := TRUE;
26  15:     for C := 1 to MaxLines-1 do
27  16:     begin
28  17:     if WordList[C]>WordList[C+1] then
29  18:     begin
30  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 

			
Vote: How useful do you find this Article/Tip?
Bad Excellent
1 2 3 4 5 6 7 8 9 10

 

Advertisement
Share this page
Advertisement
Download from Google

Copyright © Mendozi Enterprises LLC