W2203 Selection Sort

From Coder Merlin
Jump to navigation Jump to search

Algorithm[edit]

Selection Sort starts off by selecting the first element in the array, comparing that element with other remaining elements in the array, and if a smaller element is found, both elements are swapped, bringing the smallest element at index 0. This same process is repeated with the element in the following indices.

  • Iterate over the array
  • Find the smallest element in the array, assigning that element to "i".
  • Swap "i" with the first index in the array, assigning that index to "j".
  • Find the next smallest element in the array, assigning that element to "i".
  • Swap "i" with the "j + 1" index in the array, adding one to "j".
  • Repeat until the array is sorted.

Swap[edit]

You can use the same swap function as in bubble sort and selection sort because you only need to be able to swap two elements at a time.

Performance Considerations[edit]

Given an array with 8 elements, this algorithm would have to run 8 times on the first swap, 7 times on the second swap, since that is how many unsorted elements are remaining, 6 times on the third swap, and so on, until the array is sorted. This array would run a total of 36 times.

Similar to Bubble Sort, Selection Sort would not be a suitable choice to process large amounts of data due to its long run time. Selection Sort can be good at checking if arrays are already sorted. It can also be used if memory is limited since Selection Sort does not wait to swap elements .


Example[edit]

Here is an example with an array of 5 elements:

Array: [20, 12, 10, 5, 2] | Initial

  // The algorithm first finds the smallest element: 2. Since 2 < 20, both would be swapped, bringing 2 to the first index.

Array: [2, 12, 10, 5, 20] | Total loops ran before 1st swap: 5 
          |
  // The algorithm finds the next smallest element: 5. Since 5 < 12, both would be swapped, bringing 5 to the second index.

Array: [2, 5, 10, 12, 20] | Total loops ran before 2nd swap: 9
             |
  // The algorithm finds the next smallest element: 10. Since 10 !< 10, no swap would occur.
  
Array: [2, 5, 10, 12, 20] | Total loops ran before 3rd swap: 12
                 |
  // The algorithm finds the next smallest element: 12. Since 12 !< 12, no swap would occur.

Array: [2, 5, 10, 12, 20] | Total loops ran before 4rd swap: 14
                     |
  // The algorithm finds the next smallest element: 20. Since 20 !< 20, no swap would occur.
  // The array is now fully sorted

Quiz[edit]

1 Selection Sort places unsorted elements at its place in each iteration.

False
True

2 Selection sort is practical for most problems.

True
False

3 Selection sort is most practical if:

Elements are in nearly sorted order
Doubles (floating point types) are used rather than integers
Elements are already sorted in reverse order
The set of elements is very large

4 Selection Sort repeatedly looks for and swaps the highest remaining number.

True
False

5 An element that must move toward the beginning of the list can move faster than one step per pass.

False
True

6 Elements move toward the beginning of the list very quickly.

True
False

7 Consider the list: 695, 999, -375, -488, 888, 877
After the first swap, the list will be:

695, 999, -375, -488, 888, 877
-488, -375, 888, 695, 999, 877
-488, -375, 999, 695, 888, 877
-488, 999, -375, 695, 888, 877

8 Consider the list: 695, 999, -375, -488, 888, 877
After the second swap, the list will be:

-488, -375, 888, 695, 999, 877
-488, -375, 999, 695, 888, 877
-488, 999, -375, 695, 888, 877
-488, 999, -375, 695, 999, 877

9 Consider the list: 695, 999, -375, -488, 888, 877
After the third swap, the list will be:

-488, 999, -375, 695, 888, 877
-488, -375, 999, 695, 888, 877
-488, 999, -375, 695, 999, 877
-488, -375, 695, 999, 888, 877

10 Consider the list: 695, 999, -375, -488, 888, 877
After the first pass, the list will be:

-488, -375, 888, 695, 999, 877
695, 999, -375, -488, 888, 877
-488, -375, 999, 695, 888, 877
-488, 999, -375, 695, 888, 877

11 Consider the list: 695, 999, -375, -488, 888, 877
After the second pass, the list will be:

-488, 999, -375, 695, 999, 877
-488, -375, 999, 695, 888, 877
-488, -375, 888, 695, 999, 877
-488, 999, -375, 695, 888, 877

12 Consider the list: 695, 999, -375, -488, 888, 877
How many passes are required before the algorithm terminates?

Four
Three
Two
Five


References[edit]

Selection Sort (Wikipedia)

Selection Sort (Khan Academy)


Designed with pride in Silicon Valley, CA, USA