Selection sort is generic

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.
Applying the sorting algorithm in a different scenario
  1. Copy and past the code on the right.
  2. Replace data_type with whatever type you have in mind.
  3. Define the before function as follows:
    • before(a,b) should return true if and only if object a should "come before" object b.

  

bool before(data_type a, data_type b);

void selection_sort(data_type* A, int n) {
  for (int i = 0; i < n - 1; ++i) {
    // find nexti, the index of the next element
    int nexti = i;
    for (int j = i + 1; j < n; ++j) {
      if (before(A[j], A[nexti])) {
        nexti = j;
      }
    }
    // swap A[i] and A[nexti]
    data_type temp = A[i];
    A[i] = A[nexti];
    A[nexti] = temp;
  }
}

Sorting 2D-arrays

Write a program that reads in a list of 3D points (x,y,z) and prints them out in increasing distance from the origin. Each 3D-point should be represented as an array of size 3. Below is a sample run of the program: 
How many points? 5
Enter points (x,y,z): 
(3.6, 0.0, -2.1)
(1.1, -1.1, -1.1)
(3.0, 0.0, 0.0)
(-2.6, -1.8, 2.7)
(3.0, 0.5, 0.5)
(1.1,-1.1,-1.1) 
(3,0,0) 
(3,0.5,0.5) 
(-2.6,-1.8,2.7) 
(3.6,0,-2.1)

Q: What should be data_type in this case? 

 double* -- each object is a 3D point (an array of size 3)

Here's a solution. Hopefully you see that this doesn't require too many changes to the above program.

 

Swapping pointers

One key thing to see however, is what swap does when a and b are pointers. Hopefully the above picture will give you an idea:

Chaining pointers means changing arrow destinations!

More practice problem

Search is generic

Search is generic. That is, 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:

Practice Problems (Sorting)

  1. Receive 3D points as in the above. Sort in increasing order of distance from a point given by the user.
  2. Write a program that reads in a list of 10 names (first name followed by last name) from the file names.txt and prints them out in the usual order - i.e. alphabetically by last name, using first names to break ties. Note: You'll want to represent a person's name as an array of length 2.
    Here's a solution

Practice Problems (Searching)

  1. Write a program that reads in a list of 10 names (first name followed by last name) from the file names.txt, then repeatedly queries the user for a first name and prints out all names with first-name matching the query value. A run of the program might look like this: 
    ~/$ ./prog
Name (or quit): John
John Adams
John Tyler
Name (or quit): James
James Madison
James Monroe
Name (or quit): Steve
Name (or quit): George
George Washington
Name (or quit): quit
    Here's a solution
  2. 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.
  3. 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.