| |
Selection Sort | page 5 of 10 |
The Selection Sort increases efficiency over the Bubble Sort by making the comparison between an item and the smallest or largest that has been found so far in the passage through the items. (In our example below our Selection Sort procedure identifies the smaller item found on each pass through the list.) Thus swapping only occurs once each for each pass. Reducing the number of swaps makes the algorithm more efficient.
The logic of selection sort is similar to bubble sort except that fewer swaps are executed.
void selectionSort(int[] list)
{
int min, temp;
for (int outer = 0; outer < list.length - 1; outer++)
{
min = outer;
for (int inner = outer + 1; inner < list.length; inner++)
{
if (list[inner] < list[min])
{
min = inner;
}
}
//swap list[outer] & list[flag]
temp = list[outer];
list[outer] = list[min];
list[min] = temp;
}
}
Selection sort also uses passes to sort for a position in the array. Again, assuming we have a list of 6 numbers, the outer loop will range from 1 to 5. When outer = 1 , we will look for the smallest value in the list and move it to the 1st position in the array.
However, when looking for the smallest value to place in position 1, we will not swap as we search the entire list. The algorithm will check from positions 2 to 6, keeping track of where the smallest value is found by comparing with list[min] . After we have found the location of the smallest value in index position min , we swap list[outer] and list[min] .
By keeping track of where the smallest value is located and swapping once, we have a more efficient algorithm than Bubble Sort.
Here is a small list of numbers to test your understanding of Selection Sort. Fill in the correct numbers for each line after the execution of the outer loop.
| outer | 57 | 95 | 88 | 14 | 25 | 6 | | | | | | | | | | 0 |
|
|
|
|
|
| | 1 |
|
|
|
|
|
| | 2 |
|
|
|
|
|
| | 3 |
|
|
|
|
|
| | 4 |
|
|
|
|
|
|
|