Program of sorting algorithms , C/C++ Programming

Assignment Help:

The program sorting.cpp contains a main function for testing the operation of several sort algorithms over various data sizes and data set organisations. The program understands the following options:

-i insertion sort

-s selection sort (the default)

-q quicksort

-a (almost) sorted data set

-v reverse-sorted data set

-r random data set (the default)

n generate a data set of size n (default 10000)

Background

In part 3 you will need to gather information about the number of times that various parts of the code is executed. On Unix-based systems (including Linux and cygwin), the simplest approach is to use execution profiling tools. To gather profiling data, first compile the program with the -pg option, which will cause it to write information about its execution into a file (called gmon.out).

Then each time you run the program, you can use the profile analysis tool (gprof) to report on the execution counts of each called function.

g++ -pg -o sort sort.cpp

./sort // run with default arguments

gprof -b // -b means "brief" output

./sort -qr 1000000 // quicksort on one million random values

gprof -b // profile for second run

...

If the system that you're using doesn't support profiling, a work around is to add code to the program to increment a counter at each point of interest, then print the values of the counters at the end of execution.

Selection Sort

1. Implement the selectionSort and insertionSort functions. The program checks that the final list is sorted correctly, so you can test your code using try with task  sorting.

Quicksort

2. Implement the quickSort function. The real work of quicksort happens in the partition operation, so it's probably best to define a separate function to do the partitioning.

 Profiling

3. Gather data about the number of times that the innermost loops of each sort algorithm is executed. A simple way to count inner loop executions is to call a "do nothing" function from the inner loop, then look for the execution count of that function in the profiler output.

void inner() {} // for gprof to count

void ...Sort() {

for (...) {

for (...) {

...

inner();

}

}

}

When you have profiling working to your liking, run the program and record the inner loop counts for each combination of algorithm (-i, -s, and -q) and data organisation (-a, -v, and -r), beginning with a data size of 1000 and increasing progressively until execution takes around 30 seconds. A suitable set of size increments would be 1000, 2000, 5000, 10000, 20000 and so on.

For each run, compute a normalised execution count by dividing the actual count by the data set size. For example, if quicksort with a random data set containing 10,000 elements executed its inner loop 161,619 times, then the normalised execution count would be 161610/10000, or about 16.1

Finally, plot the 9 sets of data (for the options -ia, -iv, -ir, -sa, -sv, -sr, -qa, -qv, and -qr) as separate lines on a single set of axes, with data set size on the horizontal axis and normalised execution count on the vertical axis. You'll need to choose scales so that the full range of values can be displayed, and label the lines so you know which one is which. You may also find it worthwhile using a log-log plot to better show the values over the full range.

Improving Quicksort

4. A simple implementation of quicksort is likely to perform badly for certain data sets. For example, the implementation used as an example in lectures performs very poorly if the data set is in reverse-sorted order.

The poor performance can be avoided by choosing a better pivot for the partitioning step.

Common strategies include selecting a random element or finding the median of the first, middle, and last elements. In any case, the chosen pivot is swapped with the last element before proceeding to do the partition as before.

Read about and implement one of the improvements to quicksort and show (by adding its profile data to the graph of part 3) how much improvement you have achieved.


Related Discussions:- Program of sorting algorithms

Program Assignment #3, Programming Assignment #3: Vehicle Track Performance...

Programming Assignment #3: Vehicle Track Performance Tests Purpose: The purpose of this programming assignment is to give the student experience in using functions, arrays, and str

Operators and their expression in cpp, Operators in C++: All C operator...

Operators in C++: All C operators are valid operators in C++ also.  Besides C++ has developed some new operators like Operators and their Expression: 1.      Logical op

C++ and matlab, ">http://www.ee.nmt.edu/~erives/289_F12/EE289_Takehome_2.p...

">http://www.ee.nmt.edu/~erives/289_F12/EE289_Takehome_2.pdf http://www.ee.nmt.edu/~erives/289_F12/Takehome2_maze.GIF

Computer, Is computer an intelligent machine?

Is computer an intelligent machine?

What is the issue which auto_ptr objects address?, A: If you employ auto_pt...

A: If you employ auto_ptr objects you would not need to be concerned along with heap objects not being deleted even if the exception is thrown.

Loop, wap to count the numof string present in a word

wap to count the numof string present in a word

Introduction of computer and programming concept, Classify computer system ...

Classify computer system according to capacity. How they are different from computers according to the classification of technology. Provide comparative study also.

Define auto pointer?, A: The simplest instance of a smart pointer is auto_p...

A: The simplest instance of a smart pointer is auto_ptr that is included in the standard C++ library. Auto Pointer only takes care of Memory leak & does nothing regarding dangling

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd