WEEK N?

 Selection

Selection sort is probably one of the simplest and most intuitive approaches to sorting - you look through the the list (or in this case the deck of cards) to find the smallest element, and put that aside. Then you go through the rest of the deck and continue the process as many times as there were cards you started with and you end up with a sorted deck. In terms of code, a possible implementation is starting at the first (0th) element of an array, and switching it with the smallest value of the rest of the array. Then the second time through you can start on the second (1st) element and so on until you have gone through the array. 

If the size of the input (the number of elements) is n, then the first time through the list you have to check n - 1 elements. The second time, you ignore one element, so you only need to check n - 2 elements, and so on until you have 0 elements to check. So in relation to n, the number of operations you have to do is (n - 1) + (n - 2) + ... + 1 =  (n^2 + n) / 2, which means selection is O(n^2)

Recall from CSC108:

Bubble Sort:

Selection Sort:

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

64 25 12 22 11

11 25 12 22 64

11 12 25 22 64

11 12 22 25 64

11 12 22 25 64