CMPT 225 - Simon Fraser University

CMPT 225 - Simon Fraser University

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

Recently Viewed Presentations

  • National Policy - Ms. Scioli's Site

    National Policy - Ms. Scioli's Site

    National Security Policy. The Backstory. Background - employer -based benefits. Pros. cons. Truman - 1. st. proposal for a universal system, failed. Decline of pensions / benefits with manufacturing sector decline / decline of unions.
  • Assessing for College and Career Readiness:

    Assessing for College and Career Readiness:

    - Marzano (2009) DQ1. Element 1. Clear Learning Goals. There are no high-yield strategies; there are only high-probability strategies. - Marzano & Haystead (2009) Developing Effective Goals. How can a teacher write a goal for all students that satisfies the...
  • Bioethical Perspectives on Autonomy, Privacy, & Confidentiality

    Bioethical Perspectives on Autonomy, Privacy, & Confidentiality

    Definition from Institute of Medicine: PAHO Brown Bag Lunch 11/27/12 "[The] concept of privacy is also context specific, and acquires a different meaning depending on the stated reasons for the information being gathered, the intentions of the parties involved, as...
  • Parents meeting (U) Runion des parents (U) October/octobre

    Parents meeting (U) Runion des parents (U) October/octobre

    New Start hut for Edelweiss, built by Algonquin College students (coordinated by Matt Wheatley); Inauguration of new Strief Timing Hut; New timing wiring. Working on SL homologation for Strief. Preliminary schedule has 5 events at Edelweiss: U16 SL Championships (Strief)...
  • Rime of the Ancient Mariner Part III

    Rime of the Ancient Mariner Part III

    Structure of the Poem The poem is written as a ballad. The poem is written in stanza form. The poem also has a rhyme scheme: a b b a c d d c… "Poetry Analysis: The Rime of the Ancient...
  • Nitrogen Cycle - Penn State York

    Nitrogen Cycle - Penn State York

    Arial Default Design Nitrogen Cycle Nitrogen Facts Slide 3 Slide 4 Nitrification α-Proteobacteria β-Proteobacteria γ-Proteobacteria Slide 9 Anaerobic Ammonium Oxidation NH4+ + NO2- → N2O + H2O +2H+ Phylum: Planctomycetes Denitrification Sediment or Hypereutrophic Lake Nitrogen Cycling Profiles N2-Fixation Rhizobium-Legume...
  • Overview of the Spanish Civil War - Social Studies @ LSL

    Overview of the Spanish Civil War - Social Studies @ LSL

    Franco-British Arm embargo: This was an agreement drawn up by France and Britain in August of 1936. 27 countries signed it, including Italy, Germany, and the U.S.S.R, all of which did not keep their promise to stay out. The Abraham...
  • Transportation Disadvantaged Taskforce AUGUST 2, 2017 DANIELLE MCGILL

    Transportation Disadvantaged Taskforce AUGUST 2, 2017 DANIELLE MCGILL

    Presentation at the Transportation Disadvantaged Legislative Day in Tallahassee, March 2018. Presentation at the SARTAC National Self Advocacy Conference May 2018. My Goal: To share my personal insight, from a rider's perspective about my daily challenges and encourage other riders...