GCSE Bubble, Merge And Insertion Sort OCR

GCSEOCRComputer ScienceJ2763Bubble, mergeand insertion sortUnit 5Algorithms

Objectives Understand and be able to trace sort algorithms: Bubble sort Insertion sort Merge sort

Bubble, merge and insertion sortUnit 5 AlgorithmsSorting Data sets frequently need to be sorted Look at the 10 cards of the most popular boys’names in 2016 What orders could they be sorted in? Why might you need to sort data sets?

Bubble, merge and insertion sortUnit 5 AlgorithmsThe bubble sort Each item in a list is compared to the one next to it,and if it is greater, they swap places At the end of one pass through the list, the largestitem is at the end of the list This is repeated until the items are sorted Suppose you have a list of numbers to be sorted:954 15 38 11 2

Bubble, merge and insertion sortUnit 5 AlgorithmsBubble sort - First 81125493815 1125493811 1525493811152 Each item is comparedwith the one on its right,and swapped if it islarger At the end of the firstpass the largest itembubbles through to theend of the list (Mauve indicates sorteditems)

Bubble, merge and insertion sortUnit 5 AlgorithmsFirst passSecond 12155493815 11245389112155493811 15245389211 155493811152

Bubble, merge and insertion sortUnit 5 AlgorithmsSecond passThird pass549381121545389211 15459381121545389211 15459381121543589211 15453981121543589211 15453891121543589211 15453891121543582911 1545389211 15

Bubble, merge and insertion sortUnit 5 AlgorithmsThird passFourth pass45389211 1534582911 1545389211 1534582911 1543589211 1534582911 1543589211 1534582911 1543589211 1534528911 1543582911 15

Bubble, merge and insertion sortUnit 5 AlgorithmsFourth passFifth pass34582911 1534528911 1534582911 1534528911 1534582911 1534528911 1534582911 1534258911 1534528911 15

Bubble, merge and insertion sortUnit 5 AlgorithmsFifth passSixth pass34528911 1534258911 1534528911 1534258911 1534528911 1532458911 1534258911 15

Bubble, merge and insertion sortUnit 5 AlgorithmsSixth passSeventh pass34258911 1532458911 1534258911 1523458911 1532458911 15 7 passes through the list of 8 numbers ensures thatthey are sorted

Bubble, merge and insertion sortUnit 5 AlgorithmsWorksheet 3 Now try Task 1 on the worksheet

Bubble, merge and insertion sortUnit 5 AlgorithmsInsertion sort This algorithm sorts one data item at a time It is similar to how you might sort a hand of cards One item is taken from the list, and placed in the correctposition This is repeated until there are no more unsorted items in thelist

Bubble, merge and insertion sortUnit 5 AlgorithmsInsertion sortLeave the first item at the start:9541538112

Bubble, merge and insertion sortUnit 5 AlgorithmsInsertion sortLeave the first item at the start:95415381125 is now inserted into the sorted list:5941538112

Bubble, merge and insertion sortUnit 5 AlgorithmsInsertion sortLeave the first item at the start:95415381125 is now inserted into the sorted list:59415381124 is now inserted into the sorted list:4591538112

Bubble, merge and insertion sortUnit 5 AlgorithmsInsertion sortLeave the first item at the start:95415381125 is now inserted into the sorted list:59415381124 is now inserted into the sorted list:459153811215 is now inserted into the sorted list:4591538112

Bubble, merge and insertion sortUnit 5 AlgorithmsInsertion sortLeave the first item at the start:95415381125 is now inserted into the sorted list:59415381124 is now inserted into the sorted list:459153811215 is now inserted into the sorted list:45915381123 is now inserted into the sorted list:3459158112

Bubble, merge and insertion sortUnit 5 AlgorithmsInsertion sortLeave the first item at the start:95415381125 is now inserted into the sorted list:59415381124 is now inserted into the sorted list:459153811215 is now inserted into the sorted list:45915381123 is now inserted into the sorted list:34591581128 is now inserted into the sorted list:3458915112

Bubble, merge and insertion sortUnit 5 AlgorithmsInsertion sortLeave the first item at the start:95415381125 is now inserted into the sorted list:59415381124 is now inserted into the sorted list:459153811215 is now inserted into the sorted list:45915381123 is now inserted into the sorted list:34591581128 is now inserted into the sorted list:345891511211 is now inserted into the sorted list:3458911152

Bubble, merge and insertion sortUnit 5 AlgorithmsInsertion sortLeave the first item at the start:95415381125 is now inserted into the sorted list:59415381124 is now inserted into the sorted list:459153811215 is now inserted into the sorted list:45915381123 is now inserted into the sorted list:34591581128 is now inserted into the sorted list:345891511211 is now inserted into the sorted list:34589111522 is now inserted into the sorted list:2345891115Which item did not have to move?

Bubble, merge and insertion sortUnit 5 AlgorithmsWorksheet 3 Now try Task 2 on the worksheet

Bubble, merge and insertion sortUnit 5 AlgorithmsMerging two listsList A6813 20List B2711 16 Read item from list A; Read item from list B. Write smaller to output list. Read next item from the list that held the smallervalue Repeat until all items written to output list

Bubble, merge and insertion sortUnit 5 AlgorithmsMerging two listsList A68List B13 202 Read item from list A6 Read item from list B2Output list2711 16Compare and writesmaller item to output

Bubble, merge and insertion sortUnit 5 AlgorithmsMerging two listsList A68List B13 202 Read item from list A6 Read item from list B7Output list26711 16Compare and writesmaller item to output

Bubble, merge and insertion sortUnit 5 AlgorithmsMerging two listsList A68List B13 202 Read item from list A8 Read item from list B7Output list267711 16Compare and writesmaller item to output

Bubble, merge and insertion sortUnit 5 AlgorithmsMerging two listsList A68List B13 202 Read item from list A8 Read item from list B11Output list2678711 16Compare and writesmaller item to output

Bubble, merge and insertion sortUnit 5 AlgorithmsMerging two listsList A68List B13 202711 16 Fill in the rest of the output listOutput list267811 13 16 20

Bubble, merge and insertion sortUnit 5 AlgorithmsMerge sort This is much more efficient than the bubble sort The basic steps are: Divide the unsorted list into n sublists, eachcontaining one element Repeatedly merge two sublists at a time to producenew sorted sublists until there is only one sublistremaining. This is the sorted list. We will use a list of 8 integers to demonstrate theprocess

Bubble, merge and insertion sortUnit 5 AlgorithmsMerge sort part 1 Divide the unsorted list into n sublists

Bubble, merge and insertion sortUnit 5 AlgorithmsMerge sort part 2 Now merge the pairs of sublists into a singlesorted list

Bubble, merge and insertion sortUnit 5 AlgorithmsWorksheet 3 Now try Task 3 on the worksheet

Bubble, merge and insertion sortUnit 5 AlgorithmsComparing sorts The Insertion sort is much quicker than the Bubblesort, but the Merge sort is faster still Be sure you can explain how each sort works

Bubble, merge and insertion sortUnit 5 AlgorithmsCopyright 2016 PG Online LimitedThe contents of this unit are protected by copyright.This unit and all the worksheets, PowerPoint presentations, teaching guides and other associated files distributedwith it are supplied to you by PG Online Limited under licence and may be used and copied by you only inaccordance with the terms of the licence. Except as expressly permitted by the licence, no part of the materialsdistributed with this unit may be used, reproduced, stored in a retrieval system, or transmitted, in any form or byany means, electronic or otherwise, without the prior written permission of PG Online Limited.Licence agreementThis is a legal agreement between you, the end user, and PG Online Limited. This unit and all the worksheets,PowerPoint presentations, teaching guides and other associated files distributed with it is licensed, not sold, toyou by PG Online Limited for use under the terms of the licence.The materials distributed with this unit may be freely copied and used by members of a single institution on asingle site only. You are not permitted to share in any way any of the materials or part of the materials with anythird party, including users on another site or individuals who are members of a separate institution. Youacknowledge that the materials must remain with you, the licencing institution, and no part of the materials maybe transferred to another institution. You also agree not to procure, authorise, encourage, facilitate or enable anythird party to reproduce these materials in whole or in part without the prior permission of PG Online Limited.

OCR Computer Science J276 Bubble, merge and insertion sort Unit 5 Algorithms 3 Understand and be able to trace sort algorithms: Bubble sort Insertion sort Merge sort Objectives . Bubble, merge and insertion sort Unit 5 Algori