Buble sort source code

 

Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, it is not efficient for sorting large lists; other algorithms are better.

Pseudocode implementation :

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.

 readmore>>>