AQA D1 Sorting Algorithms

HideShow resource information

Bubble Sort

HOW TO:

1. Compare the first and second number, swap if necessary

2. Compare the second and third number, swap if neccessary

3. Continue through the list until the last two numbers have been compared

4. Draw a box around the last number

END OF FIRST PASS

5. Repeat steps 1-4 (ignore the boxed number)

6. Continue until there is a pass with no swaps

MAX No. OF PASSES= n+1 (when items are in reverse order)

MAX No. OF SWAPS/COMPARISONS= (n-1)+(n-2)+(n-3)...+1 OR n/2(n+1)

1 of 4

Shuttle Sort

HOW TO:

1. Block off the first and second numbers

2. Compare them and swap if necessary

END OF FIRST PASS

3. Continue line to block off the third number

4. Compare the second and third number, swap if necessary

5. If swapped, compare swapped number with the one in front of it. Swap again if necessary

END OF SECOND PASS

6. Repeat steps 3-5 until the last pair of numbers have been compared and the pass is complete

NO. OF PASSES= n-1

2 of 4

Shell Sort

HOW TO:

1. Count the number of items in the list (N)

2. Share the list into N/2 subsets (ignore any remainder)

3. Sort each subset into order

4. Put the whole list back together

END OF FIRST PASS

5. Share the list into N/4 subsets

6. Repeat steps 3-4 until there is only 1 subset

7. Sort final list using shuttle sort

3 of 4

Quick Sort

HOW TO:

1. Underline the first number in the list as a pivot

2. Move numbers around the pivot in their original order (smaller numbers infront, larger numbers remain after)

END OF FIRST PASS

3. Box previous pivot in new list

4. Repeat step 1-3

6. Stop when all numbers have been a pivot / there is only one number in a list

4 of 4

Comments

NuttyIG

Report

I have a feeling that the shell sort algorithm is wrong compared to the AQA syllabus and mark schemes. In AQA, they expect make the lists based on the first number of each sublist, then the second number of each sublist. You can't just "Put the whole list together."

Just a quick heads up for my AQA buddies.

Similar Mathematics resources:

See all Mathematics resources »See all Networks, algorithms and problem solving resources »