Reference no: EM132829941
In this practice, we will be implementing a the several sorting algorithms discussed in the class and experimenting with the runtime for these sorting algorithms. You are required to use python. For help you can use the lecture slides.
Task:
1. Implement the insertion sort algorithm in python
2. Implement the merge sort algorithm in python
3. Implement the counting sort algorithm in python
4. Compare the time for these implementations for the following cases. The code for recording the runtime is provided below.
Case A: Input to the sort algorithm is a sorted list (ascending order)
Case B: Input to the sort algorithm is a sorted list (ascending order)
Also vary the size of the input list for your experimentation: 1. 10,000
2. 100,000
3. 1000,000
[Note: There are 6 possible cases to run for each algorithm.]
For each run take three readings and populate the table in the next page.
5. Report your findings.
Recording the runtime:
To determine the sorting time, replace line 3 with appropriate function name.
1. import time # Doc available
2. t = time.process_time()
3. a = my_insertion_sort(n)
4. elapsed_time = time.process_time() - t
5. print(elapsed_time) # Note down this time in the table
|
Sorting Algorithm
|
Case
|
Reading
|
10,000
|
Avg
|
100,000
|
Avg
|
1,000,000
|
Avg
|
|
Insertion Sort
|
A
|
1
|
|
|
|
|
|
|
|
A
|
2
|
|
|
|
|
A
|
3
|
|
|
|
|
B
|
1
|
|
|
|
|
B
|
2
|
|
|
|
|
B
|
3
|
|
|
|
|
Merge Sort
|
A
|
1
|
|
|
|
|
|
|
|
A
|
2
|
|
|
|
|
A
|
3
|
|
|
|
|
B
|
1
|
|
|
|
|
|
|
|
B
|
2
|
|
|
|
|
B
|
3
|
|
|
|
|
Counting Sort
|
A
|
1
|
|
|
|
|
|
|
|
A
|
2
|
|
|
|
|
A
|
3
|
|
|
|
|
B
|
1
|
|
|
|
|
|
|
|
B
|
2
|
|
|
|
|
B
|
3
|
|
|
|
Note: It is expected that in some cases the sorting can take significantly long (in range of hours).
Attachment:- Algorithm Task.rar