Bubblesort
IDEA: "While the array is not sorted, swap adjacent elements that are out of order."
for (int i=0; i<len; i++) for (int j=0; j<len-i; j++) if (array[j] > array[j+1]) swap(array[j], array[j+1]); Bubblesort takes its name from the image of the "lightest" elements "rising" to the top of the array, like bubbles in water. Bubblesort comes in unidirectional and bidirectional varieties; the latter is not asymptotically better than the former, but shaves a constant factor off the running time.
Selectsort
IDEA: "Select the minimum element in the current array and place it in the first position. Then, do the same for the remainder of the array."
This has a natural recursive formulation, of course:
select_sort(T * array, int left, int right) { if (left != right) { int min_idx = find_min_idx(array, left, right); swap(array[left], array[min_idx)); select_sort(array, left+1, right); } } However, this has a significant asymptotic space cost (what is it?). Therefore, the iterative version is usually preferred. You should be able to write the iterative version in about 10 minutes; it's also in last week's notes.
Compared to bubblesort, selectsort performs fewer swaps (what is the worst case?) but an asymptotically similar number of comparisons, and hence is no better.
Insertsort
IDEA: "Start with the empty sorted subarray. Take each element in turn from the unsorted subarray, and insert it in the proper order in the sorted subarray."
You have covered/will cover this thoroughly in lecture, so I won't rehash it here.