Question

As stated in the chapter, many different factors affect the running time of an algorithm. Your task is to conduct experiments to see how sorting algorithms perform in different environments.

To construct this experiment you must have a program or two programs that sorts sets of data. The program or programs should sort a set of number using a quick sort and using a merge sort. To expedite this, example code that performs a quick sort and a merge sort have been provided.

You should conduct sets of experiments. Categorize your data in two major sections, one for merge sort results, one for quick sort results. Each section can be sub divided into criteria that you used to bench mark the sort.

Conduct benchmarking of quicksort and merge sort several times on the same system - once with as much software turned off a possible, and then with other programs running - Word, Excel, videos, etc. See if you can determine how different software or combinations of software running at the same time slow down the sorting algorithms the most. You might want to include an Internet connection in this test. Just as with the different software, How does a live connection to a network affect the running time of the algorithms?

Use Data Sets Starting at at 10,000,000 randomly generated numbers

All programming projects must have an associated Professional Lab Report submitted with in. A Lab Report must contain the minimum Requirements List Below

Template Workbook for Bench Marking Data

benchmarking.xlsx

Document Formatting

A document header - The Header section should contain your name

A document footer - The footer should contain a page number

Paragraphs Formatting should be formatted

1.5 line spacing

12 points before and after the paragraph

Character Formatting

Body Text should be 12 points

Segment Headers should be boldface

Submit a Project containing the Quick Sort Tool program you created to conduct the research. If the project contains the features of both programs, then only submit one project.

Submit a Project containing the Merge Sort Tool program you created to conduct the research. If the project contains the features of both programs, then only submit one project.

Submit an Excel Workbook containing the Bench Marking Data.

Submit a Lab Report for building your project tool.

Submit an Essay Report describing your work, your results, and your conclusions.Essays should follow the same formatting requirements as Lab Reports

Answer 1

Answer :

How sorting algorithms perform in different environments

Four different test cases were run:

Items are 32-bit integers. These are both very fast to compare and copy.
Also 32-bit integers, but with a high number of repetitions. Each value in the array repeats approximately 100 times in average.
Items are C++ strings with identical beginnings. Strings of 50 characters were used for the test. This tests the case where copying is fast but comparison is slow.
Items are arrays of integers. Arrays of 50 integers were used. Only the first integer was used for the comparison. This tests the case where comparison is fast but copying is slow.
More detailed info for these test cases is given in their individual pages.

I tried to implement the program so that it first counts how much time is spent generating the data to be sorted, and then this time is subtracted from the total time. While it's not possible to do this in a very exact way, I'm confident that the results are close enough to reality.

Each test case with each sorting algorithm was run several times, every time with different random data.

This was done to average out individual worst cases.

Quick sort

It is the most popular sorting algorithm. Its virtue is that it sorts in-place and that it usually is very fast
The main problem with quicksort is that it's not trustworthy: Its worse-case scenario is O(n2) and the pathological cases tend to appear too unexpectedly and without warning, even if an optimized version of quicksort is used.
Implementation:
#ifndef QUICK_SORT_HH
#define QUICK_SORT_HH

#include "InsertionSort.hh"

#include <algorithm>

template<typename ItemType>

unsigned Partition(ItemType* array, unsigned f, unsigned l, ItemType pivot)

{

unsigned i = f-1, j = l+1;

while(true)

{

while(pivot < array[--j]);

while(array[++i] < pivot);

if(i<j)

{

ItemType tmp = array[i];

array[i] = array[j];

array[j] = tmp;

}

else

return j;

}

}

template<typename ItemType>

void QuickSortImpl(ItemType* array, unsigned f, unsigned l)

{

while(f < l)

{

unsigned m = Partition(array, f, l, array[f]);

QuickSortImpl(array, f, m);

f = m+1;

}

}

template<typename ItemType>

void QuickSort(ItemType* array, unsigned size)

{

QuickSortImpl(array, 0, size-1);

}

template<typename ItemType>

void MedianHybridQuickSortImpl(ItemType* array, unsigned f, unsigned l)

{

while(f+16 < l)

{

ItemType v1 = array[f], v2 = array[l], v3 = array[(f+l)/2];

ItemType median =

v1 < v2 ?

( v3 < v1 ? v1 : std::min(v2, v3)

) :

( v3 < v2 ? v2 : std::min(v1, v3)

);

unsigned m = Partition(array, f, l, median);

MedianHybridQuickSortImpl(array, f, m);

f = m+1;

}

}

template<typename ItemType>

void MedianHybridQuickSort(ItemType* array, unsigned size)

{

MedianHybridQuickSortImpl(array, 0, size-1);

InsertionSort(array, size);

}

#endif

Merge Sort:

The virtue of merge sort is that it's a truely O(nlogn) algorithm and that it's stable.

Its main problem is that it requires a second array with the same size as the array to be sorted, thus doubling the memory requirements.

In this test I helped merge sort a bit by giving it the second array as parameter so that it wouldn't have to allocate and deallocate it each time it was called.

Also, instead of doing the basic "merge to the second array, copy the second array to the main array" procedure like the basic algorithm description suggests, I simply merged from one array to the other alternatively.

Implementation:

#ifndef MERGE_SORT_HH
#define MERGE_SORT_HH
template<typename ItemType>
void MergeSort(ItemType* array, ItemType* helpArray, unsigned size)
{
ItemType* src = array;
ItemType* dst = helpArray;

for(unsigned bSize = 2; bSize < size*2; bSize *= 2)
{
unsigned dstInd = 0;
for(unsigned bInd = 0; bInd < size; bInd += bSize)
{
unsigned sbInd1 = bInd, sbInd1e = bInd+bSize/2;
if(sbInd1e > size) sbInd1e = size;
unsigned sbInd2 = sbInd1e, sbInd2e = bInd+bSize;
if(sbInd2e > size) sbInd2e = size;
while(sbInd1 < sbInd1e && sbInd2 < sbInd2e)
{
if(src[sbInd1] < src[sbInd2])
dst[dstInd++] = src[sbInd1++];
else
dst[dstInd++] = src[sbInd2++];
}
while(sbInd1 < sbInd1e) dst[dstInd++] = src[sbInd1++];
while(sbInd2 < sbInd2e) dst[dstInd++] = src[sbInd2++];
}
ItemType* tmp = src; src = dst; dst = tmp;
}
if(src == helpArray)
{
for(unsigned i = 0; i < size; ++i)
dst[i] = src[i];
}
}
#endif

I hope this answer is helpful to you, please upvote my answer. I'm in need of it.. Thank you..