Introduction to Sorting Algorithms and Data Structures
Explore the fundamentals of sorting algorithms and data structures in this comprehensive lecture series by Franck Chauvel from Axbit & NTNU. Learn about simple sorting techniques, such as Selection Sort, Insertion Sort, and Bubble Sort. Discover the concept of sorting sequences and the importance of putting items in order. Dive into key aspects like comparison, stability, and the implementation of sorting algorithms. Get hands-on practice through examples and understand the significance of sorting in computer science.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
IDATA2032 Algorithms & Data Structures Simple Sorting Introduction to Sorting Sequences Sequences / Lecture 5 Franck Chauvel Axbit & NTNU Ask anything on www.menti.com with code 8466 4411 franck.chauvel@ntnu.no
Binary Search Find 67 54 < 67 86 > 67 27 < 67 Found 0 1 2 3 4 5 6 7 8 9 10 11 8 11 23 27 35 37 39 54 55 67 86 213 3rd pick 2nd pick 1st pick smaller larger
Agenda 1. 2. Selection Sort 3. Insertion Sort 4. Bubble Sort 5. Recap What is Sorting ? 3
What is Sorting? Put things in order Numerical Lexicographical Find a permutation where Items are ordered 4
Key vs. Information Information is your data set Key: What you use to compare Compound keys Name John John Lara Lara Harry Harry Bob Bob Sarah Sarah Surname Doe Doe Croft Croft Potter Potter Sponge Sponge Connor Connor Subject Alg. & DS DB DB Alg & DS OS DB OS Alg & DS OS Alg.&DS Score 50 76 23 46 10 65 97 34 90 78 5
Comparable Items Need to compare items Total preorder: : ? ? ? Reflexive: ? ?, ? ? Transitive: ?,?,? ?3, ? ? ? ? ? ? int compare<T>(T left, T right) { return ... } 6
Stability Stable Given input order preserved order changed order preserved Unstable
How Would you do? Give it a try for a few minutes 8
Selection Sort smallest largest 2 5 17 22 22 23 28 35 36 36 50 51 minimum comes first! sub array Intuition: 1. select the minimum 2. put it first 3. repeat for the remaining elements 9
Selection SortSlow Motion minimum minimum 36 35 22 28 22 28 35 22 36 22 ok swap minimum minimum 36 35 22 35 36 22 22 28 22 28 swap swap 10
Selection Sort def selection_sort(sequence) def find_minimum(sequence, start) for index in 0 .. sequence.length-2 minimum = start minimum = find_minimum(sequence, index) for index in start+1 .. sequence.length-1 swap(sequence, index, minimum) if sequence[index] < sequence[minimum] end minimum = index end end end def swap(sequence, left, right) return minimum tmp = sequence[right] end sequence[right] = sequence[left] sequence[left] = tmp end 11
Time & Space Complexity Time Memory Best ?(?) (1) Average ?(??) (1) Worst ?(??) (1) Exercise How would you proove the average case? 12
Insertion Sort 28 larger 22 22 23 35 36 smaller Idea: To keep an array sorted, we insert new items between the smaller and the bigger 13
Insertion SortSlow Motion Step 1 Step 4 22 28 28 35 22 36 22 35 36 22 Step 2 Step 5 28 35 22 36 22 28 35 36 22 22 Step 3 28 35 22 36 22 14
Insertion Sort def insertion_sort(sequence) for index in 1 .. sequence.length-1 position = find_position(sequence, index) insert(sequence, position, index) end end def find_position(sequence, last) for index in 0 .. last if sequence[index] >= sequence[last] return index end end return last end def insert(sequence, position, last) value = sequence[last] for index in last.downto(position) sequence[index] = sequence[index-1] end sequence[position] = value end 15
Time & Space Complexity Time Memory Best ?(?) (1) Average ?(??) (1) Worse ?(??) (1) Exercise How would you proove the average case? 16
Bubble Sort pair ???? ??? ? smallest largest 2 5 17 22 22 23 28 35 36 36 50 51 ???? ??? ? ???? ??? ? ???? ??? ? pair pair pair Intuition: Keep traversing the array Swapping pairs that are disordered Until there is no more pair to swap 17
Bubble Sort Step 4 Step 1 28 22 35 36 22 28 35 22 36 22 swap ok Step 5 Step 2 28 22 36 28 35 22 36 22 22 35 swap swap Step 6 Step 3 22 28 35 36 22 28 22 35 36 22 ok ok 18
Bubble Sort Step 6 Step 10 22 35 36 22 28 35 22 36 28 22 ok ok Step 10 Step 7 22 28 22 35 36 22 28 35 22 36 ok swap Step 8 22 28 22 35 36 ok 19
Code def bubble_sort(sequence) swapped = true while swapped swapped = false for index in 1 .. sequence.length-1 if sequence[index] < sequence[index-1] swap(sequence, index-1, index) swapped = true end end end end def swap(sequence, left, right) tmp = sequence[right] sequence[right] = sequence[left] sequence[left] = tmp end 20
Time & Space Complexity Time Memory Best ?(?) (1) Average ?(??) (1) Worse ?(??) (1) Exercise How would you proove the average case? 21
Recap Best Average Worst Memory Stable Insertion Yes (?2) ?(??) (?) (1) Selection No (?2) ?(??) (?) (1) Bubble Yes (?2) ?(??) (?) (1) 22
Thank You! Questions, Comments, or Ideas? Franck Chauvel Axbit & NTNU franck.chauvel@gmail.com
