CMPT 225 Lecture 9 Simple Sorting Algorithms 1 Last Lecture We saw how to 2 Describe Queue Define public interface of Queue ADT Design and implement Queue ADT using various data structures

Compare and contrast these various implementations using Big O notation Give examples of real-life applications (problems) where we could use Queue to solve the problem Solve problems using Queue ADT Learning Outcomes At the end of the next few lectures, a student will be able to: describe the behaviour of and implement simple sorting algorithms: insertion sort selection sort describe the behaviour of and implement more efficient sorting algorithms:

quick sort merge sort 3 analyze the best, worst, and average case running time (and space) of these sorting algorithms Todays menu Looking at insertion sort selection sort Analyze their best, worst, and average case running time and space efficiency of these sorting algorithms

4 Why Sorting? Definition: Process of placing elements in a particular sort order based on the value of a/some search key(s) Ascending/descending sort order Why sorting? Easier to deal with sorted data: easier to search (e.g. binary search) Common operation but time consuming What can be sorted?

Internal data (data fits in memory) External data (data that must reside on secondary storage) 5 How to sort? Selection Sort 6 How Selection Sort works Array has n elements Starts with element at index 0 and ends with element at index n 1

Until the array is sorted 1.Find (select) the smallest element in the unsorted Sorting done section of array by selecting This is done by comparing 1 element with all n-1 other each element elements 7 2.Swap it with the first element in the unsorted section of array

Demo - Lets have a look at Selection Sort 8 Selection Sort is in place algorithm Space Efficiency Analysis in-place: algorithm does not require additional array(s) Selection sort starts with an unsorted array: As the array is being sorted, the unsorted section decreases and sorted section increases:

9 Time Efficiency Analysis of Selection Sort -1 Unsorted Number of elements n n-1 3

2 1 10 comparisons required to select the one (smallest or largest) n-1 n-2 2 1 0

n(n-1)/2 Time Efficiency Analysis of Selection Sort -2 In total, selection sort Makes n (n 1) / 2 comparisons Performs n 1 swaps Would the way the data is organized affect the number of operations selection sort perform (affect its time efficiency)? 11 For example:

If the data was already sorted (in the desired sort order, e.g., ascending)? If the data was sorted but in the other sort order (e.g., descending)? If the data was unsorted? Summary Selection Algorithm Time efficiency Best case scenario: Average case scenario: Worst case scenario: Space efficiency Best case scenario:

Average case scenario: 12 Worst case scenario: Insertion Sort 13 How Insertion Sort works Array has n elements At the start, insertion sort considers the first cell of array to be already sorted -> sorted section So, it actually starts with element at index 1 and ends with

last element (at index n 1) Until the array is sorted 1. Pick the1st element of the unsorted section and insert it its correct (sorted) place in the sorted section of array Sorting done This is done by comparing the 1st element of the unsorted by inserting section with each element of the sorted section element 2. Shift the elements in sorted section up one position to make space for 1st element of unsorted section of array (if needed) 14 3. Inserts the element in correct position in sorted section

Demo - Lets have a look at Insertion Sort 15 Insertion Sort is in place algorithm Space Efficiency Analysis in-place: algorithm does not require additional array(s) Insertion sort starts with an unsorted array: As the array is being sorted, the unsorted section decreases and sorted section increases:

16 Time Efficiency Analysis of Insertion Sort -1 17 Sorted Elements 1 Worst-case

Comparison Worst-case Shift 1 1 2 2 2

n-1 n-1 n-1 n(n-1)/2

n(n-1)/2 Time Efficiency Analysis of Insertion Sort -2 Time efficiency of insertion sort is affected by the way data is organized in the array to be sorted In the best case scenario, the array is Requires n - 1 comparisons No shift is required 18 Time Efficiency Analysis of Insertion Sort

-3 In the worst case scenario, the array is Every element has to be moved Every element in sorted section of array has to be shifted The outer loop runs n-1 times In the first iteration, one comparison and shift In the last iteration, n-1 comparisons and shifts On average, (n (n-1) / 2 ) / (n-1) = n/2 comparisons and shifts For a total of (n-1) * n/2 comparisons and shifts 19 Time Efficiency Analysis of Insertion Sort -4

What is the average case scenario? If array contains totally unsorted data, insertion sort is usually closer to the worst case scenario 20 Summary Insertion Algorithm Time efficiency Best case scenario: Average case scenario: Worst case scenario: Space efficiency

Best case scenario: Average case scenario: 21 Worst case scenario: Summary Simple Sorting Algorithms Insertion sort Efficient: for small ns More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms Stable: does not change the relative order of elements with equal keys

Both sorts In-place: only requires a constant amount O(1) of additional memory space 22 Learning Check We can now Define the best, worst, and average case running time and space efficiency of insertion sort selection sort Considering the simple sorting algorithms, identify the most efficient one and explain why it is the most

efficient 23 Next Lectures More efficient sorting algorithms 24