CPS 6, Ramm - Summer Semester I - 6/21/99 #21
Chap 11. Sorting, Algorithms, & Matrices
- 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.cc,
usesort.cc
Overview of Assignment 7
- Introduction
- Bit-mapped Graphics & Matrices
- pixels
- P1 b&w, P2 gray-scale
- Compression
- C1, Run-length Encoding
- xv, xpaint
- space requirements
- Specific Processing Operations
- Read C1
- Compress
- Invert
- Reflect
- Expand
- Optional Operations
- Blob Count
- Enhance
- Grey-scale Compression
Chap 11. Sorting, Algorithms, & Matrices
- 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.cc
- More on Assignment #7 Blob Count
- Possible Iterative Approaches
- Easy to make mistakes
- Consider using recursion
- Much easier to program
- Example Recursive Solution to Fill Problem
- (Should give you hint as to how to approach blob count)
- Use character plot
- 0 represents space
- 1 represents figure boundary
- larger numbers represent colors
-
fillplot.cc
- Recursive Specifics of Fill
- Routine does nothing (no recursive call) if:
- Hit boundaries of graph
- Hit boundaries of figure
- Hit point already colored
- Color current point [r][c]
- Call Fill (recursively) for:
- Each of eight neighboring points
-
[r-1][c-1] [r-1][ c ] [r-1][c+1]
-
[ r ][c-1] - - - - - -[ r ][c+1]
-
[r+1][c-1] [r+1][ c ] [r+1][c+1]