Exchange sort

Exchange Sort (Bubble Sort)

Basic Idea:

Make repeated passes through a list of items, exchanging adjacent items if necessary. At each pass, the largest unsorted item will be pushed in its proper place. Stop when no more exchanges were performed during the last pass. The elements with the largest value are moved slowly or bubbled to the top. If no exchanges are made during one pass over the data, the data has been sorted and the process terminates.

Algorithm: BubbleSort(A,n)

Input: An array A storing n items

Output: A sorted in ascending order

loop1 i = 1 to n-1; step = 1

loop2 j = 0 to n-i; step = 1

if A[j] > A[j+1]

temp = A[j]

A[j] = A[j+1]

A[j+1] = temp

endif

Endloop2

Endloop1

Example:

(a)In first pass 390 is compared with 205; then exchanged as 250 is smaller

(b) 390 is compared with 182, they exchanged. Result is shown in (c )

In (c )390 is compared with 45, they exchanged

Then in (d) 390 is compared with 235 and exchanged

Result is (e) – regarding the columns as arrays - element 390 has ‘bubbled’ from index 0 to highest index (4)

Improvements on Bubble Sort:

1. Since all elements in a position greater than or equal to n-i are already in proper position after iteration i, they need not be considered in a succeeding iteration.
2. To eliminate unnecessary passes, we must be able to detect the fact that the list is already sorted. Thus, keeping the record of whether or not any interchange is made in a given pass, we can eliminate unnecessary iterations.

Improved BubbleSort

Algorithm: BubbleSort(A,n)

Input: An array A storing n items

Output: A sorted in ascending order

Flag = 1

loop1 i = 1 to i

Flag = 0

loop2 j = 0 to n-1-i; step = 1

if A[j] > A[j+1]

temp = A[j]

A[j] = A[j+1]

A[j+1] = temp

Flag = 1

Endif

Endloop2

Endloop1

Example:

Analysis of BubbleSort Algorithm

Best Case: O(n)

• Array is already sorted in ascending order
• The number of moves: 0 => O(1)
• The number of key comparisons: n-1 => O(n)

Worst Case: O(n²)

• Array is in reverse order
• Outer loop is executed n-1 times
• The number of moves: 3*(1+2+3+. . .+n-1) = 3*n*(n-1)/2 => O(n²)
• Number of key comparisons: (1+2+3+. . .+n-1) = n*(n-1)/2 => O(n²)

Average Case: O(n²)

• We have to look at all possible initial data organizations

So, Bubble Sort is O(n²).

References:

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction toAlgorithms”
2. G. Brassard and P. Bratley, “Fundamentals of Algorithms”

.