algorithm
Sortowanie przez wstawianie
Szukaj…
Uwagi
Analizując wydajność algorytmu sortowania, interesujemy się przede wszystkim liczbą porównań i wymian.
Średnia wymiana
Niech E n będzie całkowitą średnią liczbą wymiany do sortowania tablicy N elementu. E 1 = 0 (nie potrzebujemy wymiany na tablicę z jednym elementem). Średnia liczba wymiany do sortowania tablicy elementów N jest sumą średniej liczby wymiany do sortowania tablicy elementów N-1 ze średnią wymianą do wstawienia ostatniego elementu do tablicy elementów N-1.
Uprość sumowanie (szeregi arytmetyczne)
Rozszerza termin
Ponownie uprość sumowanie (szeregi arytmetyczne)
Średnie porównanie
Niech C n będzie całkowitą średnią liczbą porównań do tablicy sortowania elementu N. C 1 = 0 (nie potrzebujemy żadnego porównania na tablicy z jednym elementem). Średnia liczba porównań do tablicy elementów sortowania N jest sumą średniej liczby porównań do tablicy elementów sortowania N-1 ze średnim porównaniem do wstawienia ostatniego elementu do tablicy elementów N-1. Jeśli ostatni element jest największym elementem, potrzebujemy tylko jednego porównania, jeśli ostatni element jest drugim najmniejszym elementem, potrzebujemy porównania N-1. Jeśli jednak ostatni element jest najmniejszym elementem, nie potrzebujemy porównania N. Nadal potrzebujemy tylko porównania N-1. Dlatego usuwamy 1 / N w poniższym równaniu.
Uprość sumowanie (szeregi arytmetyczne)
Rozwiń ten termin
Ponownie uprość sumowanie (szeregi arytmetyczne i liczby harmoniczne)
Podstawy algorytmu
Sortowanie za pomocą wstawiania jest bardzo prostym, stabilnym algorytmem sortowania na miejscu. Działa dobrze na małych sekwencjach, ale jest znacznie mniej wydajny na dużych listach. Na każdym kroku algorytmy analizują i-ty element danej sekwencji, przesuwając go w lewo, aż znajdzie się we właściwej pozycji.
Ilustracja graficzna
Pseudo kod
for j = 1 to length(A)
n = A[j]
i = j - 1
while j > 0 and A[i] > n
A[i + 1] = A[i]
i = i - 1
A[i + 1] = n
Przykład
Rozważ następującą listę liczb całkowitych:
[5, 2, 4, 6, 1, 3]
Algorytm wykona następujące kroki:
-
[5, 2, 4, 6, 1, 3] -
[2, 5, 4, 6, 1, 3] -
[2, 4, 5, 6, 1, 3] -
[2, 4, 5, 6, 1, 3] -
[1, 2, 4, 5, 6, 3] -
[1, 2, 3, 4, 5, 6]
Implementacja C #
public class InsertionSort
{
public static void SortInsertion(int[] input, int n)
{
for (int i = 0; i < n; i++)
{
int x = input[i];
int j = i - 1;
while (j >= 0 && input[j] > x)
{
input[j + 1] = input[j];
j = j - 1;
}
input[j + 1] = x;
}
}
public static int[] Main(int[] input)
{
SortInsertion(input, input.Length);
return input;
}
}
Przestrzeń pomocnicza: O(1)
Złożoność czasu: O(n)
Wdrożenie Haskell
insertSort :: Ord a => [a] -> [a]
insertSort [] = []
insertSort (x:xs) = insert x (insertSort xs)
insert :: Ord a => a-> [a] -> [a]
insert n [] = [n]
insert n (x:xs) | n <= x = (n:x:xs)
| otherwise = x:insert n xs