Lab 6 : Sorting Algorithms

Lab 6 : Sorting Algorithms
Sorting Algorithm Comparisons on Sorted and not Sorted List
In this assignment you will work with between one and two of your classmates, and compare
up to six different sorting algorithms. I will assign you to a group of 2 or 3 students unless you
want to find your partners on your own. If you want to find your partners on your own,
please let me know soon.
Review the lecture slides and the textbook and write six functions that use six sorting algorithms
(bubble sort, selection sort, insertion sort, quicksort, merge sort, and heap sort). (Before doing
any comparison make sure, your code works!) Distribute the work evenly among your team
members: Each of you should write at least one of the O(n log n) sorting algorithms:
quicksort, merge sort, and heap sort. If you are in a group of two students, you can omit
the heap sort and bubble sort. Put the name of the author in the docstring of each function so
that we know who implemented the function (to determine who has slacked off in case that
indeed happens).
(Note: You are testing these sorting algorithms on integer numbers)
Comparison Sorting Visualizations link can help you to have some perspective on sort
comparison: https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
Create a python file as comparison_sort.py, write your functions for sorting sorted and unsorted list
in this file. Your goal for this lab is to implement simple versions of Bubble Sort - bubble_sort(alist),
Insertion Sort - insertion_sort(alist), Selection Sort - selection_sort(alist), Merge Sort -
merge_sort(alist), Quick Sort - quick_sort(alist), and heap sort - heap_sort(alist) that will sort an array
of integers and count the number of comparisons. Each function takes a list of integers as input,
sorts the list, counts the number of comparisons at the same time, and returns the number of
comparisons. After the function completes, the “alist” should be sorted. You can add helper functions
as needed.
Do not do any improvement in the sort algorithms, which can cause reducing the number
of comparisons. Use the version of algorithms presented in the lecture. For the quicksort,
you can choose either one of the two versions presented in the lecture. Make sure you are
using the same list for all sort algorithms.
The runtime complexity is O(n
2
) for selection and insertion sort; and O(n*log(n)) for merge and quick
sort, Why? You will submit your answers and results of your code in a pdf file. Write out the summation
1
CPE202 Spring 2020
that represents the number of comparisons. Note that you will need to run test cases of different sizes to
show that Bubble, Insertion and Selection sorts are O(n
2
) and Merge, Quick, and Heap sorts are
O(n*log(n)). To do this, plot the number of comparisons (y-axis) vs. the size of the list (x-axis). Since
the plot is shaped like a parabola for selection and insertion sort this indicates that it is quadratic. In the
pdf file, for each sort, submit a table showing list size and number of comparisons from your test cases
and a plot of that data.
Time the runtime of Python sort( ) function for a given list. Python uses Timsort algorithm (it is a
hybrid sort that derived from merge and insertion sort algorithms with runtime complexity of O(n) in best
case and O(n*log n) in average and worst cases. (just use alist.sort() in your code and set the start and end
time). The source code of the Timsort can be viewed here.
For generating the list you can create a list of random numbers.
import random
random.seed(1) #in order to generate the same sequence of numbers each time.
alist = random.sample(range(10000),10)
,which produces a list of 10 random number between 1 and 10000 [5445, 8692, 6915,
8637, 4848, 9408, 1744, 171, 4315, 2949]
For timing, you can use time class of Python
1. import time
2. start_time = time.time()
3. #Now call sort function
4. end_time = time.time()
5. sort_time = end_time – start_time
Submission:
Zip the following two files into one, and name the zip file as <calpoly_username_lab6.zip. Replace
<calpoly_username with your cal poly username. Only one of your group members needs to
submit the file. But make sure to include the names of all members in your team on every file
you submit.
1) comparison_sort.py 2) Comparison_analysis.pdf
The pdf file must include:
2
CPE202 Spring 2020
1) Two tables for each sort algorithm.
2) Answer to the questions in the last page
3) Plot the number of comparisons (y-axis) vs. the size of the list (x-axis). Since the plot is shaped
like a parabola for selection and insertion sort this indicates that it is
quadratic. It may take several hours (4 ~ 9 hours) for some sorting algorithms
to complete sorting 500,000 items. Therefore, you may want to do this
experiment at night while you are sleeping. If it is taking more than 8 hours to
complete sorting, you can stop it, and you can estimate the execution time and
the number of comparisons instead.
Algorithm Name: Type of list (sorted or unsorted):
List Size Comparisons Time (seconds)
1,000 (observed)
2,000 (observed)
4,000 (observed)
8,000 (observed)
16,000 (observed)
32,000 (observed)
100,000 (observed)
500,000 (observed)
Answer the following
questions:
1. Which sort do you think is better? Why?
2. Which sort is better when sorting a list that is already sorted (or mostly sorted)? Why?
3. You probably found that insertion sort had about half as many comparisons as selection
sort. Why? Why are the times for insertion sort not half what they are for selection sort?
3