Insertion sort

Introduction:

In the world of computer science and programming, sorting algorithms play a crucial role in organizing data efficiently. One such algorithm is Insertion Sort. This article will delve into the concept of Insertion Sort, its implementation, and provide code examples in popular programming languages such as C#, JavaScript, Python, and PHP.

Understanding Insertion Sort:

Insertion Sort is a simple yet efficient sorting algorithm that works by building a sorted array or list one item at a time. It is based on the idea of dividing the input into two parts: the sorted part and the unsorted part. Initially, the sorted part consists of only the first element, and the unsorted part includes the remaining elements.
The algorithm iterates through the unsorted part, comparing each element with the elements in the sorted part. It finds the correct position for the current element in the sorted part and shifts the larger elements to the right to make space for the insertion. This process continues until all elements are sorted.

Advantages and Applications of Insertion Sort:

The simplicity and efficiency of Insertion Sort make it a popular choice for sorting small to medium-sized data sets. It has several advantages:

Simplicity: Insertion Sort is easy to understand and implement, making it suitable for beginners.

Efficiency: In the best-case scenario, when the input is already sorted, Insertion Sort has a time complexity of O(n). In the average and worst cases, it has a time complexity of O(n^2). However, for small inputs, it performs efficiently.

Adaptive: Insertion Sort performs well for partially sorted or nearly sorted inputs. It requires fewer comparisons and swaps, making it adaptive to the data.

In-place Sorting: Insertion Sort sorts the input array in-place, without requiring additional memory space.

Links

Code Examples

C#
public static void InsertionSort(int[] array)
{
    int n = array.Length;
    for (int i = 1; i < n; i++)
    {
        int key = array[i];
        int j = i - 1;

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

        array[j + 1] = key;
    }
}

JavaScript
function insertionSort(array) {
    let n = array.length;
    for (let i = 1; i < n; i++) {
        let key = array[i];
        let j = i - 1;

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

        array[j + 1] = key;
    }
}

Python
def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        key = array[i]
        j = i - 1

        while j >= 0 and array[j] > key:
            array[j + 1] = array[j]
            j -= 1

        array[j + 1] = key

PHP
function insertionSort(&$array)
{
    $n = count($array);
    for ($i = 1; $i < $n; $i++) {
        $key = $array[$i];
        $j = $i - 1;

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

        $array[$j + 1] = $key;
    }
}

Conclusion