Selection Sort

In selection sort algorithm, list is divided into 2 lists: sorted & unsorted list.
In each iteration, smallest element is selected from unsorted list and appended to the sorted list.

While starting the scan of list, assume that the first element is the smallest, then compare it with the rest of the elements in the list, save the index of smallest element along the way. Once all the elements are scanned, swap the starting index element with the minimum index element (if the indices are different).

Here is a Java implementation of a selection sort algorithm:

In the next post, we will look at the time & space complexity of the selection sort algorithm.

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.

Optimized Bubble Sort in Java

Bubble sort is a simplest sorting algorithm which is used as a traditional method to introduce sorting concept to the students of computer science. Though it is not very efficient algorithm, it illustrates the sorting methodology very well.

Here is a bubble sort algorithm with "two optimizations" (think!!) :

Could you find out the optimizations used in above java code?
Best case running time for this algorithm in O(n) and worst case running time is O(n^2).