Insertion Sort

Code

void insertionSort(int n, vector<int> &arr){
    // Loop through the array starting from the second element
    for(int i = 1; i < n; i++) {
        int temp = arr[i];  // Current element to be placed in its correct position
        int j = i - 1;      // Index of the previous element
        // Shift elements of the sorted part of the array to the right until the correct position for temp is found
        for(; j >= 0; j--) {
            // If the current element is greater than temp, shift it to the right
            if(arr[j] > temp) {
                arr[j+1] = arr[j];
            }
            else {
                // If the current element is smaller or equal, stop shifting
                break;
            }
        }

        // Place the current element (temp) in the correct position in the sorted part
        arr[j+1] = temp;
    }
}

Example:

vector<int> arr = {5, 2, 9, 1, 5, 6};
int n = 6;

Step-by-Step Execution:

1. Initial Array:
   arr[] = {5, 2, 9, 1, 5, 6}.

2. Outer Loop (i = 1):

   • temp = arr[1] = 2.
   • Compare arr[0] (5) with temp (2) → 5 > 2, so shift 5 to the right.
   • Place 2 in the correct position (arr[0]).
   • Array after Round 1: arr[] = {2, 5, 9, 1, 5, 6}.

3. Outer Loop (i = 2):

   • temp = arr[2] = 9.
   • Compare arr[1] (5) with temp (9) → 5 < 9, so no shifting required.
   • 9 stays in its place.
   • Array after Round 2: arr[] = {2, 5, 9, 1, 5, 6}.

4. Outer Loop (i = 3):

   • temp = arr[3] = 1.
   • Compare arr[2] (9) with temp (1) → 9 > 1, so shift 9 to the right.
   • Compare arr[1] (5) with temp (1) → 5 > 1, so shift 5 to the right.
   • Compare arr[0] (2) with temp (1) → 2 > 1, so shift 2 to the right.
   • Place 1 in the correct position (arr[0]).
   • Array after Round 3: arr[] = {1, 2, 5, 9, 5, 6}.

5. Outer Loop (i = 4):

   • temp = arr[4] = 5.
   • Compare arr[3] (9) with temp (5) → 9 > 5, so shift 9 to the right.
   • Compare arr[2] (5) with temp (5) → 5 = 5, so no more shifting required.
   • Place 5 in its correct position (arr[3]).
   • Array after Round 4: arr[] = {1, 2, 5, 5, 9, 6}.

6. Outer Loop (i = 5):

   • temp = arr[5] = 6.
   • Compare arr[4] (9) with temp (6) → 9 > 6, so shift 9 to the right.
   • Compare arr[3] (5) with temp (6) → 5 < 6, so no more shifting required.
   • Place 6 in its correct position (arr[4]).
   • Array after Round 5: arr[] = {1, 2, 5, 5, 6, 9}.

Final Sorted Array:

• After sorting, the array is:
  arr[] = {1, 2, 5, 5, 6, 9}.