Sortowanie przez wstawianie (ang. insertion sort)

[algorytm] Opis działania algorytmu sortowania przez wstawianie wraz z kodem źródłowym.

Złożoność czasowa: O(n²)

Najpierw bierzemy dowolny element ze zbioru nieposortowanego. Następnie porównujemy go z kolejnymi elementami zbioru posortowanego, aż nie napotkamy elementu równego lub większego, bądź nie znajdziemy się na początku/końcu zbioru posortowanego. Wyciągnięty element wstawiamy na miejsce gdzie skończyliśmy porównywać.

void Sortowanie( int tab[], int size )
{
int temp, j;

for( int i = 1; i < size; i++ )
{
temp = tab[ i ];

for( j = i - 1; j >= 0 && tab[ j ] > temp; j-- )
tab[ j + 1 ] = tab[ j ];

tab[ j + 1 ] = temp;
}
}

Więcej informacji: http://pl.wikipedia.org/wiki/Sortowanie_przez_wstawianie

Wszystkie teksty są chronione prawami autorskimi. Kopiowanie lub rozpowszechnianie treści poza niniejszym serwisem jest zabronione.

Powyższe ograniczenie nie dotyczy autora opracowania, któremu przysługuje prawo do rozpowszechniania własnego tekstu wedle własnego uznania.