Sale!

Sorting Contest – Prog 3

Original price was: $35.00.Current price is: $30.00.

5/5 - (2 votes)

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:
Internal
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.
Internal
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

Scroll to Top