Embedded Files
SDD Topic has been refreshed!
What is an insertion Sort?
What is an insertion Sort?
An insertion sort builds the list one element at a time from the second element
The first element to be checked is item 1(assuming the first index is 0)
The current value to be inserted is stored
When an element is greater than the value to be inserted it is shifted one element to the right.
When the next element to be shifted is less than the value to be inserted then the value is placed at that point
"Swfung8 - Own work Licensed under CC BY-SA 3.0 via Wikimedia Commons - https://en.wikipedia.org/wiki/File:Insertion-sort-example-300px.gif
Insertion Sort Example - Cards
Insertion Sort Example - Cards
We will look at the following list of cards and perform 2 passes of an insertion sort algorithm.
After 1 iteration
After 1 iteration
After 2 iterations
After 2 iterations
Insertion Sort Example
Insertion Sort Example
Algorithm - Insertion Sort
Algorithm - Insertion Sort
The outer fixed loop starts from element 1 in the list. We assume that element 0 is already sorted.
Before we enter the inner loop we have to store the value that is going to be inserted into its new position and also the position that it came from.
Then whilst the current value to be placed is less than the value to the left of the current position we will shift the values to the right.
When we find the position the current value to be placed should go into we assign this to the array.
Python Implementation - Insertion Sort
Python Implementation - Insertion Sort
How do we know if a list is sorted when using an insertion sort??
How do we know if a list is sorted when using an insertion sort??
If we use the insertion sort algorithm below - when we would we know when the list of cards below are sorted if we are using the algorithm?
We would need to iterate through the entire list once to ensure that everything is in place.
Swapping Parallel Arrays using Insertion Sort
Swapping Parallel Arrays using Insertion Sort
We want to sort these two arrays so that ages (and corresponding names) are in ascending order of age
So we will run our algorithm below:
a problem...
a problem...
Sorting Parallel Arrays
Sorting Parallel Arrays
We will need to ensure that when we perform a swap that we swap the corresponding value in the other parallel array.
The elements in green will be swapped on the first iteration
Sorting Arrays of records
Sorting Arrays of records
Similar to sorting parallel arrays but we are using the following record structure shown to the right
Our record structure
Our record structure
Our array of records
Our array of records
The highlighted Lines 13-15 ensure that we mimic the shifts in the second parallel array (names).
If there were more than two parallel arrays then you would need to repeat this bold section for each parallel array used.
Sorting arrays of objects
Sorting arrays of objects
You will notice that is very similar to the algorithm for sorting the record of arrays.
This time we use the appropriate getter method e.g. getAge() in order to retrieve the appropriate value of an instance variable for use in the comparison.
Sorting 2D Arrays
Sorting 2D Arrays
Sorting by a column
Sorting by a column
You can apply any sort algorithm to a 2D array. If you consider that the following 2D array with names and 5 scores
We want to sort the score array into alphabetical order (first column)
Initial State
Initial State
We want to sort the score array into alphabetical order (first column)
Goal state
Goal state
The whole rows have now been swapped to their final position
Sorting by rows
Sorting by rows
We want to sort the scores in each row into ascending order
Initial State
Initial State
We want to sort the scores in each row into ascending order
Goal state
Goal state
We have sorted the scores in each row into ascending order
Page updated
Report abuse