Insertion Sort

Straight Insertion Sort

algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists. However, it has the advantage of being simple and adaptable, making it efficient for small datasets.

T(C) = O(n^2) where as Space Taken is constant as it sorts in place.

Steps:

1. Start with the second element (assuming the first element is sorted).
2. Compare the current element with the elements in the sorted portion and shift all the elements greater than the current element to the right.
3. Insert the current element into its correct position.
4. Repeat the process for all elements in the array.

Code:

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        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 = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    cout << "Sorted array: \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Special Points

1. Simplicity: Easy to implement and understand.
2. Stable: Maintains the relative order of equal elements.
3. In-Place Sorting: Does not require extra memory.
4. Efficient for Small Datasets: Performs well for small or nearly sorted datasets.

SHell Sort

It sorts elements at a specific interval first and gradually reduces the interval until it performs a final pass using insertion sort.

Passes:

Initial Array: [12, 34, 54, 2, 3]

Pass 1: Gap = 2
Elements Compared: [12, 54], [34, 2], [54, 3]

Reordering:
Compare and swap 12 and 54: [12, 34, 54, 2, 3]
Compare and swap 34 and 2: [12, 2, 54, 34, 3]
Compare and swap 54 and 3: [12, 2, 3, 34, 54]

Array after Pass 1: [12, 2, 3, 34, 54]

Pass 2: Gap = 1

Reordering:
Compare and swap 12 and 2: [2, 12, 3, 34, 54]
Compare and swap 12 and 3: [2, 3, 12, 34, 54]
No further swaps needed as array is already sorted

Array after Pass 2: [2, 3, 12, 34, 54]

#include <iostream>
using namespace std;

void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

int main() {
    int arr[] = {12, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    shellSort(arr, n);
    cout << "Sorted array: \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Performs Better than Insertion Sort // Unstable