Sorting Contest - Prog 3

Sorting Contest - Prog 3
CECS 325 – System Programming with C++


So you think you are faster than Linux? 

This is your chance to prove it. Linux has a sort command. If you wanted to use the linux sort command to sort all the items in a file called “numbers.txt”, you could use it like this:

% sort numbers.txt         This command treats the contents of the file like text    
% sort -n numbers.txt         this command treats the contents of the file like numbers

You could also sort the file like this:

    % cat numbers.txt | sort
    % more numbers.txt | sort

You could sort the first or last 1000 numbers like this:

    % head -1000 numbers.txt | sort     sort the first 1000 lines
    % tail -1000 numbers.txt | sort     sort the last 1000 lines

Each of the above commands will display the sorted numbers (lines) on the screen. Instead of displaying the numbers, you could write them to a file called “sorted.txt”

    % cat numbers.txt | sort > sorted.txt
    % sort -n numbers.txt > sorted.txt

In this assignment you will generate a file that has 1 million six-digit numbers between 100000 and 999999. Write these numbers to a file called “numbers.txt”. Then run this linux command to see how long it takes to sort 1 million integers:

    % time sort numbers.txt  > sorted.txt

Here’s how fast it took on my computer:
 

Your job is to write a sort function in C++ that will sort 1 million numbers as fast as you can. If you can beat the linux time, you are truly amazing.

I am providing some files to help you:
•    generate.cpp
o    Purpose: generate a file called numbers.txt
o    Description: The numbers.txt file will have COUNT random numbers between MIN and MAX
o    Usage: generate COUNT MIN MAX
o    Example: generate 1000000 100000 999999
•    mySortA.cpp
o    Purpose: sort numbers from numbers.txt, output to sortedA.txt
o    Description: Uses bubble sort on an array of integers
o    Observation – this is slow, but faster that a vector
•    mySortV.cpp
o    Purpose: sort numbers from numbers.txt, output to sortedV.txt
o    Description: Uses bubble sort on a vector of integers
o    Observation – this is slow, slower than using an array
o    
•    sortRace.bat
o    Purpose: batch file to control the race

I ran several examples to get a feel for how the bubble sort would perform. Here are screenshots of my findings:


This screenshot shows how long the bubble sort took to sort 1 million items. I was using a vector here so you can assume an array would be faster. Notice that this is over 8,000 times slower than the linux version. 

 

 
This screenshot shows the output of the sortRace.bat batch file. I generated only 100,000 integers (instead of 1 million) and the results are shown below. Linux sort is much, much faster than the bubble sort and using an array is more than twice as fast as using a vector. Notice the Array version is about 350 times slower than the linux version

 



Your assignment: write a sort function that will sort 1 million integers in a reasonable time. Linux does this task in less than 2 seconds. Can you do it in less than a minute?

What to submit:
•    Your sorting program (source code only). Call it mySort.cpp
•    Screenshot showing the output of the sortRace.bat file