Allan Didier

Allan Didier

Computer Science Teacher
Menu
Allan Didier > Mr. Didier’s Classes > AP Computer Science > APCS Skills > Selection Sort Explanation

AP Computer Science

Menu

Selection Sort Explanation

Description

Selection sort is a sorting algorithm that sorts elements by finding the smallest element (ascending order) in a set and putting it at the beginning of the set. You “select” the smallest and move it to the front. Click here for the Selection Sort assignment.

 

Logic

The basic logic of the algorithm goes as such:
  1. Find the smallest element in the set.
  2. Swap this element with the first element.
  3. Repeat with a subset not including the already sorted elements. 

Coding

Like most sorting algorithms, it consists of two loops.
  1. The outer (first) loop states how many elements need to be sorted.
    1. Generally needs to run through all of the elements. 
    2. Technically, one element is often left out.
      1. Sorting often compares two elements. You often leave an element out since you need to compare an element to the one next to it. You don’t sort the last element since you have noting to compare it to.
      2. If you have 20 elements to sort, by the time you have sorted the first 19, the 20th will be will in place. 
    3. If you only need to sort say the first 5 elements, this loop can be limited to 5. 
  2. The inner loop does the actual sorting and swapping.
    1. Search though the set for the smallest element. 
      1. This is a Linear Search. We also did this twice earlier in the year with the Math Methods assignment.
      2. If you want to reverse the order, search for the largest element.
    2. Swap the first element with the smallest element. 
    3. When repeated (the outer loop), use a smaller set of elements.
      1. Don’t include the first elements since they are already sorted and the smallest elements. 
      2. Hint: this loop doesn’t start at 0.

Example

  • Initial array (10 elements): 31, 45, 13, 55, 52, 20, 98, 8, 78, 62
  • First pass
    • Find lowest = 8. 
    • Swap with lowest with the first element, 31.
    • Array after first pass: 8, 45, 13, 55, 52, 20, 98, 31, 78, 62
  • Second pass
    • Ignore the first element as it is already sorted.
    • Find the lowest = 13
    • Swap lowest with the second element, 45
    • Array after second pass: 8, 13, 45, 55, 52, 20, 98, 31, 78, 62
  • Third pass
    • Ignore the first two elements.
    • Find the lowest = 20
    • Swap lowest with the third element, 45
    • Array after the third pass: 8, 13, 20, 55, 42, 45, 98, 31, 78, 62
  • Repeat
    • You can stop at 9th element. Once that is sorted, the 10th element will be in place. 
 

Advantages and Disadvantages

  • Fairly straightforward code. 
  • Very efficient if you are looking for only the smallest (or largest) elements in a set. 
  • Not very efficient at sorting all of the elements of a large set, but more efficient than Bubble Sort

Other Resources

Edhesive T2 Lesson 15: Selection Sort

AP College Board Video: Sorting

Geeks for Geeks: text explanation