Showing posts with label Bubble sort analysis. Show all posts
Showing posts with label Bubble sort analysis. Show all posts

Wednesday, October 28, 2015

Bubble Sort: Illustrated

Bubble sort is called "Bubble Sort" because the largest item in the list bubbles up to the end of a list after each iteration.

Following images illustrate this concept.

In this example the length of an array is 6.
In first iteration of a for loop (where j = 1), index i starts at 0 and ends at 5 (lenght - j).


In second iteration of a for loop (where j = 2), index i starts at 0 and ends at 4 (lenght - j).


In third iteration of a for loop (where j = 2), index i starts at 0 and ends at 3 (lenght - j).



In fourth iteration of a for loop (where j = 3), index i starts at 0 and ends at 2 (lenght - j).


In this iteration, there was no swapping of items as the list is already sorted. Hence the while loop terminates.

As you can see, after each iteration of a for loop, the length of an iteration reduces by 1 (because of an optimization condition i < length - j). Another optimization used is the boolean variable "swapped", if there no swaps during an iteration, that means the list is already sorted. So we can terminate outer loop immediately.