IC210: Sorting and Searching II

Reading

None.

Reinforcement

This lecture is to be used to reinforce the previous lecture on sorting and searching. We'll go over the homework very thoroughly, and try and really internalize the following:

selection sort is generic, which means that the algorithm is the same regardless of what type of objects you're sorting, and what order you want them put into. In fact, you can copy and paste the selection sort code for strings from the previous lecture,
```
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] & the last element
    string temp = A[imax];
    A[imax] = A[length - 1];
    A[length - 1] = temp;
  }
}
```
replace string with whatever type you have in mind, and replace the body of the before function with whatever code you wantin order to define when object a is supposed to "come before" object b.
search is generic, which means that the algorithm is the same regardless of what type of objects you're searching through, and what matching criterion you want to use in order to determine when you've found a match for your query object. In fact, you can copy and paste the search code for strings from the previous lecture,
```
int search(string *A, int N, string x)
{
  int i = 0;
  while(i < N && !match(A[i],x))
    i++;
  return i;
}
```
replace string with whatever type you have in mind, and 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.

Asst Prof Christopher Brown

Last modified: Tue Nov 2 15:14:13 EST 2004