## Bubble Sort

Reference: https://commons.wikimedia.org/wiki/File:Sorting_bubblesort_anim.gif

Compare each element in the list with the one before it, starting with the last (or maybe the first) element. Replace the two elements if one element is less than the preceding one. **Bubble Sort** operates by periodically switching with the neighboring items.

Once the list has been sorted through, we must repeat this process n-1 times, where n is the length of the list.

An example of **Bubble Sort**

If A=[40, 50, 10, 35, 90, 15, 5, 60]

**Parse 01**

[40, 50, 10, 35, 90, 15, 5, 60] //Compare last 2 element, 5<60 no interchange [40, 50, 10, 35, 90, 15, 5, 60] //A[6] with A[5], interchange (swap) 15 and 5 [40, 50, 10, 35, 90, 5, 15, 60] //A[5] and A[4], swap 90 with 5 [40, 50, 10, 35, 5, 90, 15, 60] //A[4] with A[3], 35 swap with 5 [40, 50, 10, 5, 35, 90, 15, 60] //A[3] with A[2], 10 swap with 5 [40, 50, 5, 10, 35, 90, 15, 60] //A[2] with A[1], 50 swap with 5 [40, 5, 50, 10, 35, 90, 15, 60] //A[1] with A[0], 40 swap with 5 [5, 40, 50, 10, 35, 90, 15, 60] //The smallest element 5 is in its proper position

Following the initial parsing, the smallest element has been placed correctly.

**Parse 02**

[5, 10, 40, 50, 15, 35, 90, 60] //Here, 10 is its proper position

**Parse 03**

[5, 10, 15, 40, 50, 35, 60, 90] //15 is its proper position

**Parse 04**

[5, 10, 15, 35, 40 , 50, 60, 90] //35 is its proper position

**Parse 05**

[5, 10, 15, 35, 40 , 50, 60, 90] //40 is its proper position

**Parse 06**

[5, 10, 15, 35, 40 , 50, 60, 90] //50 is its proper position

**Parse 07**

[5, 10, 15, 35, 40 , 50, 60, 90] //60 is its proper position

[5, 10, 15, 35, 40 , 50, 60, 90] //Sorted list

**Bubble Sort** Algorithm

BubbleSort(A[]){ for (index=0; i<A.length-1; i++){ for (j=A.length-1; j>i; --j){ swap elements in positions j and j-1 if they out of order; } } }

**Bubble Sort** running time analysis is **O(n²)**