Difference between revisions of "W2202 Insertion Sort"
Daniel-suh (talk | contribs) m (→Example) |
Jeff-strong (talk | contribs) m (Editorial review and minor corrections) |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
== Algorithm == | == Algorithm == | ||
Unlike [[W1352 Bubble Sort|Bubble Sort]] which only | Unlike [[W1352 Bubble Sort|Bubble Sort]], which compares only two elements at a time, insertion sort works by looking at each element and finding where it belongs in the sorted array. At its base, insertion sort is more complicated than bubble sort, but not by much: | ||
* Iterate over the array | * Iterate over the array | ||
* For each element at index '''i''', loop back through the array starting at '''i''' to '''0''' | * For each element at index '''i''', loop back through the array starting at '''i''' to '''0'''. | ||
** Similar to bubble sort, if the element on the left is larger than the element on the right, swap them | ** Similar to bubble sort, if the element on the left is larger than the element on the right, swap them. | ||
*** Because this starts by comparing '''i''' and '''i - 1''', if the current element is not in place it will get swapped to '''i - 1'''. If it is still not in place in the next iteration, it will be swapped to '''i - 2''', and so on until it is in the correct place | *** Because this starts by comparing '''i''' and '''i - 1''', if the current element is not in place, it will get swapped to '''i - 1'''. If it is still not in place in the next iteration, it will be swapped to '''i - 2''', and so on until it is in the correct place. | ||
* After each iteration, all | * After each iteration, all the elements up to '''i + 1''' will be in the correct order, although not necessarily ''sorted'' in the context of the full array. | ||
* Unlike bubble sort, you | * Unlike bubble sort, you need to iterate through the array only once. Once you reach the end, the array is sorted. | ||
=== Swap === | === Swap === | ||
You can use the same swap function as in bubble sort because you | You can use the same swap function as in bubble sort because you need to be able to swap only two adjacent elements at a time. | ||
=== Performance Considerations === | === Performance Considerations === | ||
Similar to bubble sort, consider passing the array '''by reference''' into the swap function (if you have one) instead of '''by value''' to avoid copying the entire array for each swap. | Similar to bubble sort, consider passing the array '''by reference''' into the swap function (if you have one) instead of '''by value''' to avoid copying the entire array for each swap. | ||
Additionally, in insertion sort, you can stop/break the inner loop once you reach two sorted elements. In other words, you | Additionally, in insertion sort, you can stop/break the inner loop once you reach two sorted elements. In other words, you need to swap only until the element on the left is smaller than the element on the right, at which point, you can exit the loop. | ||
<br> | <br> | ||
Line 21: | Line 21: | ||
=== Example === | === Example === | ||
Here is an example with an array of 5 elements: | Here is an example with an array of 5 elements: | ||
Note: The Array contents are shown, directly after each pass of the insertion sort | Note: The Array contents are shown, directly after each pass of the insertion sort. | ||
<pre> | <pre> | ||
Line 31: | Line 31: | ||
| | | | ||
// The algorithm then looks at the element at index 2: 62. Since 62 < 95, the two elements are swapped | // The algorithm then looks at the element at index 2: 62. Since 62 < 95, the two elements are swapped | ||
// The algorithm then checks if 62 < 47, this is not true so the pass is completed. | // The algorithm then checks if 62 < 47, this is not true, so the pass is completed. | ||
Array: [47, 62, 95, 33, 89] | Swaps: 1, Pass: 2 | Array: [47, 62, 95, 33, 89] | Swaps: 1, Pass: 2 | ||
Line 41: | Line 41: | ||
| | | | ||
// The algorithm now looks at the element at index 4: 89. Since 89 < 95, the two elements are swapped. | // The algorithm now looks at the element at index 4: 89. Since 89 < 95, the two elements are swapped. | ||
// 89 is only | // 89 is swapped only once because, after the first swap, 89 !< 62. | ||
Array: [33, 47, 62, 89, 95] | Swaps: 1, Pass: 4 <- Result after 4 passes | Array: [33, 47, 62, 89, 95] | Swaps: 1, Pass: 4 <- Result after 4 passes | ||
Line 55: | Line 55: | ||
{ | { | ||
In which case | In which case does an insertion sort perform best? | ||
|type="()"} | |type="()"} | ||
- These will all perform equally well | - These will all perform equally well | ||
Line 63: | Line 63: | ||
{ | { | ||
One advantage of insertion sort is that it only | One advantage of insertion sort is that it requires only one comparison. | ||
|type="()"} | |type="()"} | ||
+ True | + True | ||
Line 92: | Line 92: | ||
+ -59, 10, 511, 831, -982 | + -59, 10, 511, 831, -982 | ||
- -982, 10, -59, 511, 831 | - -982, 10, -59, 511, 831 | ||
- -59, 511, 10, 831, - | - -59, 511, 10, 831, -982 | ||
- -982, -59, 10, 511, 831 | - -982, -59, 10, 511, 831 | ||
Line 99: | Line 99: | ||
After the '''second insertion''', the list will be: | After the '''second insertion''', the list will be: | ||
|type="()"} | |type="()"} | ||
- -59, 10, 511, 831, - | - -59, 10, 511, 831, -932 | ||
- -982, 10, -59, 511, 831 | - -982, 10, -59, 511, 831 | ||
+ -59, 10, 511, 831, - | + -59, 10, 511, 831, -982 | ||
- -982, -59, 10, 511, 831 | - -982, -59, 10, 511, 831 | ||
Line 108: | Line 108: | ||
After the '''third insertion''', the list will be: | After the '''third insertion''', the list will be: | ||
|type="()"} | |type="()"} | ||
- -59, 10, 511, 831, - | - -59, 10, 511, 831, -932 | ||
- -982, 10, -59, 511, 831 | - -982, 10, -59, 511, 831 | ||
+ -59, 10, 511, 831, - | + -59, 10, 511, 831, -982 | ||
- -982, -59, 10, 511, 831 | - -982, -59, 10, 511, 831 | ||
Line 119: | Line 119: | ||
+ -59, 10, 511, 831, -982 | + -59, 10, 511, 831, -982 | ||
- -982, 10, -59, 511, 831 | - -982, 10, -59, 511, 831 | ||
- -59, 511, 10, 831, - | - -59, 511, 10, 831, -982 | ||
- -982, -59, 10, 511, 831 | - -982, -59, 10, 511, 831 | ||
Line 128: | Line 128: | ||
- -59, 10, 511, 831, -982 | - -59, 10, 511, 831, -982 | ||
- -982, 10, -59, 511, 831 | - -982, 10, -59, 511, 831 | ||
- -59, 10, 511, 831, - | - -59, 10, 511, 831, -982 | ||
+ -982, -59, 10, 511, 831 | + -982, -59, 10, 511, 831 | ||
Latest revision as of 17:21, 15 November 2023
Algorithm[edit]
Unlike Bubble Sort, which compares only two elements at a time, insertion sort works by looking at each element and finding where it belongs in the sorted array. At its base, insertion sort is more complicated than bubble sort, but not by much:
- Iterate over the array
- For each element at index i, loop back through the array starting at i to 0.
- Similar to bubble sort, if the element on the left is larger than the element on the right, swap them.
- Because this starts by comparing i and i - 1, if the current element is not in place, it will get swapped to i - 1. If it is still not in place in the next iteration, it will be swapped to i - 2, and so on until it is in the correct place.
- Similar to bubble sort, if the element on the left is larger than the element on the right, swap them.
- After each iteration, all the elements up to i + 1 will be in the correct order, although not necessarily sorted in the context of the full array.
- Unlike bubble sort, you need to iterate through the array only once. Once you reach the end, the array is sorted.
Swap[edit]
You can use the same swap function as in bubble sort because you need to be able to swap only two adjacent elements at a time.
Performance Considerations[edit]
Similar to bubble sort, consider passing the array by reference into the swap function (if you have one) instead of by value to avoid copying the entire array for each swap.
Additionally, in insertion sort, you can stop/break the inner loop once you reach two sorted elements. In other words, you need to swap only until the element on the left is smaller than the element on the right, at which point, you can exit the loop.
Example[edit]
Here is an example with an array of 5 elements: Note: The Array contents are shown, directly after each pass of the insertion sort.
Array: [95, 47, 62, 33, 89] | Initial | // The algorithm first looks at the element at index 1: 47. Since 47 < 95, the two elements are swapped. Array: [47, 95, 62, 33, 89] | Swaps: 1, Pass: 1 <- Result immediately after the first pass | // The algorithm then looks at the element at index 2: 62. Since 62 < 95, the two elements are swapped // The algorithm then checks if 62 < 47, this is not true, so the pass is completed. Array: [47, 62, 95, 33, 89] | Swaps: 1, Pass: 2 | // The algorithm then looks at the element at index 3: 33. Since 33 < 95, the two elements are swapped. // This is repeated until 33 is at the beginning of the list Array: [33, 47, 62, 95, 89] | Swaps: 3, Pass: 3 | // The algorithm now looks at the element at index 4: 89. Since 89 < 95, the two elements are swapped. // 89 is swapped only once because, after the first swap, 89 !< 62. Array: [33, 47, 62, 89, 95] | Swaps: 1, Pass: 4 <- Result after 4 passes
Quiz[edit]
References[edit]
Insertion Sort (Wikipedia)