Sortowanie przez wybór

Autor podstrony: Krzysztof Zajączkowski

Stronę tą wyświetlono już: 3965 razy

Sortowanie przez wybór może odbywać się bez konieczności deklarowania dodatkowej pamięci. Jego zasada jest prosta dla elementów od i = 0 do ik, gdzie k - to nic innego jak liczba elementów sortowanej tablicy w danym kroku szukam najmniejszej wartości i podmieniam ją z i-tym elementem tablicy. Następnie zaczynam od nowa tę samą procedurę zwiększając indeks początkowy i o 1 aż do momentu, gdy ik - 1.

Przykładowa animacja zasady działania sortowania przez wybór została pokazana poniżej. Animacja wykonywana jest za sprawą skryptu JavaScript z wykorzystaniem klasy tworzącej wykres słupkowej opisanej na stronie Programowanie → Projekty JavaScript → Skrypt JavaScript tworzący wykres słupkowy.

Rys. 1
Animacja algorytmu sortowania przez wstawianie. Kolory użyte w animacji oznaczają:
  • czerwony - najmniejszy element znaleziony w danym wycinku tablicy;
  • niebieski - element porównywany, który okazał się większy od aktualnie najmniejszego;
  • pomarańczowy - pierwszy element wycinka tablicy, który początkowo jest czerwony;
  • zielony - pozostałe elementy tablicy

Ten algorytm zawsze wymaga wykonania n - 1 wyszukiwań minimalnej wartości, natomiast liczba operacji porównania, jaką algorytm wykonuje wynosi zawsze:

złożoność obliczeniowa implementacji algorytmu sortowania bombelkowego [1]

Zapis wyrażenia w formacie TeX-a:

\frac{1}{2}\cdot n\cdot (n-1)
Propozycje książek