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