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

No comments have yet been made

Similar Mathematics resources:

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