Sortowanie przez wstawianie
Sortowanie przez wstawianie (ang. insertion sort) – prosty algorytm sortowania polegający na wstawianiu kolejnych elementów ciągu we właściwe miejsca. Złożoności czasowa algorytmu wynosi O(n2). Jest to algorytm realizujący metodę przyrostową.
Działanie algorytmu
Sortowany ciąg dzielony jest na część posortowaną i nieposortowaną. Na początku w części posortowanej znajduje się tylko jeden element (pierwszy). W każdym kolejnym kroku bierzemy pierwszy element z części nieposortowanej i wstawiamy we właściwe miejsce części posortowanej. Aby to zrobić, wstawiany element porównujemy kolejno z ostatnim elementem posortowanej części ciągu, z przedostatnim itd. Algorytm kończy się, gdy wszystkie elementy znajdują się w części posortowanej.
Przykładowy kod źródłowy w języku C jest umieszczony poniżej. Kod ten realizuje sortowanie rosnące.
void sortowanie_przez_wstawianie(int* tab, int n)
{
int i, j, t;
for (i = 1; i < n; ++i)
{
j = i;
while ( (j > 0) && (tab[j-1] > tab[j]) )
{
t = tab[j];
tab[j] = tab[j-1];
tab[j-1] = t;
--j;
}
}
}
Złożoność czasowa
Główna pętla algorytmu wykona się n-1 razy (n jest liczbą elementów do posortowania). W każdym wykonaniu pętli głównej wystąpi od 1 do j porównań, gdzie j jest numerem aktualnego wykonania pętli. W przypadku pesymistycznym algorytm wykona 1+…+(n-1)+(n-2)=(n-1)*n/2 porównań, czyli tyle samo, co algorytm sortowania bąbelkowego. Jednak w przypadku optymistycznym (sortowanie posortowanego ciągu) w każdym wykonaniu pętli głównej odbędzie się tylko jedno porównanie, co daje łącznie jedynie n-1 porównań (złożoność optymistyczna jest zatem liniowa).
Policzmy teraz, jaka jest średnia złożoność algorytmu. Jak już wspomniano, w każdym wykonaniu pętli głównej wystąpi od 1 do j porównań. Zakładając, że każda z tych liczb jest tak samo prawdopodobna, średnia liczba porównań wynosi (j+1)/2. W całym algorytmie wystąpi zatem (1+1)/2+(2+1)/2+…+n/2 porównań, czyli (n-1)(n+2)/4. Nadal jest to złożoność kwadratowa, jednak jest to algorytm szybszy od sortowania bąbelkowego. Przewaga sortowania przez proste wstawianie będzie tym większa, im większe będzie prawdopodobieństwo, że elementy w ciągu już na początku są częściowo posortowane.
Liczba głosów: 22.
- Bogosort
- Quicksort
- Sortowanie bąbelkowe
- Sortowanie przez scalanie
- Sortowanie przez wstawianie
Dodano: 29 września 2016 11:53, ostatnia edycja: 28 czerwca 2017 15:19.
Zobacz też
Rekurencja (inaczej rekursja) – odwołanie się funkcji lub definicji do samej siebie. Mówiąc inaczej, podejście rekurencyjne polega na tym, że rozwiązanie problemu wyraża się za pomocą rozwiązania tego samego problemu dla mniejszych danych wejściowych. Stosowanie rekurencji jest charakterystyczne dla algorytmów projektowanych metodą dziel i zwyciężaj.
Typowym problemem, dla którego można zastosować rekurencję, jest obliczanie silni. Przypomnijmy, że silnia z n jest zdefiniowana jako n!=1×2×…×n. Funkcja ta może być równoważnie zapisana jako:
n!=(n−1)!×n, dla n>0,
n!=1, dla n=0.
W powyższym przykładzie górny wiersz jest ogólnym równaniem rekurencji, zaś dolny wiersz jest wartością brzegową. W języku C++ powyższa funkcja byłaby zapisana w poniższy sposób.
int silnia(int n)
{
if (n > 0)
{
return n * silnia(n-1);
}
else
{
return 1;
}
};
Przekształcenie postaci rekurencyjnej funkcji do postaci zwartej (tzn. takiej, która nie zawiera odwołania do samej siebie) jest określane jako rozwiązanie rekurencji. Metody rozwiązywania rekurencji są dostępne między innymi w książkach podanych w bibliografii.
Algorytmy stosujące rekurencję są zazwyczaj proste w implementacji. Jednocześnie wiążą się one z pewnymi problemami. Przy podejściu rekurencyjnym ta sama funkcja jest wywoływana wielokrotnie, co zużywa pamięć operacyjną (w skrajnych przypadkach może to spowodować przepełnienie stosu).
Powtarzalny algorytm najbliższego sąsiada (ang. repetitive nearest neighbour algorithm, w skrócie RNN) – algorytm służący do rozwiązywania problemu komiwojażera korzystający z algorytmu najbliższego sąsiada.
Algorytm polega na wielokrotnym wykonaniu algorytmu najbliższego sąsiada w taki sposób, aby każdy wierzchołek raz był wierzchołkiem początkowym. Następnie algorytm zwraca najlepsze spośród otrzymanych rozwiązań.
Dla grafu pełnego algorytm ma złożoność O(n3), gdzie n jest liczbą wierzchołków. W trakcie wykonywania algorytmu RNN n razy zostanie wykonany algorytm najbliższego sąsiada, który ma złożoność czasową O(n2).
Algorytm RNN nie daje gwarancji znalezienia rozwiązania optymalnego. W odróżnieniu od algorytmu najbliższego sąsiada daje jednak gwarancję, że zwróci rozwiązanie co najmniej tak dobre, jak n/2-1 innych rozwiązań (dowód i więcej informacji na ten temat znajduje się w pracy podanej w bibliografii).