Tutorial: Sortowanie przez wstawianie

Aby korzystać z tej strony musisz mieć włączoną obsługę JavaScript.
Ocena: +2 Tak Nie
Liczba głosów: 2.

Tutorial pokazujący krok po kroku, jak działa sortowanie przez wstawianie. Ten samouczek jest powiązany tematycznie z artykułem „Sortowanie przez wstawianie”.

Dodano: 27 lutego 2017 17:04.

Zobacz też wszystkie nasze tutoriale!
REKLAMA

Zobacz też

Algorytm najbliższego sąsiada (ang. nearest neighbour algorithm, w skrócie NN) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm wykorzystujący strategię zachłanną.
→ Czytaj całość

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ą.

→ Czytaj całość

Wyznaczanie najkrótszej ścieżki – zagadnienie polegające na wyszkaniu w grafie takiej ścieżki łączącej dwa wierzchołki, której suma wag krawędzi jest jak najmniejsza.

W przypadku pesymistycznym do wyznaczenia optymalnej ścieżki z wierzchołka A do wierzchołka B konieczne jest wyznaczenie najkrótszych ścieżek z wierzchołka A do wszystkich pozostałych wierzchołków w grafie. Zagadnienie takie jest określane jako poszukiwanie najkrótszych ścieżek z jednego źródła. Do rozwiązywania tego zagadnienia można wykorzystać następujące algorytmy:

Nieco innym zagadnieniem jest poszukiwanie najkrótszych ścieżek pomiędzy każdą parą wierzchołków. W tym celu można wykorzystać algorytmy wymienione powyżej (wykonując je wielokrotnie, za każdym razem przyjmując inny wierzchołek źródłowy) lub algorytmy poszukujące od razu wszystkich ścieżek, takie jak:

Aby znalezienie najkrótszej ścieżki było możliwe, graf nie może zawierać ujemnych cykli osiągalnych z wierzchołka źródłowego. Jeśli taki cykl istnieje, to poruszając się nim „w kółko” cały czas zmniejszamy długość ścieżki. Dopuszczalne jest natomiast występowanie krawędzi o ujemnej wadze, choć nie wszystkie algorytmy dopuszczają ten przypadek.

Jeśli poszukujemy ścieżek o najmniejszej liczbie krawędzi (np. wtedy, gdy wszystkie krawędzie mają taką samą, dodatnią wagę), to zamiast powyższych algorytmów możemy skorzystać z prostego przeszukiwania grafu wszerz.

→ Czytaj całość
Polityka prywatnościKontakt