SESO42 - Editorial

editorial
, ,
1

Problem Link

The Insertion Sort algorithm works by iterating through the array and, for each element, inserting it into the correct position relative to the already sorted portion of the array. The process can be described as follows:

  1. Outer Loop: The algorithm starts with the second element (index 1) because the single element at index 0 is trivially sorted. The outer loop iterates from the second element to the last element in the array.

  2. Key Element: For each iteration of the outer loop, the current element (arr[i]) is considered the “key” element. This key element needs to be placed in the correct position within the sorted portion of the array (i.e., the part of the array before index i).

  3. Inner Loop: The inner loop scans the sorted portion of the array from right to left, comparing each element with the key. If an element is greater than the key, it is shifted one position to the right. This continues until the correct position for the key is found.

  4. Insertion: Once the correct position is found (i.e., when no more elements in the sorted portion are greater than the key), the key is inserted into its correct position.

  5. Repeat: The process is repeated for each element in the array, progressively growing the sorted portion until the entire array is sorted.

Code Explanation

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // Store the current element as key
        int j = i - 1;
        
        // Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // Insert the key at its correct position
        arr[j + 1] = key;
    }
}

How It Works

  • Initial Step: The algorithm starts by assuming that the first element is sorted by default. It then takes the second element as the key and compares it with the elements in the sorted portion to find its correct position.
  • Shifting: Elements in the sorted portion that are greater than the key are shifted to the right to make room for the key.
  • Insertion: The key is inserted into the correct position, extending the sorted portion of the array by one element.

Complexity Analysis

  • Time Complexity: The time complexity of Insertion Sort in the worst and average cases is O(n^2), where n is the number of elements in the array. This occurs when the array is sorted in reverse order. However, in the best case, when the array is already sorted, the time complexity is O(n) because the inner loop does not perform any shifts.

  • Space Complexity: The space complexity is O(1), as Insertion Sort is an in-place sorting algorithm that requires only a constant amount of additional memory beyond the input array.