algorithm
Invoegsortering
Zoeken…
Opmerkingen
Wanneer we de prestaties van het sorteeralgoritme analyseren, zijn we vooral geïnteresseerd in het aantal vergelijkingen en uitwisselingen.
Gemiddelde uitwisseling
Laat E n als totale gemiddelde aantal uitwisseling sort reeks N element. E 1 = 0 (we hebben geen uitwisseling nodig voor array met één element). Het gemiddelde aantal uitwisselingen voor het sorteren van de N-elementenreeks is de som van het gemiddelde aantal uitwisselingen voor het sorteren van de N-1-elementenreeks met de gemiddelde uitwisseling om het laatste element in de N-1-elementenreeks in te voegen.
Vereenvoudig de sommatie (rekenkundige reeks)
Verlengt de termijn
Vereenvoudig de sommatie opnieuw (rekenkundige reeks)
Gemiddelde vergelijking
Laat C n het totale gemiddelde aantal vergelijkingen zijn voor de sorteermatrix van het N-element. C 1 = 0 (we hebben geen vergelijking nodig voor één elementmatrix). Het gemiddelde aantal vergelijkingen voor het sorteren van de N-reeks elementen is de som van het gemiddelde aantal vergelijkingen voor het sorteren van de N-1-elementenreeks met de gemiddelde vergelijking om het laatste element in de N-1-elementenreeks in te voegen. Als het laatste element het grootste element is, hebben we slechts één vergelijking nodig, als het laatste element het op een na kleinste element is, hebben we een N-1-vergelijking nodig. Als het laatste element echter het kleinste element is, hebben we geen N-vergelijking nodig. We hebben nog steeds alleen N-1-vergelijking nodig. Daarom verwijderen we 1 / N in onderstaande vergelijking.
Vereenvoudig de sommatie (rekenkundige reeks)
Vouw de term uit
Vereenvoudig de sommatie opnieuw (rekenkundige reeks en harmonisch nummer)
Algoritme Basics
Invoegsortering is een zeer eenvoudig, stabiel sorteeralgoritme. Het presteert goed op kleine reeksen, maar het is veel minder efficiënt op grote lijsten. Bij elke stap houden de algoritmen rekening met het i-de element van de gegeven reeks en verplaatsen het naar links totdat het in de juiste positie staat.
Grafische illustratie
pseudocode
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
Voorbeeld
Overweeg de volgende lijst met gehele getallen:
[5, 2, 4, 6, 1, 3]
Het algoritme voert de volgende stappen uit:
-
[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]
C # Implementatie
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;
}
}
Hulpruimte: O(1)
Tijd Complexiteit: O(n)
Haskell-implementatie
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