algorithm => Insättningssortering

Anmärkningar

När vi analyserar prestanda för sorteringsalgoritmen, intresserar vi främst antalet jämförelser och utbyten.

Genomsnittligt utbyte

Låt E _n vara det totala genomsnittliga antalet utbyten för att sortera array av N-element. E ₁ = 0 (vi behöver inget utbyte mot matris med ett element). Det genomsnittliga antalet utbyten för att sortera N-element-array är summan av det genomsnittliga antalet utbyten för att sortera N-1-elementarray med det genomsnittliga utbytet för att infoga det sista elementet i N-1-elementarray.

Förenkla summeringen (aritmetiska serier)

Utökar termen

Förenkla summeringen igen (aritmetiska serier)

Genomsnittlig jämförelse

Låt _Cn vara det totala genomsnittliga antalet jämförelse med sorts matris med N element. C ₁ = 0 (vi behöver ingen jämförelse på en elementarray). Det genomsnittliga antalet jämförelser för att sortera N-elementarray är summan av det genomsnittliga antalet jämförelser för att sortera N-1-elementarray med den genomsnittliga jämförelsen för att infoga det sista elementet i N-1-elementarrayen. Om det sista elementet är det största elementet behöver vi bara en jämförelse, om det sista elementet är det andra minsta elementet behöver vi N-1-jämförelse. Men om det sista elementet är det minsta elementet behöver vi inte N-jämförelse. Vi behöver fortfarande bara N-1 jämförelse. Det är därför vi tar bort 1 / N under ekvationen.

Förenkla summeringen (aritmetiska serier)

Utöka termen

Förenkla summeringen igen (aritmetiska serier och harmoniskt nummer)

Grundläggande om algoritmer

Insertion sort är en mycket enkel, stabil, på plats placeringsalgoritm. Det fungerar bra på små sekvenser men det är mycket mindre effektivt på stora listor. Vid varje steg beaktar algoritmerna det i-te elementet i den givna sekvensen och flyttar det till vänster tills det är i rätt position.

Grafisk illustration

pseudo

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

Exempel

Tänk på följande lista med heltal:

[5, 2, 4, 6, 1, 3]

Algoritmen kommer att utföra följande steg:

[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 # Implementering

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;
    }
}

Hjälprum: O(1)
Tidskomplexitet: O(n)

Haskell-implementering

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

Modified text is an extract of the original Stack Overflow Documentation

Licensierat under CC BY-SA 3.0

Inte anslutet till Stack Overflow

algorithm
Insättningssortering

Sök…