Selection Sort

• Selection Sort “divides” the array into a sorted portion AND an unsorted portion.  To begin with, the entire array is considered unsorted
• The first task is to locate the smallest element in the unsorted portion of the array and swap it with the first element in the unsorted portion of the array. repeat until one remain in unsorted portion.
• While a timer can give us insight into the speed of an algorithm, time is not the best way to measure the speed of an algorithm:

  • hardware varies

  times differ with same number of elements
• Computer Scientist tend to use time complexity (asymptotic run time) to describe the performance, complexity, or space requirement of an algorithm.
• Time complexity seeks to describe the speed of an algorithm by noting the number of comparisons that are made in relation to the total number of elements.
• In all cases (best, average, worst), Selection Sort is of order n2, or Ω (n2), Θ (n2), O (n2).
• Selection Sort makes a quadratically increasing number of comparisons depending on the number of elements (n) being sorted.
• O(1) - constant

  O(n) - linear

  O(n2) - quadratic 

  O(log2n) - logarithmic 

  O(n * log2n) - linear * logarithmic

  O(x^n) - exponential