As stated in the chapter, many different factors affect the running time of an a
ID: 3734243 • Letter: A
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.
You should select 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?
Submit a Project containing the Quick Sort Tool program you created to conduct the research
Submit a Project containing the Merge Sort Tool program you created to conduct the research
Submit an Excel Workbook containing the Bench Marking Data
Submit a Report describing your work, your results, and your conclusions.
Explanation / Answer
How sorting algorithms perform in different environments
Four different test cases were run:
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
#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:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.