首页 > > 详细

辅导 program、讲解 C++编程语言

Data Structure Project 1
Deadline: Apr 28, 23:59

This project requires students to compare five sorting algorithms, which are “Bubble Sort”,
“Insertion Sort”, “Merge Sort”, “Quick Sort”, and “Heap Sort” in the aspect of time
complexity, best&worst case scenario.

Requirement:

1. Implement the five sorting algorithms based on the skeleton code provided.
2. Compare the running time of five sorting algorithms, and fill the following table:

t 3 4 5 6 … 14 15 16 17
Bubble
Insertion
Merge
Quick
Heap

where each cell in the table denotes the running time (recorded by C++ timer) given the
input size (number of elements in the list to be sorted) 2t
. For example, at column “17”,
each soring algorithm should sort the list containing 217
random integers. Note: in order to
be fairness to all the sorting algorithms, the input random integer list should be the same.
3. Use “t” as X-axis and running time (value in each cell in above table) as Y-axis, plot all
the points and sketch the curve (You may do this by Excel) for each sorting
algorithms. Draw all five curves in one X-Y coordinate plane. Compare the five curves
and explain the reason.
4. Describe the best/worst case and the corresponding time complexity of each sorting
algorithm. You may fill the tables below:

Best case
description
Best case example Best case time
complexity
Bubble
Insertion
Merge
Quick
Heap

Worst case
description
Worst case
example
Worst case time
complexity
Bubble
Insertion
Merge
Quick
Heap

联系我们
  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp
热点标签

联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!