Insertion Sort

Insertion sort constructs a sorted array incrementally. It takes one element from the input data and finds its correct position within the sorted list, repeating until no elements remain.

Simple Insertion Sort

For each element at index i (from 1 to n-1), the algorithm compares it with the elements in the sorted subarray [0..i-1] and inserts it into its correct position.

Implementation

void insertionSort(int arr[], int size) {
    for (int i = 1; i < size; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Properties

• Time Complexity: O(n²) in the worst and average cases, O(n) in the best case.
• Space Complexity: O(1).
• Stability: Stable.

Shell Sort

Shell sort is an optimization of insertion sort that sorts elements at specific intervals (gaps) to make the array partially sorted, followed by a final insertion sort.

Aglorithm

1. Initialize the gap size, typically set to half the array length.
2. Perform an insertion sort on elements separated by the gap.
3. Reduce the gap and repeat untill the gap is 1, which performs a standard insertion sort on a nearly sorted aray.

Implementation

void shellSort(int arr[], int size) {
    int gap = size;
    while (gap > 1) {
        gap = gap / 3 + 1;
        for (int i = gap; i < size; i++) {
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

Properties

• Time Complexity: Varies by gap sequence; approximately O(n log² n) or O(n^(3/2)).
• Space Complexity: O(1).
• Stability: Not stable.