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