Understanding Sorting Algorithms: Bubble Sort and Insertion Sort
Master the concepts of standard sorting algorithms through a detailed exploration of Bubble Sort and Insertion Sort. Learn how each algorithm functions step-by-step, gaining a practical understanding of sorting techniques in computational thinking and programming. Engage in hands-on activities to apply these algorithms to real-world scenarios and solidify your knowledge in this fundamental aspect of 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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Sorting Algorithms 2.1 Algorithms
Monday, 22 July 2024 Sorting Algorithms Unit 2: Computational Thinking, Algorithms & Programming Learning Objective: To be able to demonstrate an understanding of standard sorting algorithms. Success Criteria: 1. I can describe how items are sorted using a bubble sort algorithm. 2. I can write a bubble sort algorithm. 3. I can describe how items are sorted using an insertion sort algorithm. 4. I can write an insertion sort algorithm.
Unit 2: Computational Thinking, Algorithms & Programming Sorting Algorithms You need to know how to complete the following sort algorithms: Bubble sort Insertion sort Merge sort
Unit 2: Computational Thinking, Algorithms & Programming Bubble Sort A bubble sort works by comparing each item in the list to the item to the right of it. The item is then moved based upon whether it is bigger/smaller. Step 1: Compare the first two numbers. Are they in order? Adjust them if not. 10 2 6 5 11 Step 2: Move to the next two numbers. Are they in order? Adjust them if not. 2 10 6 5 11
Unit 2: Computational Thinking, Algorithms & Programming Bubble Sort Step 3: Move to the next two numbers. Are they in order? Adjust them if not. 2 6 10 5 11 Step 4: Move to the next two numbers. Are they in order? Adjust them if not 2 6 5 10 11 Step 5: Once you have been through the entire list, check that they are in order. If they are, great! If not, undertake the same process again until they are in order.
Unit 2: Computational Thinking, Algorithms & Programming Bubble Sort: Activity A 15 9 22 27 14 B 44 30 16 51 27 C Pear Banana Apple Blueberry Pineapple D Rain Lolly Freedom Aeroplane Zebra Task: Sort the above using the bubble sort algorithm. Show your steps. Show the order of the list after each adjustment.
Unit 2: Computational Thinking, Algorithms & Programming Insertion Sort Algorithm The insertion sort works by looking at each value in turn and inserting the value into its correct place in the list. 2 Step 1: Compare the first two items. 9 > 2 so 2 moves position. 9 5 8 7
Unit 2: Computational Thinking, Algorithms & Programming Insertion Sort Algorithm Step 2: Insert 5 into its correct position. 5 > 2 and 5 < 8 so 5 moves position. 5 2 9 8 7 8 Step 3: Insert 8 into its correct position. 8 > 5 and < 9 so 8 moves position. 2 5 7 9
Unit 2: Computational Thinking, Algorithms & Programming Insertion Sort Algorithm Step 4: Insert 7 into its correct position. 7 > 5 and 7 < 8 so 7 moves position. 7 2 5 8 9 Completed Insertion Sort: 2 5 7 8 9
Unit 2: Computational Thinking, Algorithms & Programming Insertion Sort: Activity A 4 2 8 9 7 B 19 5 8 7 15 C 40 9 32 27 20 Task: Sort the above using the Insertion sort algorithm. Show your steps. Show the order of the list after each adjustment.
Unit 2: Computational Thinking, Algorithms & Programming Merge Sort Algorithm The merge sort algorithm is an example of a divide-and-conquer algorithm and takes advantage of two facts: Small lists are easier to sort than large lists. It s easier to merge two-ordered lists than two unordered lists. 1) Split the list in half (the smaller lists are called sub-lists) the second sub-list should start at the middle item. 2) Keep repeating step 1 on each sub-list until all the lists only contain one item. 3) Merge pairs of sub-lists so that each sub-list has twice as many items. Each time you merge sub-lists, sort the items into the right order. 4) Repeat step 3 until you ve merged all the sub-lists together.
Unit 2: Computational Thinking, Algorithms & Programming Merge Sort: Example F P A L T D K H F P A L T D K H F P A L T D K H F P A L T D K H F P A L D T H K A F L P D H K T A D F H K L P T
Unit 2: Computational Thinking, Algorithms & Programming Merge Sort Pros & Cons The pros and cons of merge sort algorithms are as follows: Pros Cons In general, it is much more efficient and quicker than the bubble sort and insertion sort algorithms for large lists. It has a very consistent running time regardless of how ordered the items in the original list are. It s slower than other algorithms for small lists. Even if the list is already sorted it still goes through the whole splitting and merging process. It uses more memory than the other sorting algorithms in order to create the separate lists.
Unit 2: Computational Thinking, Algorithms & Programming Merge Sort: Activity Task: Sort these items using the merge sort method. S A P H J Z E R 19 5 29 1 87 14 61 33 Goat Dog Bird Turtle Horse Snake Lion Bear
