Sortowania-Informatyka

Rodzaje Sortowania

START

Spis

Sortowanie

Strategiczne

Wybieranie

Kubełkowe

Wstawianie

Kopcowanie

Scalanie

Podziękowanie

1.

Sortowanie poprzez Wybieranie (Selekcje)

Sortowanie selekcyjne

Wizualizacja

Jak działa?

Zalety

• Liniowa złożoność algorytmu obliczeniowego
• Przykład: Rozpiętość liczb w Dużym Lotku wynosi (49-1) + 1 = 49

Wady

• Konieczna jest uprzednia znajomość zakresu danych
• Algorytm zakłada przymus złożoności pamięciowej

Implementacje

• Prosta- sortująca w miejscu, zakłada, że elementy o równych kluczach są nierozróżnialne, nie mogą zatem być to klucze danych (każdy z nich jest bowiem powiązany z przenoszoną wartością – zatem, mimo iż są one równe, muszą pozostawać rozróżnialne)

• Standardowa-gwarantuje stabilność i nie wymaga dodatkowego założenia. Potrzebuje natomiast O(n) dodatkowej pamięci.

2.

Sortowanie poprzez Wstawianie

Sortowanie porównywane do układania kart pokerzysty

Wizualizacja

Sposób działania

Strategia sortowania:

• Sortowanie zaczyna się od drugiego elementu tablicy
• Porównuje go z poprzedzającym, dostanie wykryta większa liczba to przesuwamy ją o jedno miejsce w prawo
• Czynność będzie się powtarzać do spotkania liczby niemniejszej lub w chwili zabraknięcia liczb
• W kolejnym kroku stawiamy liczbe w odpowiednie miejsce i otrzymujemy posortowny podzbiór
• Czynność powtarzamy dla każdego elementu

Zalety:

• Stabilność
• Bardzo dobre działanie w spotkaniu z zbiorem posortowanym lub częściowo posortowanego
• Prosty w implementacji
• Radzi sobie z niedużymi zbiorami

Wady:

• Ma problemy w kontakcie z większymi zbiorami
• Nieposortowane zbiory sprawiają problem

3.

Sortowanie poprzez Scalanie

Zasada "Dziel i zwyciężaj"

Wizualizacja

Sposób działania

• Znajdujemy środkowy wyraz m(reszta z dzielenia przez 2 zaokrąglamy w dół)

• Wywołujemy sortowanie przez scalanie dla podtablicy o indeksach od l do m

• Wywołaj sortowanie przez scalanie dla podtablicy o indeksach od m+1 do r

• Połącz podtablicę l – m i m+1 – r, przyrównując przy tym ich elementy – Jeśli element lewej tablicy na aktualnej pozycji jest mniejszy od tego na prawej, wstaw go do tablicy docelowej i zwiększ indeks lewej tablicy. W przeciwnym przypadku, wykonaj analogiczne działanie dla prawej tablicy

Zalety

• Prostota
• Wydajny
• Stabilny
• Algorytm sortuje zbiór n-elementowy w czasie proporcjonalnym do liczby

Wady

• podczas scalania potrzebny jest dodatkowy obszar pamięci przechowujący kopie podtablic do scalenia

5.

Sortowanie Strategiczne

Dziel-Zwyciężaj-Połącz

Sortowanie strategiczne

Działanie

• Do utworzenia partycji musimy ze zbioru wybrać jeden z elementów, który nazwiemy piwotem. W

lewej partycji znajdą się wszystkie elementy niewiększe od piwotu, a w prawej partycji umieścimywszystkie elementy niemniejsze od piwotu. Położenie elementów równych nie wpływa na processortowania, zatem mogą one występować w obu partycjach. Również porządek elementów w każdejz partycji nie jest ustalony.Jako piwot można wybierać element pierwszy, środkowy, ostatni, medianę lub losowy.

Zalety

Wady

• Długotrwały proces
• W razie nieznajomości działania może dojść do nieukończenia sortowania

• Logiczne działanie
• Stopniowe wykrywanie

4.

Sortowanie poprzez Kubełkowe

Sortowanie zbiorów liczb całkowitych

Wizualizacja

Sposób działania

1.Założenia:

• liczby do posortowania znajdują się w przedziale
• liczby są równomiernie rozłożone
• dla n liczb tworzymy n kubełków

• wyznaczamy długość przedziału pojedynczego kubełka
• wybieramy ilość liczb do sortowania
• Każdą z tych liczb wkładamy do odpowiedniego kubełka
• Następnie przeglądamy każdy kubełek i jeśli jest w nim więcej niż jeden element, wykonujemy sortowanie dowolnym algorytmem

5.

Sortowanie Przez Kopcowanie

Kolejka z użyciem priorytetowej

Zalety

• złożoność czasowa jest rzędu O(n)

• algorytm nie potrzebuje dodatkowej tablicy (sortowanie odbywa się w miejscu)
• jest łatwy w implementacji

Wady

• dane muszą być równomiernie rozłożone, aby złożoność była liniowa
• trzeba znać dokładny rozstęp zbioru (różnicę między największą i najmniejszą wartością do posortowania)

Wizualizacja

SPOSÓB DZIAŁANIA

• Kopiec jest drzewem binarnym, w którym wszystkie węzły spełniają następujący warunek (zwany warunkiem kopca):

• Węzeł nadrzędny jest większy lub równy węzłom potomnym (w porządku malejącym relacja jest odwrotna - mniejszy lub równy)
• Konstrukcja kopca jest nieco bardziej skomplikowana od konstrukcji drzewa binarnego, ponieważ musimy dodatkowo troszczyć się o zachowanie warunku kopca. Zatem po każdym dołączeniu do kopca nowego węzła, sprawdzamy odpowiednie warunki i ewentualnie dokonujemy wymian węzłów na ścieżce wiodącej od dodanego węzła do korzenia.
• Charakterystyczną cechą kopca jest to, iż korzeń zawsze jest największym (w porządku malejącym najmniejszym) elementem z całego drzewa binarnego.

Zalety

Wady

• szybki
• niepochłaniający wiele pamięci

• wolniejszy od sortowania szybkiego
• niestabilny

Dziękujemy za uwagę

Jakub Deszcz&Zofia Poradomska