Description: As a senior software engineer, I would like to determine and prove

Question

Description: As a senior software engineer, I would like to determine and prove which sorting algorithm is the most efficient between quick sort, merge sort, and heap sort so that I can recommend it to the development team for inclusion in the code base of an upcoming code optimization project.

Acceptance Criteria:

Well documented, executable C++ source files including classes for each of the aforementioned sorting algorithms. In addition, each sorting algorithm class implementation should be written in its own .cpp file and each class declaration should be written in its own .h file. For example, you should have a class called MergeSort and its implementation should be written in mergeSort.cpp and its declaration should be written in mergeSort.h.

The program should run test cases against each sorting algorithm using arrays of random numbers. The sizes of the arrays are the following: 10, 100, 1000, 10,000 and 100,000.

To insure a fair comparison, the same set of random numbers should be used for each sorting algorithm.

The program should produce the following chart and populate it with the computed results (Note: you do not need to have borders for the table but the output should be tabbed to insure its readability:

Quick Sort

Merge Sort

Heap Sort

Array Size

# of Comparisons

Time to Sort

# of Comparisons

Time to Sort

# of Comparisons

Time to Sort

Time to sort is the amount of time it took to sort the arrays. You should probably use the time.h library. Number (#) of comparisons is the total number of comparisons made to sort the array.

Quick Sort

Merge Sort

Heap Sort

Array Size

# of Comparisons

Time to Sort

# of Comparisons

Time to Sort

# of Comparisons

Time to Sort

10 100 1,000 10,000 100,000

Explanation / Answer

Quicksort. The algorithm is basicaly for random selection sort.It partition the dataset into two similar sized sets. This places one item in final position and then keep the smaller items on ons side and greater items the other.Thus, apart from the log(N) complexity of the algorithm, this method exploits locality quite reasonably. Heapsort. : This algorithm uses a heap to be traversed depending on the characteristics of the data.The heap is touched all-over when the items find their place in the heap and other ithems are pulled up, leading to a poor locality if the heap does not fit in memory. Merge Sort. It is used when several dataitems are already sorted. The locality of the method comes from the fact that each run is traversed sequentially, thus, locality is exploited reasonably. Also, the heap used to sort is R Log(R) size for R being the number of runs to be sorted, which keeps locality reasonably well if the heap fits in memory.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---