Sorting Visualization

DESCRIPTION

Insertion Sort is a straightforward sorting algorithm that builds the final sorted array one element at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

In Insertion Sort algorithm:

Start with 2^nd element of the array, as 1^st element is assumed to be sorted.
Compare 2^nd element with 1^st element. If 2^nd element is smaller, swap them.
Move to 3^rd element & compare it with 2^nd element, then 1^st element, and swap as needed to ensure it's positioned correctly among the first three elements.
Continue comparing each element with preceding ones, swapping as necessary to maintain its correct position within the sorted portion of the array.
Repeat until the entire array is sorted.

Advantages	Disadvantages
Simple and easy to understand. Stable sorting algorithm. Efficient for small lists and nearly sorted lists. Space-efficient.	Inefficient for large lists. Not as efficient as other sorting algorithms (e.g., merge sort, quick sort) for most cases.

COMPLEXITY

Worst Case	O(n²)
Best Case	O(n)
Average Case	O(n²)
Space Complexity	O(1)

IMPLEMENTATIONS

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

void insertionSort(int arr[]) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

void sort(int[] arr) {
    int n = arr.Length;
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        
        j = i-1
        while j >= 0 and key < arr[j] :
                arr[j + 1] = arr[j]
                j -= 1
        arr[j + 1] = key

function insertionSort(&$arr, $n) {
    for ($i = 1; $i < $n; $i++)     {
        $key = $arr[$i];
        $j = $i-1;
    
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j = $j - 1;
        }
        
        $arr[$j + 1] = $key;
    }
}