Pascal Bubble Sort Implementation

Question

I would prefer a review of:

• Efficiency
• Standards
• Different approaches

Here's the code:

program bubbleSort;
var
 toSort: array[1..5] of integer = (3, 25, 2, 69, 1);
 passChanges: boolean = true;
 counter, index, temp: integer;
begin
 while passChanges do
 begin
 index := 1;
 passChanges := false;
 for index := 1 to length(toSort) - 1 do
 begin
 if (toSort[index] > toSort[index +1]) then
 Begin
 temp := toSort[index + 1];
 toSort[index + 1] := toSort[index];
 toSort[index] := temp;
 passChanges := true;
 end;
 end;
 end;
 for counter := 1 to length(toSort) do
 writeln(toSort[counter]);
 readln;
end.

Answer 1

As long as we're bumping this older question:

 for index := 1 to length(toSort) - 1 do

You don't need to iterate over the entire array every time. You could set a variable and decrement it. E.g.

 unsortedCount: integer = length(toSort);

Then before the loop

 Dec (unsortedCount);

While this won't change the asymptotic analysis (still quadratic worst case), it can cut the effective time. This works because Bubble Sort is guaranteed to move the largest element in a segment to the last position in each pass. Once that's done, that element will no longer move. So we don't need to check it again and can reduce the segment size.

Note: it's been at least thirty years since I programmed in Pascal. And I was not an expert on Pascal syntax then. Please don't take anything I wrote as suggesting the correct Pascal way to do things. This is purely an algorithmic review.

Answer 2

This is a rather old request, and its been quite a while since I've coded in Pascal, but I'd like to make a few recommendations for this code.

Currently the entire behavior of the sorting is in the main program. If you extract the sorting into its own function it will be easier to reuse the code as well as test it with additional combinations as input. To do this efficiently you'll probably want to declare a new type for an array of integers to use as an input argument and the function return.

while passChanges do

The intent of this while loop is to always execute at least once until passChanges is true. This requires you to set passChanges to true prior to entry into the loop. It may be cleaner and less error prone to use a repeat until loop rather than a while do loop as repeat until is guaranteed to execute at least once.

 index := 1;

You set the index variable to 1 and then don't use it again until the for loop. This line serves no purpose and can be deleted.

 Begin

Here you capitalize Begin where as everywhere else it is all lowercase. I recommend picking one style and being consistent as it make the code easier to read and less "surprising."