algorithm => Inserimento Ordina

Osservazioni

Quando analizziamo le prestazioni dell'algoritmo di ordinamento, ci interessa principalmente il numero di confronto e scambio.

Scambio medio

Sia E _n il numero medio totale di scambi per ordinare un array di elementi N. E ₁ = 0 (non è necessario alcun scambio per array con un elemento). Il numero medio di scambi per ordinare l'array di elementi N è la somma del numero medio di scambi per ordinare l'array di elementi N-1 con lo scambio medio per inserire l'ultimo elemento nell'array di elementi N-1.

Semplificare la somma (serie aritmetiche)

Espande il termine

Semplifica nuovamente la somma (serie aritmetiche)

Confronto medio

Sia C _n il numero medio totale di confronti per ordinare un array di elementi N. C ₁ = 0 (non è necessario alcun confronto su un array di elementi). Il numero medio di confronto per ordinare l'array di elementi N è la somma del numero medio di numeri di confronto per ordinare l'array di elementi N-1 con il confronto medio per inserire l'ultimo elemento nell'array di elementi N-1. Se l'ultimo elemento è l'elemento più grande, abbiamo bisogno di un solo confronto, se l'ultimo elemento è il secondo elemento più piccolo, abbiamo bisogno del confronto N-1. Tuttavia, se l'ultimo elemento è l'elemento più piccolo, non è necessario il confronto N. Abbiamo ancora solo bisogno del confronto N-1. Questo è il motivo per cui rimuoviamo 1 / N in sotto l'equazione.

Semplificare la somma (serie aritmetiche)

Espandi il termine

Semplifica nuovamente la somma (serie aritmetica e numero armonico)

Nozioni di base sugli algoritmi

Insertion sort è un algoritmo di ordinamento sul posto molto semplice, stabile e diretto. Funziona bene su piccole sequenze ma è molto meno efficiente su elenchi di grandi dimensioni. Ad ogni passo, gli algoritmi considerano l'elemento i-esimo della sequenza data, spostandolo verso sinistra finché non si trova nella posizione corretta.

Illustrazione grafica

pseudocodice

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

Esempio

Si consideri il seguente elenco di numeri interi:

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

L'algoritmo eseguirà i seguenti passaggi:

[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]

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

Spazio ausiliario: O(1)
Complessità del tempo: O(n)

Implementazione 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

Modified text is an extract of the original Stack Overflow Documentation

Autorizzato sotto CC BY-SA 3.0

Non affiliato con Stack Overflow

algorithm
Inserimento Ordina

Ricerca…