Bubblesort - Optimization
Content of the lesson:
- Optimizing the BubbleSort Algorithm
Bubblesort - Variant 3
The third version - it is even more optimized than the previous ones because of removing several more problems from the previous versions.
k:=1;
s:=false;
WHILE s=false DO
begin
s:=true;
FOR i:=1 to (pmax-k) DO
begin
IF p[i]>p[i+1] THEN
begin
pom:=p[i];
p[i]:=p[i+1];
p[i+1]:=pom;
s:=false;
end;
end;
k:=k+1;
end;
WHILE
The first FOR cycle was replaced with the WHILE cycle which allows us to change the counter and to master the final number of steps (the FOR cycle has the possibility to change counter in a few programming languages but the WHILE cycle is more general and better manageable). Then we use a boolean variable s (sorted) and set it as FALSE before the cycle is launched. Immediatelly after the BEGIN command we can assume that the array is sorted and set s:=true - using this step we can handle a situation when all numbers have already been sorted but the cycle continues because of the counter.
In case that the array is not sorted (IF p[i]>p[i+1] condition is true), the s variable is set back to false and the WHILE cycle is repeated. Otherwise the WHILE cycle is terminated because there is no more data to process.
Difference between pmax-1 and pmax-k
The principle of stairs can be handled similarly to the second variant (you can change pmax-1 to pmax-k) You should not forget to assign k:=1 before launching the WHILE cycle, otherwise the program would not function. There also cannot be value 2 for example because the array would not be browsed to the end. Then you have to increase the value of k by one after each step inside the WHILE cycle to realize the principle of stairs. We improved several more possibilities which can occur when sorting an array and we reduced the number of steps so the algorithm can run faster.
The following graph compares numbers of browsed items and rows when using 10 000 items.
Bubblesort - Variant 4 - The Last Optimization
k:=1;
s:=false;
WHILE s=false DO
begin
s:=true;
FOR i:=(0+k) to (pmax-k) DO
begin
IF p[i]>p[i+1] THEN
begin
pom:=p[i];
p[i]:=p[i+1];
p[i+1]:=pom;
s:=false;
end;
end;
FOR i:=(pmax-k) downto (1+k) DO
begin
IF p[i]
pom:=p[i];
p[i]:=p[i-1];
p[i-1]:=pom;
s:=false;
end;
end;
k:=k+1;
end;
The last optimization is to speed up the whole sorting process. This variant does not only put the highest value to the end but it also puts the smallest value to the beginning inside one step. In every following step only numbers between 1+k and pmax-k are being processed (k is increased by one in each step). The schema looks like a reversed pyramid.
You can see a graph comparing this variant with the previous ones:
Source Code Used to Compare the Speed of Each Variant
The following source code can be downloaded here: bubblesortcomparison.pas (you will need Delphi to open it).
const pmax=1000;
type pole=array[1..pmax] of integer;
var k,i,pom,opakovani:integer;
p,pz:pole;
s:boolean;
pocetk,poceti:longint;
begin
Randomize;
opakovani:=0;
WHILE opakovani<10 DO
begin
FOR i:=1 to pmax DO p[i]:=random(3000);
FOR i:=1 to pmax DO pz[i]:=p[i];
{start of nonoptimized without K}
pocetk:=0;
poceti:=0;
FOR k:=1 to (pmax-1) DO
begin
FOR i:=1 to (pmax-1) DO
begin
IF p[i]>p[i+1] THEN
begin
pom:=p[i];
p[i]:=p[i+1];
p[i+1]:=pom;
end;
poceti:=poceti+1;
end;
pocetk:=pocetk+1;
end;
writeln('Pocet K neop: ',pocetk);
writeln('Pocet I neop: ',poceti);
{end of nonoptimized without K}
{start of nonoptimized with K}
FOR i:=1 to pmax DO p[i]:=pz[i];
pocetk:=0;
poceti:=0;
FOR k:=1 to (pmax-1) DO
begin
FOR i:=1 to (pmax-k) DO
begin
IF p[i]>p[i+1] THEN
begin
pom:=p[i];
p[i]:=p[i+1];
p[i+1]:=pom;
end;
poceti:=poceti+1;
end;
pocetk:=pocetk+1;
end;
writeln('Pocet K neop s k: ',pocetk);
writeln('Pocet I neop s k: ',poceti);
{end of nonoptimized with K}
{start of optimized}
FOR i:=1 to pmax DO p[i]:=pz[i];
k:=1;
pocetk:=0;
poceti:=0;
s:=false;
WHILE s=false DO
begin
s:=true;
FOR i:=1 to (pmax-k) DO
begin
IF p[i]>p[i+1] THEN
begin
pom:=p[i];
p[i]:=p[i+1];
p[i+1]:=pom;
s:=false;
end;
poceti:=poceti+1;
end;
k:=k+1;
pocetk:=pocetk+1;
end;
writeln('Pocet K optimal: ',pocetk);
writeln('Pocet I optimal: ',poceti);
{end of optimized}
{start of optimized 2}
FOR i:=1 to pmax DO p[i]:=pz[i];
k:=1;
pocetk:=0;
poceti:=0;
s:=false;
WHILE s=false DO
begin
s:=true;
FOR i:=(0+k) to (pmax-k) DO
begin
IF p[i]>p[i+1] THEN
begin
pom:=p[i];
p[i]:=p[i+1];
p[i+1]:=pom;
s:=false;
end;
poceti:=poceti+1;
end;
FOR i:=(pmax-k) downto (1+k) DO
begin
IF p[i]<p[i-1] THEN
begin
pom:=p[i];
p[i]:=p[i-1];
p[i-1]:=pom;
s:=false;
end;
poceti:=poceti+1;
end;
k:=k+1;
pocetk:=pocetk+2;
end;
writeln('Pocet K optimal2: ',pocetk);
writeln('Pocet I optimal2: ',poceti);
{end of optimized 2}
opakovani:=opakovani+1;
writeln('Pocet kompletniho cyklu ',opakovani);
writeln;
end;
readln;
end.
Homework
Find at least two more sorting algorithms in the Internet and realize one of them using Pascal.
Questions
- Describe the principle of the BubbleSort algorithm.
- Which optimizations can you use when programming the BubbleSort algorithm?
- Name at least two more examples of sorting algorithms.