Quicksort
Quicksort Video Overview The purpose of this lab is to investigate the quicksort algorithm. File Descriptions vt100ansi.h - This header file allows colors to be printed to the screen using the macro vtprintf(COLOR) where COLOR is one of the colors defined in the file. quicksort.cpp - This defines the quicksort algorithm using median-of-three pivots. This version of quicksort puts the pivot in the first slot, instead of the last slot as discussed in class. Both approaches are valid. The code will call insertion sort when the number of elements is less than the defined THRESHOLD value. You can run quicksort in debug mode by defining DEBUG_MODE at the top of the file. In debug mode, information about choosing the pivot, making the swaps and doing insertion sort are printed to the screen. Since there is a lot of information, SLEEP_USEC defines how long the debug mode pauses between stages so that the information can be read. You can turn this pausing off by defining SLEEP_USEC as 0 at the top of the file. input1 input2 input3 Misc. Notes This works best if you are using a color terminal with scrollback capacity. If you are using your laptop instead of the machines in 240, make sure that your terminal supports VT100 ANSI colors. Putty for Windows should work, as should the Mac OS X terminal. The pausing code may behave oddly if you try to download it and compile it on Windows (even though there is a workaround in the code, Windows does poorly with this sort of task), so make sure to log onto Sleipnir and try the code there. Assignment In main(), open one of the provided input files take the input filename as a command line argument. Read all of the numbers from the file into an array and pass that array to the quicksort function. you could look at your dynamic memory lab 8? for an example of reading values from a file Use 0 for the starting index and count-1 for the ending index (this means you need to make sure to keep track of the count of numbers you read off the file). Once you have made your main.cpp file, compile the program and test the code with different sets of input you can test yours versus the examples by passing in the name of the sample files after the name of the executable ./example input1 versus ./runme input1