CSC151 2010S, Class 47: Introduction to Sorting Overview: * The problem of sorting. * Writing sorting algorithms. * Examples: Insertion, selection, etc. * Formalizing the problem. Admin: * Reminder: One more day to register for classes! * Reading for Friday: Sorting. * I will not be in class on Friday Prof. Weinman and a guest will be here. * Note: I do plan to release tentative grades and such during week 14 * EC for Osgood convocation tomorrow. * Warning, it's a PBK convo! * EC for Friday's CS Extra Table (Science 3821). I need a headcount! 3 Sorting: * Given a collection of values Criterion for ordering pairs of values * Goal: Put them in order from smallest to largest according to the criterion E.g., a collection of students * Order them by grade (from least to most or vice versa) * By name (alphabetically) * By class year * By mailbox number (or zip code or ...) Technique one: Insertion Sort * Two groups of people: * Those we haven't processsed yet * Those who are already in order * Repeatedly grab one unprocessed person * Compare that person to each of the people in the ordered list * If that person precedes the next person stop * Otherwise, move on to the next person Technique two: Insertion Sort with Binary Search * Two groups of people * Unprocessed * Sorted * Repeatedly grab one unprocessed person * Find the appropriate place for that person using binary search Technique three: Selection Sort * Repeatedly * Find the "largest" element of the group * Remove it and put to the side Technique threeD: Selection Sort from both ends Technique four: Bubble Sort * Repeatedly swap things that are out of order * Never use bubble sort!