Week 13

Quiz

Review

·        Searching

o       Linear

o       Binary

o       Hash

§         linear

§         Second hash

§         Chained

Sorting

·        Have them each think about how they would sort an array of integers

o       Put design on the board

·        Selection sort

o       Go through the entire array and put the min in the first location

o       Loop through the array  to find the min

o       Show example on board

o       O(n²) – for best, average, and worst cases

·        Sorting test cases

o       Already sorted

o       Sorted in reverse order

o       Empty array

o       Array of one element

·        Insertion sort

o       Concept – build up a new list, taking items off the original list and inserting them in order in the new list

o       Draw concept on the board

o       Can do this with one array.  Just start with the [0] sorted by definition and grow it.

o       Go through the array 0-n making 0-i sorted.

§         For each item taken, need to shift all the elements in the array up to the point where this one is to be inserted

o       Go through example on the board

o       O(n²) – for average, and worst cases

o       O(n) if already sorted, and still good if nearly sorted

·        Bubble sort (my favorite)

o       Go through list doing pairwise comparisions and swapping order if necessary

o       At the end of one pass the largest (smallest) is at the bottom (top)

o       Now go through the list, only don’t need to look at last item.

o       Go through the list n-1 times this way

o       O(n²) – for worst, average, best case

o       can do better with small change – do they know what it is?

§         set a flag, if don’t do any swaps in a pass, then done sorting

§         makes best case O(n) !

·        Recursive sorting algorithms

·        Merge sort (divide and conquer)

o       Break original list in two, sort each and then merge into one list

o       Merge into one list by comparing head of each of the lists and moving the min to a new, temp list

o       Put example on board

o       P. 585, 590

o       O(nlogn) for best, worst, average cases

·        Quicksort

o       Like mergesort but partitions list and moves everything greater than the pivot point to one end and everything larger to the other end, not just break in half

o          O(n²) worst case, O(n logn) best and average cases

·        Heapsort

o       Builds a heap

in class work on game project