Difference between revisions of "W2202 Insertion Sort"

From Coder Merlin
(5 intermediate revisions by the same user not shown)
Line 13: Line 13:


=== Performance Considerations ===
=== Performance Considerations ===
Similar to bubble sort, if you use a swap function then consider passing the array by reference 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 only need to swap until the element on the left is smaller than the element on the right, at which point you can exit the loop.
Additionally, in insertion sort, you can stop/break the inner loop once you reach two sorted elements. In other words, you only need to swap until the element on the left is smaller than the element on the right, at which point you can exit the loop.
<br>


=== 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


<pre>
<pre>
Array: [95, 47, 62, 33, 89] | Initial
Array: [95, 47, 62, 33, 89] | Initial
   * Elements at indexes 0 (95) and 1 (47) are not in order (95 > 47), swapping.
            |
Array: [47, 95, 62, 33, 89] | Swaps: 1
   // The algorithm first looks at the element at index 1: 47. Since 47 < 95, the two elements are swapped.
   * Elements at indexes 1 (95) and 2 (62) are not in order (95 > 62), swapping.
 
   * Elements at indexes 0 (47) and 1 (62) are already in order (47 < 62), nothing to swap
Array: [47, 95, 62, 33, 89] | Swaps: 1, Pass: 1  <- Result immediately after the first pass
Array: [47, 62, 95, 33, 89] | Swaps: 1
                |
   * Elements at indexes 2 (95) and 3 (33) are not in order (95 > 33), swapping.
   // The algorithm then looks at the element at index 2: 62. Since 62 < 95, the two elements are swapped
   * Elements at indexes 1 (62) and 2 (33) are not in order (62 > 33), swapping.
   // The algorithm then checks if 62 < 47, this is not true so the pass is completed.
  * Elements at indexes 0 (47) and 1 (33) are not in order (47 > 33), swapping.
 
Array: [33, 47, 62, 95, 89] | Swaps: 3
Array: [47, 62, 95, 33, 89] | Swaps: 1, Pass: 2
   * Elements at indexes 3 (95) and 4 (89) are not in order (95 > 89), swapping.
                    |
   * Elements at indexes 2 (62) and 3 (89) are already in order (62 < 89), nothing to swap
   // The algorithm then looks at the element at index 3: 33. Since 33 < 95, the two elements are swapped.
Array: [33, 47, 62, 89, 95] | Swaps: 1
   // 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 only swapped once because, after the first swap, 89 !< 62.
 
Array: [33, 47, 62, 89, 95] | Swaps: 1, Pass: 4  <- Result after 4 passes
</pre>
</pre>



Revision as of 14:55, 29 April 2021

Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder

Algorithm[edit]

Unlike Bubble Sort which only compares 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
  • After each iteration, all of 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 only need to iterate through the array 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 only need to be able to swap 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 only need to swap 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 only swapped once because, after the first swap, 89 !< 62. 

Array: [33, 47, 62, 89, 95] | Swaps: 1, Pass: 4  <- Result after 4 passes

Quiz[edit]

1 Insertion Sort is an algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.

True
False

2 In which case would an insertion sort perform best?

These will all perform equally well
If the array was sorted in reverse order
If the array was already sorted
If the array was in a random order

3 One advantage of insertion sort is that it only requires one comparison.

False
True

4 Insertion sort is recommended for large arrays.

True
False

5 Insertion sort is useful when the array is close to being sorted.

True
False

6 Elements can move toward the beginning of the list very quickly.

True
False

7 Consider the list: 10, -59, 511, 831, -982
After the first insertion, the list will be:

-982, 10, -59, 511, 831
-982, -59, 10, 511, 831
-59, 511, 10, 831, -932
-59, 10, 511, 831, -982

8 Consider the list: 10, -59, 511, 831, -982
After the second insertion, the list will be:

-59, 10, 511, 831, -932
-59, 10, 511, 831, -982
-982, -59, 10, 511, 831
-982, 10, -59, 511, 831

9 Consider the list: 10, -59, 511, 831, -982
After the third insertion, the list will be:

-59, 10, 511, 831, -982
-982, 10, -59, 511, 831
-982, -59, 10, 511, 831
-59, 10, 511, 831, -932

10 Consider the list: 10, -59, 511, 831, -982
After the first pass, the list will be:

-59, 10, 511, 831, -982
-59, 511, 10, 831, -932
-982, 10, -59, 511, 831
-982, -59, 10, 511, 831

11 Consider the list: 10, -59, 511, 831, -982
After the fourth pass, the list will be:

-982, -59, 10, 511, 831
-59, 10, 511, 831, -982
-59, 10, 511, 831, -932
-982, 10, -59, 511, 831

12 Consider the list: -365, -894, 638, 678, -41
How many passes are required before the algorithm terminates?

Three
Five
Four
Two


References[edit]

Insertion Sort (Wikipedia)