Sorting Algorithms: Bubble Sort vs. Merge Sort
Explore the concepts of bubble sort and merge sort algorithms in computing, learn how they work, compare their differences, and practice tracing them. Engage in interactive activities to enhance your understanding of sorting algorithms.
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
Teaching Computing to GCSE Session 7 Theory: Sorting Algorithms Practical: Testing
Specification Content OCR Standard sorting algorithms: Bubble sort Merge sort Insertion sort AQA Understand and explain how the merge sort algorithm works. Understand and explain how the bubble sort algorithm works. Compare and contrast merge sort and bubble sort algorithms. Edexcel Understand how standard algorithms (bubble sort, merge sort) work.
Sorting Algorithms We use sorting algorithms to sort lists of unordered values. There are many different sorting algorithms, these include: Bubble Sort Merge Sort Insertion Sort
Activity 1 This activity will demonstrate a fun way of teaching sorting algorithms.
Bubble Sort Tracing (1) In exams students may be asked to demonstrate their understanding of the bubble sort algorithm by tracing it. One method of tracing is to show the state of the list after each swap. Original List 2 3 1 5 6 4 Swap 1 2 1 3 5 6 4 Swap 2 2 1 3 5 4 6 Swap 3 1 2 3 5 4 6 Swap 4 1 2 3 4 5 6
Bubble Sort Tracing (2) Another way to trace the bubble sort algorithm is to show the state of the list after each complete pass. Original List 2 3 1 5 6 4 Pass 1 2 1 3 5 4 6 Pass 2 1 2 3 4 5 6 Pass 3 1 2 3 4 5 6
Activity 2a Complete this table to show the state of the list after each swap using the bubble sort algorithm: Original List 56 32 49 24 Swap 1 Swap 2 Swap 3 Swap 4 Swap 5
Activity 2b Complete this table to show the state of the list after each pass using the bubble sort algorithm: Original List 78 46 13 27 Pass 1 Pass 2 Pass 3
Merge Sort Tracing In exams students may be asked to demonstrate their understanding of the merge sort algorithm by tracing it. Original List 3 2 7 5 1 8 6 4 Stage 1 3 2 7 5 1 8 6 4 Stage 2 2 3 5 7 1 8 4 6 Stage 3 2 3 5 7 1 4 6 8 Stage 4 1 2 3 4 5 6 7 8
Activity 3 Complete this table to show the state of the list after each stage of the merge sort algorithm: Original List 56 44 76 21 14 82 65 71 Stage 1 Stage 2 Stage 3 Stage 4
Insertion Sort Tracing In exams students may be asked to demonstrate their understanding of the insertion sort algorithm by tracing it. Sorted Unsorted Stage 1 23, 56, 87, 18, 29 Stage 2 23 56, 87, 18, 29 Stage 3 23, 56 87, 18, 29 Stage 4 23, 56, 87 18, 29 Stage 5 18, 23, 56, 87 29 Stage 6 18, 23, 29, 56, 87
Activity 4 Complete this table to show the state of the list (56, 44, 76, 21, 14) after each stage of the insertion sort algorithm: Sorted Unsorted Stage 1 Stage 2 Stage 3 Stage 4 Stage 5 Stage 6
Comparison Students need to understand the benefits and drawbacks of each sorting algorithm. Algorithm Benefits / Drawbacks Bubble Sort Simple to implement but very inefficient. Merge Sort An efficient algorithm for sorting both large and small lists. Insertion Sort Relatively efficient when used with small lists, but not with larger lists.
