CSC161 2010F, Class 37: Sorting Overview: * Sorting: The Six P's. * Sorting in C. * Some Famous Sorting Algorithms. * Choosing a Sorting Algorithm. Admin: * I did not hear from anyone planning to attend today's rally, so we will hold class as normal. * Expect your next assignment late tonight or early tomorrow. * EC for Singers Concert at 2pm on Sunday. * EC for FreeNet meeting at 4pm on Sunday. * EC Cool Damani Phillips concert tonight in S-L! 7:30 * Belly Dance at 3pm on Sunday (no EC) * EC if you attend all of the Twenty-four hour improv in Younker Lounge 8pm tonight to 8pm Saturday (you must be awake for at least 20 hours of it) * Reading for Mondaya Sorting: * Given an array of values, rearrange the array so that the elements are organized from smallest to largest (or largest to smallest). Procedure: sort Parameters: a, a homogeneous array size, an int comparator, a function that lets us compare values Purpose: Rearrange the array so that the elements are organized from smallest to largest Produces: [Nothing; Called for the side effect] Preconditions: size >= 0 The array contains at least size elements Comparator can be applied to any two elements in a A = a Postconditions: For all 0 <= i < size-1, comparator indicates that a[i] is less than a[i+1] a at the end is a permutation of the original No values were added or removed. A is unmodified a is a permutation of A So, how do we express this in C? * We don't yet know how to pass a function as a parameter * We don't yet know how to say "a homogeneous array of an unknown type" So, we might just write separate sort routines for each type * How do we write a generic sort routine that will work for many types? int a[] char a[] char *a[] Two strategies for C programmers who want to write somewhat type-independent code. * Macros #define SORTER(TYPE, COMPARE) void sort (TYPE a[], int size) \ { \ if (COMPARE(a[i],a[i+1]) \ ... } * The wonders of #include #define TYPE int #define COMPARE(x,y) x < y #include sort.c sort.c TYPE TYPE_sort (TYPE a[], int size) { ... } double a[] Sorting Algorithms * Bubble Sort - One round: Compare neighboring elements and swap out-of-order elements. In each round, the largest remaining element "bubbles" to the end. * Selection sort - Take the largest remaining element and swap to the end of the unsorted section. * Why use this instead of bubble sort? * Fewer swaps! * Insertion sort - Two parts of the array: Unsorted part and sorted part. One round: Take one element of the unsorted part and insert it into the appropriate place in the sorted part * Merge sort - Split into two halves, sort the two halves, and merge back together * Shell sort - We're not quite sure how it works, but it seems to Like insertion sort, but does the insertion using bit "steps" * Quicksort Divide into small and large elements and recurse on the two halves. * Pick the "pivot" randomly