CPS 6, Ramm - Spring 2000 - 4/5/00, #30
- Announce
- No Quiz Friday
- Next Homework Assignment
11. Sorting, Templates, and Generic Programming
- Sorting
- "Ideal" Computer Science Topic
- Theory and Practice Meet
- Selection Sort
- Find smallest; swap with element [0]
- Consider rest of list [1], [2], ...; find smallest,
swap with element [1]
- Continue process until you get to end
- Loop Invarient
- What can we say about our partially sorted list that
is true each time around?
- Complexity
- "asymptotic" running time as a function of size
- Develop relationship for Seletion Sort
- Function Overloading
- Different Functions With Same Name
- Parameters Differ by Number
- Parameters Differ by Type
- Combinations
- Must write a (somewhat) different function each time
- Compiler automatically selects correct one
- Consider sort functions to sort vectors of different types
- Function Templates
-
template <class Type>
- One size fits all (almost)
- Similar effect to overloading
- write (and maintain) only one copy
- Compiler does automatic substitution
-
swap2.cpp,
usesort.cpp
- Other Simple Sorts
- Insertion Sort
- Almost used in wordlist problem
- Develop Algorithm
- Bubble Sort (XXX)
- Quicksort
- A pivot element of the vector being sorted is chosen. Elements
of the vector are rearranged so that elements less than or equal to the
pivot are moved before the pivot. Elements greater than the pivot
are moved after the pivot. This is called the partition step.
- Quick sort (recursively) the elements before the pivot.
- Quick sort (recursively) the elements after the pivot.
- The Partition Function
- Desired outcome:
- +-------------------+---+------------------+
- |...elements <= X...| X |...elements > X...+
- +-------------------+---+------------------+
- first...............pivot...............last
- After several iterations:
- +---+------------+-----------+-------------+
- | X |... <= X ...|... > X ...|... ? ? ? ...+
- +---+------------+-----------+-------------+
- first...........p.............k.........last
- All elements processed:
- +---+----------------+---------------------+
- | X |..... <= X .....|........ > X ........|
- +---+----------------+---------------------+
- first...............p...................last
- After swapping 1st element to pivot loc:
- +---+------------+---+---------------------+
- |..... <= X .....| X |........ > X ........|
- +---+------------+---+---------------------+
- first............pivot..................last
- Note Invariant: 2nd diagram true after every iteration
- Looking at the Code
timesort.cpp