Implement Quicksort on a large database.

The file /home/218/database-million.txt contains records for exactly
one million randomly generated people, one person per line. The
individual pieces of information are: social security number, day
of birth, month of birth, year of birth, first name, last name, and
secret code. The items are separated by spaces, and no item ever
contains a space. Here is a small selection from some way into
the file.

      346671424 25 04 1953 Simba VonRichthofen iPSD1jpE
      346672433 02 10 1952 Brent Mozart Bup1v6FX
      346673675 08 06 1974 Alexandra Lamprey YNbEg0Lt
      346674451 17 10 1970 Ezra Osmond 8nenexhH
      346675987 07 08 1997 Nancy Dornier JxoKZszB
      346676332 12 02 1974 Arthropod Tumor PTGS4Ifb
      346677449 18 05 1987 Lillian DeMorgan 7vel34Ds
      346678718 25 08 1959 Terence Silverman 0JVurP0u
      346679758 01 04 1999 Ralph Frampton UXsW6mOz
      346680428 29 05 1990 Betty Osborne sVZdggQ6

Define a struct or class to represent a person, and create an array
or vector of pointers to person object, and fill the array with the
million people from the file.

Then sort them into alphabetical order with your own implementation
of quick-sort. They should be ordered primarily on last name, but when
two last names are the same, break the tie with their first names, if
they are still the same, break the tie with their social security
number. There will be no ties after that.

In order to be able to debug effectively, you will need to start with
a much smaller file. The database file is too big for pico, but Rabbit
has a utility called lines, which can be used to extract a number of
lines from anywhere in a text file:

  To extract the first 20 lines
      lines 1 20 /home/218/database-million.txt
    or
      lines 1 +20 /home/218/database-million.txt
  To extract the middle 20 lines
      lines 499990 500009 /home/218/database-million.txt
    or
      lines 499990 +20 /home/218/database-million.txt
  To extract the last 20 lines
      lines -20 +20 /home/218/database-million.txt
    or
      lines -20 -1 /home/218/database-million.txt

In case it isn't clear, the two numbres are line numbers, the first
line in a file is line 1. A negative number counts backwards from the
end of the file, the last line in a file us line -1. If the second
number begins with a + sign, it is the number of lines wanted.

So by redirecting the output as in

      lines 499990 500009 /home/218/database-million.txt > sample.txt

you create your own file called sample.txt containing just the middle
20 lines from the giant file.

Verify that your sort is correct.

For small sample files, that is easy. For big files you need another
tool.

The file /home/218/sorted-million.txt contains the correctly sorted
database. So make your program create a new file with your sorted
data, perhaps it is called output.txt, and compare them like this:

      diff /home/218/sorted-million.txt output.txt

diff is a standard unix utility that detects any differences between
two files. If the files are identical it says nothing, if they are
not, it lists all the differences.

For a successful exact match you need to take accout of the fact that
social security numbers, days, and months can have leading zeros.
The correct way to print a social security number int is like this:

      cout << setw(9) << setfill('0') << ssn;

Those are single quotes round the zero and you must #include <iomanip>.

Finally, we want to know how fast your sorting is. There is a function
called get_cpu_time() that returns a measure of how much time the
computer spent on your program, the return value is a double and
is measured in seconds. It is only accurate to a few milliseconds, so
for a very small data set it may register no time at all. Call it
once immediately before your sort, and again immediately after. The
difference between the two results is the value you want. Make sure
you only include your sort function's time, not the time it took to
read and write the data. You should be able to sort the million people
in not much more than three seconds.

This is the function:

#include <time.h>
#include <sys/resource.h>

double get_cpu_time()
{ rusage ruse;
  getrusage(RUSAGE_SELF, & ruse);
  return ruse.ru_utime.tv_sec + ruse.ru_utime.tv_usec / 1000000.0 + 
         ruse.ru_stime.tv_sec + ruse.ru_stime.tv_usec / 1000000.0; }

I know that's a long description, but it describes a simple task. It
is not difficult to get quicksort working if you go about it sensibly
and don't drag in anything insane from the internet.