Sortowanie przez scalanie
•Metoda sortowania przez scalanie zaliczana jest do algorytmów wykorzystujących porównania. Jednocześnie jednak jest to metoda wykorzystująca ‘’dziel i zwyciężaj’ .
W tej metodzie wyróżniamy dwa etapy:
PODZIAŁ
- Faza wykonywana jest rekurencyjnie , polega na podzieleniu ciągu na podciągi zawierające jedną wartość
SCALANIE
- realizowana jest podczas łączenia podciągów i polega na scalaniu ich, z jednoczesnym sortowaniem
Wynika stąd, że głównym celem jest tutaj scalenie dwóch uporządkowanych ciągów w jeden posortowany
***
Załóżmy, że w tablicy mamy dwa uporządkowane podciągi, które chcemy scalić. Kopiujemy pierwszy z lewej strony tablicy podciąg ( mający mniejsze indeksy!!! ) do dodatkowej tablicy. Następne porównujemy parami kolejne wyrazy podciągów i wstawiamy do tablicy te, które są mniejsze.
Sortowanie Szybkie
•Metoda sortowania szybkiego jest oparta na następującej własności: jeśli w tablicy T [0…n-1] istnieje element o indeksie k taki, że wszystkie elementy o mniejszych numerach mają wartość mniejszą od T [k], to aby uzyskać posortowany ciąg, wystarczy osobno posortować elementy tablicy T[0…k-1] i T[k+1…n-1]
W każdym kolejnym kroku...
•Powtarzane są te same czynności, zmienia się tylko fragment ciągu, na którym wykonujemy określone operacje. Indeks pierwszego wyrazu oznaczamy jako lewy, ostatniego – prawy.
•
Realizacje każdego
kroku algorytmu należy rozpocząć od wybrania wyrazu ŚRODKOWEGO , którego wartość wyznaczamy : srodek – T [(lewy+prawy/2].Znajdowanie wyrazów w ciągu do zmiany rozpoczynamy od wyrazów skrajnych : LEWY i PRAWY, a dalej przesuwamy się w stronę wyrazu środkowego SRODEK. Szukamy z lewej strony elementu T [i] mniejsze/równe srodek, a z prawej elementu T[j] większy/równy srodek. Po znalezieniu pary spełniającej podane warunki wykonujemy zamianę elementów T[i] z T[j]. Czynności te powtarzamy tak długo, aż indeksy I i J się spotkają, dochodząc z obsu stron do elementu srodek.
Zapraszam: Prezentacja - lekcja
Brak komentarzy:
Prześlij komentarz