CS 15900 Chapter Notes - Chapter 8: Bubble Sort, Insertion Sort, Selection Sort

• School: Purdue University
• Department: Computer Sciences
• Course: CS 15900
• Professor: Alan Bunning

Document Summary

Bubble sort: repeatedly steps through the list, compares each pair of adjacent elements, and swaps them if they"re in the wrong order. **stable, o(1) extra space, o(n^2) comparisons and swaps, adaptive: o(n) when nearly sorted. *algorithm: for i = 1:n, end swapped = false for j = n:i+1, if a[j] < a[j-1], swap a[j,j-1] swapped = true. Invariant: a[1i] in final position break if not swapped. Insertion sort: steps through the list, takes next unsorted element and places it in the appropriate place within the sorted data. **stable, o(1) extra space, o(n^2) comparisons and swaps, adaptive: o(n) time when nearly sorted, very low overhead. *algorithm: for i = 2:n, end for (k = i; k > 1 and a[k] < a[k-1]; k--) swap a[k,k-1] Selection sort: steps through the list, finds the smallest value in the unsorted list and moves it to the sorted list after the previous smallest value.