Bubble Sort ( concept & algorithm )

The oldest and simplest sort in use.

Unfortunately, also the slowest.

Works by comparing each item in the list with the item next to it, and swapping them if required.

---

The algorithm repeats this process until it makes a pass all the way through the list without swapping any items.

This causes larger values to "bubble" to the end of the list while smaller values "sink" towards the beginning of the list.

---

Algorithm :

Suppose the list of number A[1], [2], A[3], …, A[N] is in memory. Algorithm works as follows.

[1]  Compare A[1] and A[2], arrange them in the desired order so that A[1] < A[2]. Then Compare A[2] and A[3], arrange them in the desired order so that A[2] < A[3]. Continue until A[N-1] is compared with A[N], arrange them so that A[N-1] < A[N].  

[2]  Repeat Step 1, Now stop after comparing and re-arranging A[N-2] and A[N-1]. 

[3]  Repeat Step 3, Now stop after comparing and re-arranging A[N-3] and A[N-2]. 

.

.

[N-1]  Compare A[1] and A[2] and arrange them in sorted order so that A[1] < A[2].

After N-1 steps the list will be sorted in increasing order. 

---

A Bubble Sort Example :

see image of each step carefully :

step 1: 

step 2:
       

Step 3:

Step 4:

Step 5:

Step 6:

Step 7:

Step 8:

Step 9:

Step 10 :  As you can see, the largest number
has “bubbled” down, or sunk to the bottom of the List after the first pass through the List

Step 11 : For our second pass through the List, we start by comparing these first two elements in the List.

Repeat process again for n-1 term then again for n-2 term ....... at last we found sorted list.

---

Algorithm :

DATA is an array with N elements

[1] Repeat Step 2 and 3 for K =1 to N-1

[2] Set PTR :=1 

[3] Repeat While PTR <= N –K 

(a) If DATA[PTR] > DATA[PTR+1]

Interchange DATA[PTR] and DATA[PTR + 1]

(b) Set PTR = PTR + 1

[4] Exit 

---

---

Analysis of Bubble Sort :

    f(n) = (n-1) + (n-2) + …. + 2+1 = n(n-1)/ 2 = O(n2 )

---

C PRogram : bubble-sort-in-c