## Description

CPE 202 Lab week 6 W22 CompSorts.docx 1

Lab Week 6: Basic Comparison Sorts

A comparison sort is a type of sorting algorithm that compares elements in a list (array, file, etc)

using a comparison operation that determines which of two elements should occur first in the

final sorted list. The operator is almost always a total order:

1. a ≤ a for all a in the set

2. if a ≤ b and b ≤ c then a ≤ c (transitivity)

3. if a ≤ b and b ≤ a then a=b

4. for all a and b, either a ≤ b or b ≤ a // any two items can be compared (makes it a total

order)

In situations where three does not strictly hold then, it is possible that and b are in some way

different and both a ≤ b and b ≤ a; in this case either may come first in the sorted list. In a stable

sort, the input order determines the sorted order in this case.

The following link is helpful.

• Comparison Sorting Visualizations:

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

Your goal for this lab is to implement simple versions of Insertion Sort – insert_sort(alist),

Selection Sort – select_sort(alist), and Merge Sort Sort – merge_sort(alist) that will sort an array

of integers and count the number of comparisons. Each function takes as input a list of

integers, sorts the list counting the comparisons at the same time, and returns the number of

comparisons. After the function completes the “alist” should be sorted.

The worst-case runtime complexity is (n2

) for selection and insertion sort. Why? Write out the

summation that represents the number of comparisons.

Note: There is a fundamental limit on how fast (on average) a comparison sort can be, namely

(n*log n). We will discuss the reasons for this in class.

In addition to submitting your code file (sorts.py) and associated test file (sorts_tests.py) for insert

and selection sorts, fill out and submit a table similar to the table below as well as answers to the

questions below to Canvas. Note: Do not submit Mergesort but be sure you can reproduce the

algorithm and understand it in detail.

Note: The list sizes designated as (observed) should be based on actual runs of your code. The list

sizes designated as (estimated) should be estimates you make based on the behavior of the sorting

algorithm and the times from actual runs with fewer elements.

CPE 202 Fall 2017

February 4, 2022 Lab week 6 W22 CompSorts.docx 2

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? (For part

of the answer, think about what insertion sort does more of compared to selection sort.)