Bubble Sort Algorithm in Data Structures

Bubble sort is the simple sorting algorithm. The algorithm of bubble sort is comparison-based in which each pair of adjacent elements is compared and the elements are swapped if they are not in order. This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n2) where n is the number of items.

Let A be a list of ‘n’ numbers. Sorting A refers to the operation of re-arranging the elements of A, so they are in increasing order, i.e. so that

A[1]< A[2]< A[3]< …….. <A[N]

For example, Suppose A originally is the list 8, 4, 19, 2, 7, 13, 5, 16. After sorting, A is the list 2, 4, 5, 7, 8, 13, 16, 19.

Algorithm: (Bubble Sort.)

BUBBLE(A, N). Here, A is an array with N elements. This algorithm sorts the elements in A.

Step I: Repeat steps 2 to 4 for K=1 to N-1.

[This loop is for number of passes.]

Step II: Set PTR:= 1. [Initializes pass pointer PTR.]

Step III: Repeat step 4 while PTR <= N-K: [Execute pass.]

[This step 3 loop is for comparisons.]

Step IV: If A[PTR] > A[PTR+1], then:

[Interchange the elements.]

a) TEMP:= A[PTR]

b) A[PTR]:= A[PTR+1]

c) A[PTR+1] := TEMP

[End of If structure.]

Step V: Set PTR:= PTR+1. [Increase pointer.]

[End of step 3 loop.]

[End of step 1 loop.]

Step VI: Exit.