# D1 aqa

HideShow resource information
• Created by: Lauren-x-
• Created on: 05-01-16 19:40

## Bubble Sort

·         Compare first two numbers. The larger number moved to second, leaving behind the smaller number at the front.

·         the second and third numbers are compared. The lighter number gets moved to the front.

·         Etc... Until you get to the end of the row. This is known as a pass.

·         Repeat from beginning again until nothing has moved (no swaps made).

[Write out the number of comparisons and passes made at every pass. Show every pass made until everything is in order, i.e. no more swaps are made. It’s called bubble as the lighter number rises to the top... but my teacher thinks it should be called dead weight as the heavy number is the one that moves... to the bottom.]

1 of 4

## Shuttle Sort

·         Compare first two numbers.

·         Move larger number to second place.

·         Compare first three numbers.

·         Move it into position by comparing it with second, first.

·         Etc...Until all number have been compared.

[write out each pass and the comparisons and swaps at each one too. you will also need to underline the ones that are being compared, so on the original list the first two, then first three, first four.... etc. failure to come up with a weird analogy.]

2 of 4

## Shell Sort

·         Separate into sublists using INT(n/2) this gives the number of lists to be used

·         Pair up the first number in the first half with the first number in the second half, second with second etc. but keeping the order the same.[write each pair on separate lines diagonally so order can be seen.]

·         Compare the pairs and shuttle sort them to get the larger number at the back.

·         Merge/re-piece the list but with the numbers that have been swapped in their new positions.

·         Quarter the list and do the same with each sublist.

·         Repeat until each sublist only has 1 number.

[As you will only need to write out the sublists, and then the merges the guy won’t know how you sorted the sublists etc. Write out comparisons and swaps at each stage.]

3 of 4

## Quick Sort

·         Use the first number as the pivot. [Underline it].

·         Keeping the order of the numbers, move the smaller ones in front of the pivot, keeping larger ones behind. [write this pass out]

·         The first number in each sublist is now a new pivot. [box the pivot you have just used and underline new ones]

·         Repeat until every number has been used as a pivot [everything is boxed] - Maybe I'm wrong but I believe that you only box the first in each sublist, until each sublist only has 1 number.

4 of 4