Sorting and Searching 2

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 doubles.

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:

void selectionsort(string *A, int N) {
  for( int length = N; length > 1; length-- ) {   
    // Find imax, the index of the largest
    int imax = 0;
    for( int i = 1; i < length; i++ )
      if( before(A[imax],A[i]) )
        imax = i;

    // Swap A[imax] and the last element
    swap(A[imax], A[length-1]);
  }
}

When you apply the sorting algorithm in a different scenario:

Search is generic

Search is generic. This that the algorithm is the same

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:

Problems

  1. 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) 
    	    

  2. 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.
  3. 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.
  4. 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.