-
The Selection Sort also makes several passes through the list. On each pass, it compares each remaining item to the smallest (or largest) item that has been found so far in the pass. In the example below, the Selection Sort method finds the smallest item on each pass. At the end of a pass, the smallest item found is swapped with the last remaining item for that pass. Thus, swapping only occurs once 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(ArrayList <Integer> list){
int min, temp;
for (int outer = 0; outer < list.size() - 1; outer++){
min = outer;
for (int inner = outer + 1; inner < list.size(); inner++){
if (list.get(inner) < list.get(min)) {
min = inner; // a new smallest item is found
}
}
//swap list[outer] & list[min]
temp = list.get(outer);
list.set(outer, list.get(min));
list.set(min, temp);
}
}
Again, assuming that 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 first position in the array.
-
However, when looking for the smallest value to place in position 1, we will not swap as we search through the list. The algorithm will check from indexes 1 to 5, keeping track of where the smallest value is found by saving the index of the smallest value in min. After we have found the location of the smallest value, we swap list[outer] and list[min].
-
By keeping track of where the smallest value is located and swapping only 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. (Answers are found in Lesson A17 Handout, Sorting Answers.)
