Сортування включенням

Сортування включенням

Клас	Алгоритм сортування
Структура даних	Масив
Найгірша швидкодія	О(n2)
Найкраща швидкодія	О(n)
Середня швидкодія	О(n2)
Просторова складність у найгіршому випадку	О(n), O(1)
Оптимальний	Переважно ні

Сортування включенням — простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг:

• простота у реалізації
• ефективний (за звичай) на маленьких масивах
• ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна O(n + d), де d — кількість інверсій
• на практиці ефективніший за більшість інших квадратичних алгоритмів (O(n²)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n²/4, і в найкращому випадку є лінійною
• є стабільним алгоритмом

Наприклад, більшість людей при сортуванні колоди гральних карт, використовують метод, схожий на алгоритм сортування включенням.

Приклад сортування включенням. Елементи в чорних рамках — посортована частина списку. Метод порівнює наступний елемент непосортованої частини (червона рамка) з послідовними елементами посортованої та вставляє у потрібне місце.

Приклади реалізації

C

void insertSort(int a[], size_t length) {
    int i, j, value;
 
    for(i = 1; i < length; i++) {
        value = a[i];
        for (j = i - 1; j >= 0 && a[j] > value; j--) {
            a[j + 1] = a[j];
        }
        a[j + 1] = value;
    }
}

C#

static void InsertSort(IComparable[] array)
{
    int i, j;
 
    for (i = 1; i < array.Length; i++)
    {
        IComparable value = array[i];
        j = i - 1;
        while ((j >= 0) && (array[j].CompareTo(value) > 0))
        {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = value;
    }
}

C# 2.0

static void InsertSort<T>(IList<T> list) where T : IComparable<T>
{
    int i, j;
 
    for (i = 1; i < list.Count; i++)
    {
        T value = list[i];
        j = i - 1;
        while ((j >= 0) && (list[j].CompareTo(value) > 0))
        {
            list[j + 1] = list[j];
            j--;
        }
        list[j + 1] = value;
    }
}

Java

public static int[] insertionsort(int[] numbers) {
    for (int i = 0; i < numbers.length; i++) {
        int copyNumber = numbers[i];
        int j = i;
        while (j > 0 && copyNumber < numbers[j-1]) {
            numbers[j] = numbers[j-1];
            j--;
        }
        numbers[j] = copyNumber;
    }
    return numbers;
}

Pascal

const n=1000;
type ArType=array[1..n] of integer;
procedure insertsort(var a: artype);
var i,j,x: integer;
begin
    for i:=2 to n do
    begin
        x:=a[i];
        j:=i-1;
        while (j>0) and (x<a[j]) do
        begin
            a[j+1]:=a[j];
            j:=j-1;
        end;
        a[j+1]:=x;
    end;
end;

PHP

for($j=1; $j < count($array); $j++){
    $temp = $array[$j];
    $i = $j;
    while(($i >= 0) && ($array[$i-1] > $temp)){
       $array[$i] = $array[$i-1];
       $i--;
    }
    $array[$i] = $temp;
}

Python

def insertsort(array):
    for removed_index in range(1, len(array)):
        removed_value = array[removed_index]
        insert_index = removed_index
        while insert_index > 0 and array[insert_index - 1] > removed_value:
            array[insert_index] = array[insert_index - 1]
            insert_index = insert_index - 1
        array[insert_index] = removed_value

Ruby

def insert_sort!(list)
    for i in 1..(list.length - 1)
        value = list[i]
        j = i - 1
        while j >= 0 and list[j] > value
            list[j + 1] = list[j] 
            j -= 1
        end
        list[j + 1] = value
    end
end

NASM

Прототип функції на мові С:

void isort(int *a, int n)

Її реалізація на Assembler:

isort:
 %define a [ebp + 8]
 %define n [ebp + 12]
 enter 0, 0
 pusha
 mov ecx, 1
 for:
   mov ebx, ecx
   imul ebx, 4
   add ebx, a
   mov ebx, [ebx]
   mov edx, ecx
   dec edx
   while:
     cmp edx, 0
     jl while_quit
     mov eax, edx
     imul eax, 4
     add eax, a
     cmp ebx, [eax]
     jge while_quit
     mov esi, [eax]
     mov dword [eax + 4], esi
     dec edx
     jmp while
   while_quit:
   mov [eax], ebx
   inc ecx
   cmp ecx, n
   jl for
 popa
 leave
 ret

Джерела інформації

• Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1

Див. також

• Список алгоритмів.

Посилання

• Animated Sorting Algorithms: Insertion Sort — графічна демонстрація роботи алгоритму
• Category:Insertion Sort — LiteratePrograms — приклади реалізації алгоритму на різних мовах програмування
• InsertionSort
• Insertion Sort Demonstration
• Sorting Algorithms Demo
• TIDE 2.0 beta
• Sorting Algorithms in Turkish