Download:

Insertion Sort Code(Code Needs To Be Copied Into Python)

townlist(Text Document Needed For Python File to Work)

Note: Make sure that townlist and the python file is in the same folder for the program to work. Remove/add comments where needed in order test out variants

**Insertion Sort: (GCSE & A-Level)**

The Insertion sort inserts each item into its correct position in a data set one at a time,

*Simplified Explanation:*

- Start at the second item in the list.
- Compare current item with the first item in the sorted list
- If the current item is greater than the item in the list, move to the next item in the sorted list.
- Repeat from step 3 until the position of the current item is less than or equal to the item in the sorted list.
- Move all the items in the list from the current position up one place to create a space for the current item.
- Insert the current Item.
- Repeat from step 2 with the next item in the list until all items have been inserted.

**Insertion Sort in Python:**

Advantages: |
Disadvantages: |

· Can out perform a quicksort/bubblesort on small data sets | · It is less efficient on a large datasets as performance slows down |

· It is a simple algorithm that is easy to make and implement | |

· Has the ability to sort a list as it is being received | |

** **

**Big O Notation: (A-Level)**

Best Case: |
Average Case: |
Worst Case: |
Space Complexity |

· Linear | · Polynomial | · Polynomial | · Constant |

· O(n) | · O(n^{2}) |
· O(n^{2}) |
· O(1) |

1,357 total views, 1 views today