This lecture is to be used to reinforce the previous lecture on sorting and
searching.
Selection sort is generic
typedef
One way to define your own types in C++ is using the
typedef
keyword. Actually, this doesn't let you really make a new type, but rather give
a name to an existing type.
For example the line
typedef double** matrix;
would define a new type
matrix
, which is a 2D-array of
double
s.
This clearly isn't very exciting, since it's really just a way to define
shortcuts from one typename to another one. But even simple typedefs can be
useful to make code more readable. For example, the prototype of the search
function can be re-written by using typedef:
typedef string DATA;
void selectionsort(DATA *A, int N);
The selection sort is generic. That is, the sorting algorithm is the same:
- regardless of what type of objects you're sorting, and
- regardless of what order you want them put into.
void selectionsort(string *A, int N)
{
for(int length = N; length > 1; length--)
{
// Find imax, the index of the largest
int imax = 0, i;
for(i = 1; i < length; i++)
if (before(A[imax],A[i]))
imax = i;
// Swap A[imax] and the last element
string temp = A[imax];
A[imax] = A[length - 1];
A[length - 1] = temp;
}
}
When you apply the sorting algorithm in a different scenario:
- Define the data type: Replace
string
with whatever type you have in mind.
- Define the order: Replace the body of the
before
function
with whatever code you want in order to define when object a
is
supposed to "come before" object b
.
Search is generic
Search is generic. This that the algorithm is the same
- regardless of what type of objects you're searching through, and
- regardless of what matching criterion you want to use in order to determine when
you've found a match for your query object.
int search(string *A, int N, string x)
{
for(int i = 0; i < N; i++ )
if( match(A[i], x) )
return i;
return N;
}
If you apply the search algorithm in a different scenario:
- Define the data type: Replace
string
with whatever type you have in mind
- Define the order: Replace the body of the
match
function with
whatever code suits your purpose.
Problems
-
Write a program that reads in a list of 3D points
(x,y,z) and prints them out in increasing distance
from the origin. The points should be represented as arrays
of length 3. Here's my solution.
Below is a sample run of the program:
How many points? 3
Enter points (x,y,z): (1,0,1) (1,0,-1.2) (-1,1,-1)
(1,0,1) (1,0,-1.2) (-1,1,-1)
- Try the same thing, but sort by x-values, breaking ties
by y-values, breaking those ties by z-values.
- Try the same thing, but sort in increasing order of
distance from a point given by the user.
-
Write a program that reads in a list of non-negative
integers from the user and sorts them by their last digit.
Numbers with the same last digit should appear smallest to
largest.
So, 678 32 67 102 7 18 would appear as 32 102 7 67 18 678.
- Next, try allowing the user to enter a modulus M
along with the numbers, and sort the numbers according
to their mod M value - smaller mod M values first.
Numbers with the same mod M values should appear
smallest to largest.
-
Write a program that reads in a list of 3D points
(x,y,z), then reads in a point p and a distance d
from the user, and then prints a point from the list that
lies within distance d of point p ... if it exists.
-
Write a program that reads in a list of 2D points
(x,y), then reads in a point p prints a point
from the list that lies in the same quadrant as point p ... if it exists.