Сортировка вставками

Этот вид сортировки заключается в следущем.

Делим массив на две части: слева отсортированная часть, где изначально находится один элемент, и справа — неотсортированная.

Проходим в цикле элементы неотсортированной части и ищем место для очередного элемента путем сравнения его с предыдущим. Если текущий элемент меньше — сдвигаем элементы вправо, и так, пока не найдем место для него или пока не дойдем до нулевого элемента массива.

Как только нашли место и сдвинули элементы, ставим текущий элемент на свое место. Потом шаги повторяются до тех пор, пока не отсортируем весь массив.

Асимптотическая сложность алгоритма — O(N²).

Далее приводится реализация алгоритма на нескольких языках программирования.

#include <stdio.h>
#include <stdlib.h>


int arr[] = { 12,5,4,9,8,10,0,2,1,3, -1 };

void selection_sort(int ar[], int length)
{
	int min, minIndex, i;
	min = 0;
	minIndex = 0;

	for (i = 0; i < length - 1; i++) {
		min = ar[i];
		minIndex = i;
		for (int j = i + 1; j < length; j++) {
			if (ar[j] < min) {
				min = ar[j];
				minIndex = j;
			}
		}

		if (i != minIndex) {
			ar[minIndex] = ar[i];
			ar[i] = min;
		}
	}
}

void show(const int ar[], int length)
{
	for (int i = 0; i < length; i++)
		printf("%d ", ar[i]);
	puts("\n========================\n");
}

int main(void)
{
	int length = sizeof(arr) / sizeof(*arr);

	show("Array: ", arr, length);

	selection_sort(arr, length);

	show("Sorted array: ", arr, length);

	return 0;
}

internal class Program
{
    // O(N2)
    static void InsertionSort(T[] arr) where T:IComparable
    {
        int length = arr.Length;
        
        for(int i=1; i<length; i++) { 
            T temp = arr[i]; int j = i;  
            while(j > 0 && temp.CompareTo(arr[j-1])==-1) 
            {
                arr[j]=arr[j-1];
                j--;
            }

            arr[j] = temp;
        }
    }

    static void Main(string[] args)
    {
        int[] arr = { 12, 5, 4, 9, 8, 10, 0, 2, 1, 3 };
        
        Console.WriteLine($"Array: {string.Join(" ", arr)}");

        InsertionSort(arr);

        Console.WriteLine($"Sorted array: {string.Join(" ", arr)}");

        Console.ReadKey();
    }
}

<?php
function InsertionSort(array &$arr): void
{
    $length=count($arr);
    
    for($i=1; $i<$length; $i++) { $temp=$arr[$i]; $j=$i-1; while($j>=0 && $temp<$arr[$j]) {
            $arr[$j+1]=$arr[$j];
            $j--;
        }
        $arr[$j+1]=$temp;
    }
}

function InsertionSort(arr) 
{
    if (Array.isArray(arr)) {
        const len=arr.length;
        let temp;

        for(let i=1; i<len; i++) { temp=arr[i]; let j=i-1; while(j>=0 && temp<arr[j]) {
                arr[j+1]=arr[j];
                j--;
            }

            arr[j+1]=temp;
        }
    }
    else {
        throw new Error("Argument must be of type Array");
    }
}