- Forward


Selection Sort
An Introduction with Examples


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back SMYC Forward
  • A Popular Motivation:
    • Between 25% and 50% of computing time in commercial applications is devoted to sorting
    • Hence, it is important to consider the efficiency of sorting algorithms
  • My Motivation:
    • The issues that arise are illustrative of the issues that arise when developing other algorithms
    • They provide good examples of how to find the efficiency of an algorithm
Selection Sort
Back SMYC Forward
  • The Algorithm:
    • Iteratively select the largest value in the list and swap it with the element at the bottom of the list, moving the bottom up by one
  • Compared to Bubble Sort:
    • The bubble sort tends to move many more elements than does the selection sort
    • The bubble sort "painstakingly" moves an element to the top by swapping adjacent elements rather than by searching and making only one swap
An Example
Back SMYC Forward
  • The Array to Sort:
    • The six-element array (8, 4, 7, 3, 9, 3)
  • Iteration 1:
    • The 9 in element 4 is swapped with the 3 in element 5 and the bottom is moved up to 4
    • Note that this requires an inner loop that searches through all of the elements in the array
    • 8 4 7 3 3 9
  • Iteration 2:
    • The 8 in element 1 is swapped with the 3 in element 4 and the bottom is moved up to 3
    • 3 4 7 3 8 9
  • The Remaining Iterations:
    • 3 4 3 7 8 9
      3 3 4 7 8 9
      3 3 4 7 8 9
An Implementation
Back SMYC Forward
cppexamples/sorting/SelectionSort.cpp
 
Efficiency Analysis
Back SMYC Forward
  • The Outer Loop:
    • Always \(n-1\) iterations
  • The Inner Loop:
    • The first time through the inner loop iterates \(n-1\) times
    • The second time through the inner loop iterates \(n-2\) times
    • ...
Efficiency Analysis (cont.)
Back SMYC Forward

\( T(n) = (n-1) + (n-2) + \cdots 2 + 1 = n \cdot (n-1)/2 \)

So: \( T(n) = O(n^2) \)

There's Always More to Learn
Back -