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,
- 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:
|· 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(n2)||· O(n2)||· O(1)|
357 total views, 2 views today