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

  • Explicitação e Simplificação na tradução de termos simples ...

    Explicitação e Simplificação na tradução de termos simples ...

    Sociedade 5. Negros 6. Gente 7. Povo 8. Escravos 9. Civilização 10. Cultural Tabela 1: Lista das dez palavras mais frequentes no subcorpus principal em português Para a análise do corpus de estudo de Antropologia das Civilização, utilizamos primeiramente as...
  • What-ere you do in word or deed, do

    What-ere you do in word or deed, do

    What-e're you do in word or deed, do all in the name of the Lord. Do naught in name of man or creed, do all in the name of the Lord. Inferences
  • What are you interested in? - Ch. 1 - PROF. JONES

    What are you interested in? - Ch. 1 - PROF. JONES

    What are you interested in? Oh, I like a lot of things. What I like the most is computer games. Have you ever played LOL (League of Legends)? My ranking is gold, and I have played LOL for several years.
  • Drug Classification - Uplift Education

    Drug Classification - Uplift Education

    A drug is a substance that is designed to affect the body either physically or psychologically. Controlled substances . are all drugs whose use and/or possession are somehow restricted by law. Definitions. Name a controlled substance. Name a drug that...
  • THEILERIOSIS EAST COAST FEVER By Julie Murchie and

    THEILERIOSIS EAST COAST FEVER By Julie Murchie and

    Caused by a tick-borne obligate intracellular parasite, Theileria parva, in sub-Saharan Africa, infecting ungulates. Major constraint to livestock production & food security in many developing countries. Causes high morbidity & mortality, killing 1 million cattle every year
  • CHAPTER 5 Microbial Metabolism Basic Chemical Reactions Underlying

    CHAPTER 5 Microbial Metabolism Basic Chemical Reactions Underlying

    Precursor metabolites, energy from ATP, and enzymes are used in anabolic reactions. ... Activation energy. without enzyme. Activation energy. with enzyme. Products. Figure 5.4 The effect of enzymes on chemical reactions. Active sites similar. to substrate's.
  • C-Notes: Enzymes

    C-Notes: Enzymes

    How does the structure of an enzyme affect its function?. Enzymes are . SPECIFIC! Each enzyme has a SPECIFIC " SHAPE " that . only . allows for a . certain " reactant " to bind to it. (needs to...
  • Plant Pigment Chromatography Visual Instructions Step through the

    Plant Pigment Chromatography Visual Instructions Step through the

    Lay the spinach leaf over the paper and roll a coin back and forth, over the line, 2-3 times. ... These are the different pigments in the leaf. Greens are Chlorophylls. Yellows are Carotenes and Xanthophylls. Take your paper out...