Bubble Sort

(** Bubble sort algorithm.
*
* Author: Paulo Roma
* Date: 21/04/2008.
* http://en.wikipedia.org/wiki/Bubble_sort
*)

program Bubble_Sort;

type SArray = array of integer;
var Asize: integer;
var A: SArray;
var i: integer;

(** bubbleSort.
*
* Sorts A=(A0, A1, ..., An) into nondecreasing order of keys.
* This algorithm has a worst case computational time of O(n**2).
* Stable.
*
* Bubble sort is a straightforward and simplistic method of sorting
* data that is used in computer science education.
* The algorithm starts at the beginning of the data set.
* It compares the first two elements, and if the first is greater
* than the second, it swaps them. It continues doing this
* for each pair of adjacent elements to the end of the data set.
* It then starts again with the first two elements, repeating until
* no swaps have occurred on the last pass. While simple, this algorithm
* is highly inefficient and is rarely used except in education.
* A slightly better variant, cocktail sort, works by inverting the
* ordering criteria and the pass direction on alternating passes.
* Its average case and worst case are both O(n**2).
*
* Large elements at the beginning of the list do not pose a problem,
* as they are quickly swapped. Small elements towards the end,
* however, move to the beginning extremely slowly.
* This has led to these types of elements being named rabbits and
* turtles, respectively.
*
* @param A array to be sorted.
* @param n number of elements to be sorted.
*)

procedure bubbleSort( var A: SArray; n: integer );
var swapped: boolean;
var i, temp: integer;
begin
repeat
swapped := false;
n := n - 1;
for i := 0 to n-1 do begin
if ( A[i] > A[i+1] ) then begin
// swap
temp := A[i];
A[i] := A[i+1];
A[i+1] := temp;
swapped := true;
// every time one pass of this loop is completed,
// the largest element has been moved to the end
// of the array
end
end;
until not swapped;
end;

begin
write ( 'Enter number of elements: ' );
read ( Asize );
// alocate an array from 0 to Asize-1
// the array index is always zero-based
SetLength ( A, Asize );
// generate the seed
randomize;
// fill A with random numbers in the range [0..99]
for i := 0 to Asize-1 do
A[i] := random (100);

// print original array
for i := 0 to Asize-1 do begin
write (A[i]); write (' ');
end;
writeln;

// sort
bubbleSort ( A, Asize );

// print sorted array
for i := 0 to Asize-1 do begin
write (A[i]); write (' ');
end;
writeln;
end.