Write a function insertionsort(somelist) that applies the insertion sort algorithm. (You should use the pop and insert commands) Insertion sort works as follows remove the first element from the original list (mylist) and add it to a new list sortedlist. Then repeat, at each stage removing the first element (call it x) from mylist and adding it to sortedlist. The challenge is that it needs to be added at the correct position, which means scanning through sortedlist for the first element bigger than x and inserting x just before that point, or if there is no such element then inserting x at the end. We recollect two useful list commands you should use in this code: • x = mylist.pop(0) which lets x be the entry at index 0 of mylist while also removing that entry from mylist. (Generally x = mylist.pop(j) works in the obvious way.) • sortedlist.insert(i,x) which changes sortedlist by inserting x into it at index i (with all entries with indices ≥ i having their indices increased by 1).
The question is in bold the other parts juts helps explain concepts .
Write a function insertionsort(somelist) that applies the insertion sort
Insertion sort works as follows remove the first element from the original list (mylist) and add it to a new list sortedlist. Then repeat, at each stage removing the first element (call it x) from mylist and adding it to sortedlist. The challenge is that it needs to be added at the correct position, which means scanning through sortedlist for the first element bigger than x and inserting x just before that point, or if there is no such element then inserting x at the end. We recollect two useful list commands you should use in this code:
• x = mylist.pop(0) which lets x be the entry at index 0 of mylist while also removing that entry from mylist. (Generally x = mylist.pop(j) works in the obvious way.)
• sortedlist.insert(i,x) which changes sortedlist by inserting x into it at index i (with all entries with indices ≥ i having their indices increased by 1).
Step by step
Solved in 4 steps with 2 images
