Sortowanie szybkie – notatki

Sortowanie szybkie

Algorytm dziel i zwyciężaj, który dzieli tablicę na mniejsze części i sortuje je rekurencyjnie.

Podział w sortowaniu szybkim

Tablica jest dzielona na dwa podzbiory według pivotu, elementy mniejsze idą do lewej, większe do prawej.

Pivot

Element używany do podziału tablicy, może być wybierany na różne sposoby, np. pierwszy, ostatni lub losowy.

Przypadek średni złożoności

Złożoność czasowa w najlepszym i przeciętnym przypadku wynosi $\displaystyle O(n imes ext{log} n)$.

Złośliwy przypadek złożoności

W najgorszym przypadku, gdy pivot jest najmniejszy lub największy, złożoność wynosi $\displaystyle O(n^2)$.

Stabilność sortowania

Sortowanie szybkie nie jest stabilne, co oznacza, że równe elementy mogą zmieniać się miejscami.

Rekurencja

Sortowanie szybkie wykorzystuje rekurencję do sortowania podtablic, co może prowadzić do dużego zużycia pamięci.

Zastosowanie sortowania szybkiego

Często używane w praktycznych aplikacjach, takich jak sortowanie dużych zestawów danych w bazach danych.

Algorytm in-place

Sortowanie szybkie działa w miejscu, co oznacza, że nie wymaga dodatkowej pamięci na przechowywanie kopii tablicy.

Wybór pivotu

Właściwy wybór pivotu może znacząco wpłynąć na wydajność sortowania szybkiego.

Optymalizacja sortowania

Można optymalizować poprzez użycie algorytmu sortowania prostszego dla małych podtablic, jak np. sortowanie bąbelkowe.

Złożoność pamięciowa

Sortowanie szybkie ma złożoność pamięciową $\displaystyle O( ext{log} n)$ w przypadku wywołań rekurencyjnych.

Implementacja sortowania szybkiego

Można zaimplementować w językach programowania takich jak Python, Java, C++ i wiele innych.

Kod w Pythonie

Przykładowa implementacja: def quicksort(arr): ...

Sortowanie tablicy

Sortowanie tablicy o n elementach zajmuje średnio $\displaystyle O(n imes ext{log} n)$ czasu.

Przykład danych

Dla tablicy [3, 6, 8, 10, 1, 2, 1], pivotem może być 6. Po podziale: [3, 1, 2, 1] | [6, 8, 10].

Złożoność w najlepszym przypadku

W najlepszym przypadku, gdy wybór pivotu jest optymalny, czas działania to $\displaystyle O(n imes ext{log} n)$.

Porównanie z innymi algorytmami

Sortowanie szybkie jest często szybsze od sortowania przez scalanie dla małych i średnich zbiorów danych.

Wady sortowania szybkiego

Może być nieefektywne przy już posortowanych danych, jeśli pivot jest źle wybrany.

Sortowanie z rekurencją

Rekurencyjna strategia sortowania może prowadzić do przekroczenia limitu stosu dla bardzo dużych tablic.

Alternatywne metody wyboru pivotu

Można stosować medianę trzech, by poprawić wydajność algorytmu.

Analiza wydajności

Wydajność sortowania szybkiego można analizować poprzez analizę przypadków i wyboru pivotu.

Dostosowanie do realnych zastosowań

Algorytm często dostosowuje się do specyfiki danych i wymagań aplikacji.