W tym artykule omówimy ważne właściwości różnych technik sortowania, w tym ich złożoność, stabilność i ograniczenia pamięci. Przed zrozumieniem tego artykułu, powinieneś zrozumieć podstawy różnych technik sortowania (Zobacz : Techniki sortowania).
Analiza złożoności czasowej –
Przedyskutowaliśmy najlepszą, średnią i najgorszą złożoność różnych technik sortowania z możliwymi scenariuszami.
Sortowanie oparte na porównaniach –
W sortowaniu opartym na porównaniach elementy tablicy są porównywane ze sobą, aby znaleźć posortowaną tablicę.
- Sort bąbelkowy i sortowanie wstawiania –
Średnia i najgorsza złożoność czasowa: n^2
Najlepsza złożoność czasowa: n, gdy tablica jest już posortowana.
Przypadek najgorszy: gdy tablica jest odwrotnie posortowana. - Sortowanie selekcyjne –
Najlepsza, średnia i najgorsza złożoność czasowa: n^2, która jest niezależna od rozkładu danych. - Merge sort –
Najlepsza, średnia i najgorsza złożoność czasowa: nlogn, która jest niezależna od dystrybucji danych. - Heap sort –
Najlepsza, średnia i najgorsza złożoność czasowa: nlogn, która jest niezależna od dystrybucji danych. - Sortowanie szybkie –
Jest to podejście typu dziel i zwyciężaj z relacją rekurencji:T(n) = T(k) + T(n-k-1) + cn
Najgorszy przypadek: gdy tablica jest posortowana lub posortowana odwrotnie, algorytm podziału dzieli tablicę na dwie podtarcze z 0 i n-1 elementami. Dlatego,
T(n) = T(0) + T(n-1) + cnSolving this we get, T(n) = O(n^2)
Przypadek najlepszy i Przypadek średni: Średnio algorytm partycji dzieli tablicę na dwie podtarcze o równym rozmiarze. Therefore,
T(n) = 2T(n/2) + cnSolving this we get, T(n) = O(nlogn)
Non-comparison based sorting –
W non-comparison based sorting, elementy tablicy nie są porównywane ze sobą w celu znalezienia posortowanej tablicy.
- Radix sort –
Najlepsza, średnia i najgorsza złożoność czasowa: nk, gdzie k jest maksymalną liczbą cyfr w elementach tablicy. - Count sort –
Najlepsza, średnia i najgorsza złożoność czasowa: n+k, gdzie k jest rozmiarem tablicy count. - Sortowanie kubełkowe –
Najlepsza i średnia złożoność czasowa: n+k gdzie k jest liczbą kubełków.
Pogorszona złożoność czasowa: n^2 jeśli wszystkie elementy należą do tego samego kubełka.
Technika in-place/Outplace –
Technika sortowania jest inplace jeśli nie używa żadnej dodatkowej pamięci do sortowania tablicy.
Wśród omawianych technik opartych na porównywaniu, tylko merge sort jest techniką outplaced, ponieważ wymaga dodatkowej tablicy do połączenia posortowanych podtablic.
Wśród omawianych technik nie opartych na porównywaniu, wszystkie są technikami outplaced. Counting sort używa tablicy zliczającej, a bucket sort używa tablicy haszującej do sortowania tablicy.
Online/Offline technique –
Technika sortowania jest uważana za Online, jeśli może przyjmować nowe dane w czasie trwania procedury, tj. kompletne dane nie są wymagane do rozpoczęcia operacji sortowania.
Pośród omówionych technik opartych na porównywaniu, tylko Insertion Sort kwalifikuje się do tego ze względu na bazowy algorytm, którego używa, tj. przetwarza tablicę (nie tylko elementy) od lewej do prawej i jeśli nowe elementy są dodawane po prawej stronie, nie ma to wpływu na trwającą operację.
Stabilna/Niestabilna technika –
Technika sortowania jest stabilna, jeśli nie zmienia kolejności elementów o tej samej wartości.
Z pośród technik opartych na porównywaniu, sortowanie bąbelkowe, sortowanie przez wstawianie i sortowanie przez scalanie są technikami stabilnymi. Sortowanie przez wybór jest niestabilne, ponieważ może zmienić kolejność elementów z tą samą wartością. Na przykład rozważ tablicę 4, 4, 1, 3.
W pierwszej iteracji minimalny znaleziony element to 1 i jest on zamieniany z 4 na pozycji 0. Dlatego kolejność 4 w odniesieniu do 4 na 1. pozycji ulegnie zmianie. Podobnie, szybkie sortowanie i sortowanie sterty są również niestabilne.
Z technik opartych na nieporównywalności, sortowanie zliczające i sortowanie kubełkowe są stabilnymi technikami sortowania, podczas gdy stabilność sortowania radix zależy od bazowego algorytmu używanego do sortowania.
Analiza technik sortowania :
- Gdy tablica jest prawie posortowana, preferowany może być sort insertion.
- Gdy kolejność danych wejściowych nie jest znana, preferowany jest merge sort, ponieważ ma on najgorszą złożoność czasową nlogn i jest również stabilny.
- Gdy tablica jest posortowana, insertion i bubble sort dają złożoność n, ale quick sort daje złożoność n^2.
Que – 1. Który algorytm sortowania zajmie najmniej czasu, gdy wszystkie elementy tablicy wejściowej są identyczne? Rozważ typowe implementacje algorytmów sortowania.
(A) Insertion Sort
(B) Heap Sort
(C) Merge Sort
(D) Selection Sort
Rozwiązanie: Jak omówiono, insertion sort będzie miał złożoność n, gdy tablica wejściowa jest już posortowana.
Que – 2. Rozważmy algorytm Quicksort. Załóżmy, że istnieje procedura znajdowania elementu pivot, która dzieli listę na dwie podlisty, z których każda zawiera co najmniej jedną piątą elementów. Niech T(n) będzie liczbą porównań potrzebnych do posortowania n elementów. Wtedy, (GATE-CS-2012)
(A) T(n) <= 2T(n/5) + n
(B) T(n) <= T(n/5) + T(4n/5) + n
(C) T(n) <= 2T(4n/5) + n
(D) T(n) <= 2T(n/2) + n
Rozwiązanie: Złożoność sortowania szybkiego można zapisać jako:
T(n) = T(k) + T(n-k-1) + cn
Jak podano w pytaniu, jedna lista zawiera 1/5 wszystkich elementów. Dlatego inna lista będzie miała 4/5 wszystkich elementów. Podstawiając wartości, otrzymujemy:
T(n) = T(n/5) + T(4n/5) + cn, co odpowiada opcji (B).
Tabela porównawcza złożoności czasowej i przestrzennej :
| Algorytm sortujący | Złożoność czasowa | Złożoność przestrzenna | |||
|---|---|---|---|---|---|
| Best Case | Average Case | Worst Case | Worst Case | ||
| Sort bąbelkowy | Ω(N) | Θ(N2) | O(N2) | O(1) | |
| Sort selekcji | Ω(N2) | Θ(N2) | O(N2) | O(1) | |
| Sort wstawiania | Ω(N) | Θ(N2) | O(N2) | O(1) | |
| Merge Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(N) | |
| Heap Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(1) | |
| Θ(N k) | O(N k) | O(N + k) | |||
| Sortowanie zliczeniowe | Ω(N + k) | Θ(N + k) | O(N + k) | O(N + k) | O(k) |
| Sortowanie kubełkowe | Ω(N + k) | Θ(N + k) | O(N2) | O(N) | |
