TECHNIK PROGRAMISTA INF. 04
Materiały pomocnicze, rozwiązania zadań i arkusze egzaminacyjne – wszystko, czego potrzebujesz, aby zdać egzamin i rozwijać swoje umiejętności programistyczne.

Sortowanie

Sortowanie to podstawowa operacja informatyczna, która polega na uporządkowaniu elementów w zbiorze według określonego kryterium, takiego jak wartość numeryczna, kolejność alfabetyczna, długość czy inny porządek. Sortowanie jest kluczowe w wielu aspektach przetwarzania danych i algorytmiki, ponieważ uporządkowane dane są znacznie łatwiejsze do przeszukiwania, analizowania i prezentowania.

Cel Sortowania
  • Ułatwienie dostępu do danych: Posortowane dane pozwalają na szybsze wyszukiwanie, na przykład poprzez wyszukiwanie binarne.
  • Uporządkowanie danych: Sortowanie jest używane do porządkowania danych w celach prezentacji lub dalszej analizy.
  • Optymalizacja algorytmów: Niektóre algorytmy, takie jak te związane z grafami, działają efektywniej na posortowanych danych.

Sortowanie bąbelkowe, znane również jako sortowanie przez zamianę lub sortowanie bąbelkami, jest prostą metodą sortowania danych w informatyce. Podstawowa idea działania tego algorytmu polega na wielokrotnym przeglądaniu listy lub tablicy elementów i zamianie miejscami tych par sąsiednich elementów, które są w niewłaściwej kolejności. Proces jest powtarzany do momentu, aż cała lista zostanie posortowana.

Sortowanie bąbelkowe:

  1. Start na początku listy: Algorytm rozpoczyna działanie od pierwszego elementu listy.
  2. Porównywanie sąsiednich elementów: Porównuje on dwa sąsiadujące elementy.
  3. Zamiana miejscami (jeśli to konieczne): Jeśli element znajdujący się po lewej stronie jest większy od elementu po prawej (dla sortowania rosnącego), algorytm zamienia te elementy miejscami.
  4. Przejście do następnej pary: Po porównaniu i ewentualnej zamianie, algorytm przesuwa się o jeden element w prawo i powtarza proces.
  5. Kończenie iteracji: Gdy algorytm dojdzie do końca listy, jedna iteracja sortowania jest zakończona. Jeśli w trakcie tej iteracji dokonano jakiejkolwiek zamiany, oznacza to, że lista może być jeszcze nieposortowana i wymaga kolejnej iteracji.
  6. Powtarzanie procesu: Cały proces jest powtarzany od początku listy tyle razy, aż podczas jednej pełnej iteracji nie będzie potrzeby dokonywania żadnych zamian, co oznacza, że lista jest już posortowana.
Właściwości algorytmu:
  • Złożoność czasowa: O(n²) dla najgorszego i przeciętnego przypadku, gdzie n to liczba elementów do posortowania. Dla już posortowanej listy złożoność to O(n).
  • Złożoność przestrzenna: O(1) – sortowanie bąbelkowe nie wymaga dodatkowej przestrzeni pamięci, oprócz miejsca na zamieniane elementy, ponieważ jest sortowaniem na miejscu (in-place).
  • Stabilność: Sortowanie bąbelkowe jest sortowaniem stabilnym, co oznacza, że zachowuje ono kolejność równych elementów.
Wady i zalety:
  • Prostota: Jest to jeden z najprostszych algorytmów do zrozumienia i implementacji.
  • Wydajność: Sortowanie bąbelkowe jest bardzo niewydajne dla dużych list i rzadko używane w praktycznych zastosowaniach z powodu swojej niskiej wydajności.
  • Użyteczność dydaktyczna: Pomimo niskiej wydajności, jest często nauczany w edukacji jako wprowadzenie do pojęcia algorytmów sortowania.

Ze względu na swoją niską wydajność, w praktycznych aplikacjach często zastępuje się sortowanie bąbelkowe bardziej zaawansowanymi algorytmami, takimi jak sortowanie przez scalanie (merge sort), sortowanie szybkie (quick sort) czy sortowanie przez kopcowanie (heap sort).

Przykład z liczbami: 5, 12, 3, 55, 1
Iteracja 1:
  • Porównujemy 5 i 12. Ponieważ 5 < 12, nie zamieniamy ich miejscami: 5, 12, 3, 55, 1
  • Porównujemy 12 i 3. Ponieważ 12 > 3, zamieniamy je miejscami: 5, 3, 12, 55, 1
  • Porównujemy 12 i 55. Ponieważ 12 < 55, nie zamieniamy ich miejscami: 5, 3, 12, 55, 1
  • Porównujemy 55 i 1. Ponieważ 55 > 1, zamieniamy je miejscami: 5, 3, 12, 1, 55
Iteracja 2:
  • Porównujemy 5 i 3. Ponieważ 5 > 3, zamieniamy je miejscami: 3, 5, 12, 1, 55
  • Porównujemy 5 i 12. Ponieważ 5 < 12, nie zamieniamy ich miejscami: 3, 5, 12, 1, 55
  • Porównujemy 12 i 1. Ponieważ 12 > 1, zamieniamy je miejscami: 3, 5, 1, 12, 55
  • 55 jest już na swoim miejscu, więc nie ma potrzeby porównywania go z żadnymi liczbami.
Iteracja 3:
  • Porównujemy 3 i 5. Ponieważ 3 < 5, nie zamieniamy ich miejscami: 3, 5, 1, 12, 55
  • Porównujemy 5 i 1. Ponieważ 5 > 1, zamieniamy je miejscami: 3, 1, 5, 12, 55
  • Reszta listy jest już posortowana, więc nie ma potrzeby dalszego porównywania.
Iteracja 4:
  • Porównujemy 3 i 1. Ponieważ 3 > 1, zamieniamy je miejscami: 1, 3, 5, 12, 55
  • Pozostałe liczby są już na swoich miejscach.

Teraz mamy już posortowany ciąg liczb: 1, 3, 5, 12, 55

Po tych iteracjach, ciąg liczb jest teraz całkowicie posortowany. Jak widać, sortowanie bąbelkowe jest prostym, ale dość wolnym algorytmem sortowania, szczególnie dla dużych zbiorów danych, gdzie liczba porównań i potencjalnych zamian jest znacząca.

void SortowanieBobelkowe(int tablicaLiczb[], int rozmiar) {
    int temp;
    for(int i=0; i<rozmiar; i++) {
        for(int j=0; j<rozmiar-1; j++) {
            if(tablicaLiczb[j]>tablicaLiczb[j+1]) {
                temp=tablicaLiczb[j];
                tablicaLiczb[j]=tablicaLiczb[j+1];
                tablicaLiczb[j+1]=temp;
            }
        }
    }
}

Oto krok po kroku, jak działa ten kod:

  1. Zewnętrzna pętla for: Iteruje przez całą tablicę. Warto zauważyć, że ta konkretna implementacja nie jest zoptymalizowana, ponieważ wykonuje pełną liczbę iteracji nawet jeśli tablica zostanie posortowana przed zakończeniem wszystkich przebiegów. W optymalizowanej wersji algorytmu można by zastosować mechanizm (na przykład zmienną boolowską), który kończy algorytm wcześniej, jeśli w danym przebiegu nie dokonano żadnej zmiany.
  2. Wewnętrzna pętla for: Przechodzi przez tablicę od początku do przedostatniego elementu. Dla każdego elementu tablicy (oznaczonego jako tablicaLiczb[j]) porównuje go z następnym elementem w tablicy (tablicaLiczb[j+1]).
  3. Warunek if: Sprawdza, czy bieżący element (tablicaLiczb[j]) jest większy niż następny element w tablicy (tablicaLiczb[j+1]). Jeśli tak, to elementy są w złej kolejności i muszą zostać zamienione miejscami, aby zapewnić porządek rosnący.
  4. Zamiana miejscami: Jeśli warunek w punkcie 3 jest spełniony, algorytm zamienia miejscami elementy, używając zmiennej tymczasowej temp do przechowania jednej z wartości podczas operacji zamiany.
  5. Powtarzanie: Krok 2 do 4 są powtarzane aż do momentu, gdy cała tablica zostanie przejrzana tyle razy, ile jest elementów w tablicy. Dla tablicy N elementowej oznacza to N pełnych przebiegów, co gwarantuje, że każdy element znajdzie się na swoim miejscu.

Sortowanie przez wstawianie (Insertion Sort)

Sortowanie przez wstawianie to prosty algorytm sortowania, który buduje posortowaną sekwencję elementów (tablicę lub listę) poprzez jednoelementowe dodawanie do uporządkowanej części sekwencji. Jest to algorytm porównawczy, który działa bardzo dobrze dla małych lub częściowo posortowanych danych.

Jak działa sortowanie przez wstawianie:
  1. Zaczynamy od drugiego elementu: Pierwszy element jest już w „posortowanej” sekcji tablicy.
  2. Wybieranie elementu: Algorytm bierze następny element z nieposortowanej części tablicy.
  3. Porównywanie i wstawianie: Porównuje ten element z posortowanymi elementami, przesuwając każdy z nich o jedno miejsce w prawo, aż znajdzie odpowiednie miejsce dla wstawianego elementu.
  4. Wstawienie elementu: Wstawia wybrany element w odpowiednie miejsce.
  5. Powtórzenie dla kolejnych elementów: Proces jest powtarzany dla każdego elementu w nieposortowanej części tablicy aż do jej końca.
Właściwości algorytmu:
  • Złożoność czasowa: O(n²) dla najgorszego i przeciętnego przypadku, ale O(n) dla najlepszego przypadku (gdy dane są już posortowane).
  • Złożoność przestrzenna: O(1), ponieważ sortowanie odbywa się na miejscu.
  • Stabilność: Sortowanie przez wstawianie jest stabilne.

ość dla małych zbiorów danych lub gdy dane są już częściowo posortowane. Nie jest jednak zalecane dla dużych

Początkowy zestaw danych:

5, 12, 3, 55, 1

Zbiór elementów posortowanych: 5
Zbiór elementów nieposortowanych: 12, 3, 55, 1

Krok 1: Wybieramy cyfrę 12.

Cyfra 12 jest już większa od 5, więc nie musimy przesuwać elementów w zbiorze posortowanym.
Zbiór po kroku 1: 5, 12 | 3, 55, 1

Krok 2: Wybieramy cyfrę 3.

Cyfra 3 jest mniejsza niż 12 i 5, więc przesuwamy obie te liczby w prawo, by zwolnić miejsce dla 3.
Zbiór po kroku 2: 3, 5, 12 | 55, 1

Krok 3: Wybieramy cyfrę 55.

Cyfra 55 jest większa od wszystkich elementów w zbiorze posortowanym, więc zostaje na swoim miejscu.
Zbiór po kroku 3: 3, 5, 12, 55 | 1

Krok 4: Wybieramy cyfrę 1.

Cyfra 1 jest mniejsza niż wszystkie elementy w zbiorze posortowanym, więc przesuwamy wszystkie liczby w prawo, by zwolnić miejsce na początku.
Zbiór po kroku 4: 1, 3, 5, 12, 55

Zbiór został całkowicie posortowany. Jak widać, sortowanie przez wstawianie efektywnie radzi sobie z organizowaniem danych, przesuwając mniejsze elementy na początek i większe na koniec zbioru posortowanego, aż do osiągnięcia pełnej organizacji zestawu.

void SortowaniePrzezWstawienie (int tablicaLiczb[], int rozmiar) {
    int temp, j;
    for (int i = 1; i < rozmiar; i++) {
        temp = tablicaLiczb[i];
        for (j = i - 1; j >= 0 && tablicaLiczb[j] > temp; j--) {
            tablicaLiczb[j + 1] = tablicaLiczb[j];
        }
        tablicaLiczb[j + 1] = temp;
    }
}

Oto krok po kroku, jak działa ten kod:

  1. Pętla zewnętrzna (for): Rozpoczyna od drugiego elementu tablicy (i = 1), ponieważ zakłada się, że pierwszy element (indeks 0) jest już „posortowany”. Iteruje przez każdy element tablicy aż do ostatniego.
  2. Przygotowanie do wstawienia: Na początku każdej iteracji zewnętrznej pętli, bieżący element do wstawienia (temp) jest zapisywany, aby móc go porównywać z poprzednimi elementami w posortowanej już części tablicy.
  3. Pętla wewnętrzna (for lub tutaj while ukryta w for): Rozpoczyna od elementu bezpośrednio przed bieżącym elementem (j = i - 1) i porusza się wstecz przez posortowaną już część tablicy (czyli w lewo od bieżącego elementu), szukając odpowiedniego miejsca dla elementu temp. Jeśli bieżący element jest mniejszy od elementu temp, to przesuwa ten element o jedno miejsce w prawo (tablicaLiczb[j + 1] = tablicaLiczb[j]). Dzięki temu, robi miejsce na wstawienie elementu temp.
  4. Wstawienie elementu: Po znalezieniu odpowiedniego miejsca (gdy j jest mniejsze od 0 lub gdy element w tablicaLiczb[j] jest mniejszy lub równy temp), wstawia się element temp na swoje miejsce w posortowanej części tablicy. Operacja ta jest realizowana po zakończeniu pętli wewnętrznej.
  5. Powtórzenie procesu: Proces ten jest powtarzany dla każdego elementu tablicy, rozszerzając posortowaną część tablicy aż do jej całkowitego posortowania.

Sortowanie przez wybieranie (Selection Sort)

Sortowanie przez wybieranie to prosty algorytm sortowania, który dzieli wejściową tablicę na dwie części: posortowaną, która jest budowana od lewej strony, i nieposortowaną, z której elementy są wybierane i przenoszone do posortowanej części.

Jak działa sortowanie przez wybieranie:
  1. Wyszukiwanie minimalnego elementu: W każdej iteracji algorytm przeszukuje nieposortowaną część tablicy, aby znaleźć najmniejszy element.
  2. Zamiana elementów: Znaleziony minimalny element jest następnie zamieniany miejscami z pierwszym nieposortowanym elementem.
  3. Aktualizacja indeksów: Granica między posortowaną a nieposortowaną częścią tablicy jest przesuwana o jeden element w prawo.
  4. Powtarzanie: Kroki te są powtarzane aż do posortowania całej tablicy.
Właściwości algorytmu:
  • Złożoność czasowa: O(n²), niezależnie od początkowego uporządkowania danych.
  • Złożoność przestrzenna: O(1), ponieważ sortowanie jest wykonywane na miejscu.
  • Stabilność: Sortowanie przez wybieranie nie jest stabilne, co oznacza, że może zmienić wzajemne położenie równych elementów.

Początkowy zestaw danych:

5, 12, 3, 55, 1

Krok 1: Wyszukujemy najmniejszy element, czyli 1.

Zamieniamy go z pierwszym elementem listy, czyli 5.
1, 12, 3, 55, 5

Krok 2: W zaznaczonej liście (pomijając już posortowany element 1) wyszukujemy najmniejszy element, czyli 3.

Zamieniamy go z pierwszym elementem nieposortowanej części listy, czyli 12.
1, 3, 12, 55, 5

Krok 3: W zaznaczonej liście (pomijając już posortowane elementy 1, 3) wyszukujemy najmniejszy element, czyli 5.

Zamieniamy go z pierwszym elementem nieposortowanej części listy, czyli 12.
1, 3, 5, 55, 12

Krok 4: W zaznaczonej liście (pomijając już posortowane elementy 1, 3, 5) wyszukujemy najmniejszy element, czyli 12.

Zamieniamy go z pierwszym elementem nieposortowanej części listy, czyli 55.
1, 3, 5, 12, 55

Krok 5:

Na tym etapie pozostaje nam tylko jeden element, 55, który jest już na swoim miejscu, ponieważ wszystkie wcześniejsze elementy są posortowane.

Końcowy rezultat wygląda następująco:
1, 3, 5, 12, 55

Sortowanie przez wybieranie jest prostym algorytmem sortowania, który jest łatwy do zrozumienia i implementacji, ale nie jest zalecany dla dużych zbiorów danych ze względu na swoją niską wydajność w porównaniu z bardziej zaawansowanymi algorytmami.

void SortowaniePrzezWybieranie (int tablicaLiczb[], int rozmiar) {
    int temp;
    for(int i=0; i<rozmiar-1; i++) {
        int min =i;
        for(int j=i+1; j<rozmiar; j++) {
            if(tablicaLiczb[j]<tablicaLiczb[min]) {
                min=j;
            }
        }
        if(min!=i) {
            temp=tablicaLiczb[i];
            tablicaLiczb[i]=tablicaLiczb[min];
            tablicaLiczb[min]=temp;
        }
    }
}

Oto krok po kroku, jak działa ten kod:

  1. Inicjalizacja: Algorytm rozpoczyna od ustawienia zmiennej i na 0. Zmienna i reprezentuje indeks pierwszego elementu nieposortowanej części tablicy. Pętla zewnętrzna iteruje przez wszystkie elementy tablicy oprócz ostatniego, ponieważ po posortowaniu wszystkich pozostałych elementów, ostatni automatycznie znajduje się na właściwym miejscu.
  2. Wyszukiwanie minimalnego elementu: Na początku każdej iteracji pętli zewnętrznej, algorytm zakłada, że pierwszy element nieposortowanej części tablicy (tablicaLiczb[i]) jest tymczasowo minimalnym elementem, ustawiając zmienną min na i. Następnie, wewnątrz pętli wewnętrznej, algorytm przeszukuje pozostałą część tablicy (zaczynając od i+1) w poszukiwaniu elementu mniejszego niż bieżący minimalny element.
  3. Zamiana: Jeżeli w trakcie przeszukiwania zostanie znaleziony mniejszy element (tablicaLiczb[j] < tablicaLiczb[min]), algorytm aktualizuje zmienną min, aby wskazywała na ten mniejszy element. Po zakończeniu przeszukiwania, jeśli indeks min różni się od i (co oznacza, że znaleziono mniejszy element w nieposortowanej części tablicy), algorytm zamienia miejscami element o indeksie i z elementem minimalnym znalezionym w tej iteracji.
  4. Powtarzanie: Proces ten jest powtarzany, przy czym za każdym razem rozmiar nieposortowanej części tablicy maleje o jeden element (ponieważ element na początku tej części jest zamieniany z minimalnym elementem i staje się częścią posortowaną), aż do osiągnięcia przedostatniego elementu tablicy.

Sortowanie grzebieniowe (Comb Sort)

Sortowanie grzebieniowe to ulepszona wersja sortowania bąbelkowego. Główną różnicą jest to, że w sortowaniu grzebieniowym początkowa odległość (lub „przerwa”) pomiędzy porównywanymi elementami jest znacznie większa niż 1. Ta odległość jest stopniowo zmniejszana aż do wartości 1, co ostatecznie redukuje się do klasycznego sortowania bąbelkowego. Dzięki temu sortowanie grzebieniowe eliminuje problem „żółwi”, czyli powolnego przesuwania małych wartości w kierunku początku tablicy, który jest typowy dla sortowania bąbelkowego.

Jak działa sortowanie grzebieniowe:
  1. Ustalanie przerwy: Początkowa przerwa jest zazwyczaj ustalana jako długość listy podzielona przez 1.3 (ten współczynnik jest wynikiem empirycznych badań).
  2. Porównywanie elementów w przerwie: Porównuje się elementy, które są oddzielone przez przerwę.
  3. Zmniejszanie przerwy: Po każdej iteracji, przerwa jest zmniejszana (zazwyczaj dzielona przez 1.3), aż do wartości 1.
  4. Finalne sortowanie bąbelkowe: Gdy przerwa osiągnie wartość 1, algorytm wykonuje klasyczne sortowanie bąbelkowe.
Właściwości algorytmu:
  • Złożoność czasowa: Średnio szybsze niż O(n²) dzięki większej przerwie na początku, ale w najgorszym przypadku nadal może osiągnąć O(n²).
  • Złożoność przestrzenna: O(1), ponieważ jest to sortowanie na miejscu.
  • Stabilność: Nie jest stabilne.
Przykład z liczbami: 5, 12, 3, 55, 1

Załóżmy, że mamy tablicę 5,12,3,55,1 do posortowania.

  1. Początkowa przerwa: Długość listy to 5, więc początkowa przerwa wynosi 5/1.3 ≈ 4.
  2. Pierwsza iteracja:
    • Porównujemy pary elementów oddzielone przerwą 4: nie ma par, więc przechodzimy dalej.
  3. Nowa przerwa: 4/1.3 ≈ 3
    • Porównujemy pary elementów oddzielone przerwą 3: (5, 55) – nie zamieniamy, bo 5 < 55.
  4. Nowa przerwa: 3/1.3 ≈ 2
    • Porównujemy pary elementów oddzielone przerwą 2: (5, 3) – zamieniamy, bo 5 > 3; (12, 1) – zamieniamy, bo 12 > 1. Tablica teraz wygląda: 3,12,5,1,55
  5. Nowa przerwa: 2/1.3 ≈ 1
    • Wykonujemy klasyczne sortowanie bąbelkowe: po kilku iteracjach otrzymujemy posortowaną tablicę 1,3,5,12,55

Sortowanie grzebieniowe jest znacznie szybsze od klasycznego sortowania bąbelkowego, szczególnie dla dużych list. Współczynnik zmniejszania przerwy 1.3 został empirycznie ustalony jako optymalny dla wielu zestawów danych. Algorytm ten jest szczególnie efektywny w przypadku list, które mają dużo małych elementów na końcu.

Sortowanie przez zliczanie (Counting Sort)

Sortowanie przez zliczanie jest algorytmem sortowania, który działa najlepiej z danymi, które są dyskretne i mają ograniczony zakres, jak liczby całkowite w małym przedziale. Zamiast porównywać same wartości, sortowanie przez zliczanie liczy ilość wystąpień każdego elementu.

Jak działa sortowanie przez zliczanie:
  1. Znalezienie zakresu danych: Najpierw algorytm wyszukuje wartość maksymalną w zbiorze danych, aby wiedzieć, jak duży musi być pomocniczy tablica do zliczania.
  2. Inicjalizacja tablicy do zliczania: Tworzona jest pomocnicza tablica (tablica zliczeń) o długości równej maksymalnej wartości plus jeden. Wszystkie wartości są inicjalizowane na zero.
  3. Zliczanie wystąpień: Algorytm przechodzi przez oryginalną tablicę danych i dla każdego elementu inkrementuje wartość w tablicy zliczeń odpowiadającą wartości tego elementu.
  4. Tworzenie posortowanej tablicy: Na podstawie tablicy zliczeń algorytm generuje posortowaną tablicę. Dla każdego indeksu w tablicy zliczeń, odpowiadającej liczbie wystąpień dodaje do posortowanej tablicy element o wartości tego indeksu.
Właściwości algorytmu:
  • Złożoność czasowa: O(n+k), gdzie n to liczba elementów do posortowania, a k to zakres danych.
  • Złożoność przestrzenna: O(k), gdzie k to zakres danych.
  • Stabilność: Sortowanie przez zliczanie jest stabilne, co oznacza, że zachowuje kolejność równych elementów.
Przykład z liczbami: 5, 12, 3, 55, 1
  1. Zakres danych: Największa liczba to 55, więc tworzymy tablicę zliczeń o długości 56 (od 0 do 55).
  2. Inicjalizacja tablicy zliczeń: [0, 0, 0, …, 0] (56 zer)
  3. Zliczanie wystąpień:
    • Zwiększamy wartość w indeksie 5 (dla liczby 5).
    • Zwiększamy wartość w indeksie 12 (dla liczby 12).
    • Zwiększamy wartość w indeksie 3 (dla liczby 3).
    • Zwiększamy wartość w indeksie 55 (dla liczby 55).
    • Zwiększamy wartość w indeksie 1 (dla liczby 1).
    • Po zliczeniu tablica zliczeń wygląda tak: [0, 1, 0, 1, 0, 1, 0, …, 0, 1, 0, 1]
  4. Generowanie posortowanej tablicy:
    • Przechodzimy przez tablicę zliczeń i dla każdej niezerowej wartości dodajemy odpowiednią liczbę do posortowanej tablicy.
    • Posortowana tablica: [1, 3, 5, 12, 55]

I to jest posortowana tablica. Sortowanie przez zliczanie jest niezwykle szybkie dla danych o małym zakresie wartości, ale może być nieefektywne pamięciowo, jeśli zakres danych jest bardzo duży, ponieważ wymaga tablicy pomocniczej o długości równej maksymalnej wartości w zestawie danych.

Sortowanie gnoma (Gnome Sort)

Sortowanie gnoma to algorytm sortowania, który przypomina działanie osoby próbującej posortować rząd kart. Jest on bardzo prosty w swoim działaniu i działa na zasadzie porównywania kolejnych par elementów i zamiany ich miejscami, jeśli są w złej kolejności, a następnie 'cofania się’ w celu ponownego sprawdzenia poprzednich elementów po każdej zamianie.

Jak działa sortowanie gnoma:
  1. Start: Rozpocznij od drugiego elementu tablicy.
  2. Porównywanie elementów: Porównaj bieżący element z poprzednim.
  3. Jeśli kolejność jest prawidłowa: Przesuń się o jeden indeks do przodu.
  4. Jeśli kolejność jest nieprawidłowa: Zamień elementy miejscami i cofnij się o jeden indeks, aby ponownie porównać elementy.
  5. Cofanie: Jeśli jesteś na początku tablicy, przejdź do następnego elementu.
  6. Powtarzanie: Powtarzaj kroki 2-5 aż dojdziesz do końca tablicy i tablica będzie posortowana.
Właściwości algorytmu:
  • Złożoność czasowa: Najgorszy przypadek to O(n^2), ale dla danych prawie posortowanych jest znacznie szybszy.
  • Złożoność przestrzenna: O(1), ponieważ jest to algorytm sortujący na miejscu.
  • Stabilność: Jest stabilny, zachowuje kolejność elementów o równych wartościach.

Początkowy zestaw danych:

5, 12, 3, 55, 1

Krok 1: Pomijamy pierwszy element i lądujemy na pozycji o wartości 12:

5, 12, 3, 55, 1
Sprawdzamy, czy 12 jest większe lub równe 5. Jest to prawda, więc wykonujemy krok w przód.

Krok 2: Przesuwamy się do wartości 3:

5, 12, 3, 55, 1
Sprawdzamy, czy 3 jest większe lub równe 12. Jest to fałsz, więc zamieniamy elementy miejscami.
5, 3, 12, 55, 1
Teraz sprawdzamy, czy 3 jest większe lub równe 5. Jest to fałsz, więc ponownie zamieniamy elementy miejscami.
3, 5, 12, 55, 1

Krok 3: Przesuwamy się do wartości 55:

3, 5, 12, 55, 1
Sprawdzamy, czy 55 jest większe lub równe 12. Jest to prawda, więc wykonujemy krok w przód.

Krok 4: Przesuwamy się do wartości 1:

3, 5, 12, 55, 1
Sprawdzamy, czy 1 jest większe lub równe 55. Jest to fałsz, więc zamieniamy elementy miejscami.
3, 5, 12, 1, 55
Teraz sprawdzamy, czy 1 jest większe lub równe 12. Jest to fałsz, więc zamieniamy elementy miejscami.
3, 5, 1, 12, 55
Kontynuujemy proces. Sprawdzamy, czy 1 jest większe lub równe 5. Jest to fałsz, więc zamieniamy elementy miejscami.
3, 1, 5, 12, 55
W końcu sprawdzamy, czy 1 jest większe lub równe 3. Jest to fałsz, więc zamieniamy elementy miejscami.
1, 3, 5, 12, 55

Po wykonaniu wszystkich kroków, wszystkie elementy zostały prawidłowo posortowane rosnąco:

1, 3, 5, 12, 55

Sortowanie gnoma jest bardzo intuicyjne i łatwe do implementacji, ale nie jest wydajne dla dużych list ze względu na swoją kwadratową złożoność czasową. Jest jednak efektywny w przypadku list prawie posortowanych.

Sortowanie przez spanie (Sleep Sort)

Sortowanie przez spanie jest bardziej nietypowym i humorystycznym algorytmem sortowania, który wykorzystuje czas jako kluczowy element do porządkowania danych. Jest to algorytm niestandardowy i nie jest zalecany do poważnego użycia, głównie ze względu na jego niestabilność i zależność od czasu wykonania.

Jak działa sortowanie przez spanie:
  1. Przypisanie wartości do czasu: Każda wartość w tablicy jest przekształcana na jednostkę czasu (np. milisekundy).
  2. Tworzenie wątków lub procesów: Dla każdej wartości tworzony jest osobny wątek lub proces, który „zamraża” wykonanie na czas odpowiadający wartości.
  3. „Spanie” i wypisywanie: Każdy wątek/proces „śpi” przez czas proporcjonalny do swojej wartości, a po obudzeniu wypisuje swoją wartość.
  4. Wynik: Wartości są wypisywane (lub zbierane) w kolejności od najmniejszej do największej, opartej na czasie, jaki upłynął od rozpoczęcia algorytmu do obudzenia wątku.
Właściwości algorytmu:
  • Złożoność czasowa: Teoretycznie O(n), ale w praktyce zależy od mechanizmu wykonania wątków/procesów i dokładności zegara systemowego.
  • Złożoność przestrzenna: Zależna od liczby tworzonych wątków/procesów.
  • Niezawodność: Niska, ponieważ wynik jest zależny od wielu zmiennych zewnętrznych i zachowania systemu.
Przykład z liczbami: 5, 12, 3, 55, 1

Załóżmy, że każda jednostka liczby odpowiada jednej milisekundzie.

  1. Start algorytmu: Rozpoczynamy równocześnie pięć wątków/procesów, każdy „śpi” przez czas odpowiadający danej liczbie.
    • Wątek dla liczby 5 śpi przez 5 ms.
    • Wątek dla liczby 12 śpi przez 12 ms.
    • Wątek dla liczby 3 śpi przez 3 ms.
    • Wątek dla liczby 55 śpi przez 55 ms.
    • Wątek dla liczby 1 śpi przez 1 ms.
  2. Kolejność obudzenia:
    • Najpierw obudzi się wątek dla liczby 1 (po 1 ms), następnie 3 (po 3 ms), 5 (po 5 ms), 12 (po 12 ms), a na końcu 55 (po 55 ms).
  3. Wypisywanie wartości:
    • Wartości są wypisywane w kolejności ich „obudzenia”: 1, 3, 5, 12, 55.

Wynikiem jest posortowana tablica: 1,3,5,12,55

Sortowanie przez spanie jest bardziej ciekawostką programistyczną niż praktycznym algorytmem sortowania. Jego wydajność i niezawodność są bardzo niskie, a działanie zależy od wielu czynników zewnętrznych, co czyni go niepraktycznym w większości zastosowań.

Sortowanie przez wstrząsanie (Cocktail Shaker Sort)

Sortowanie przez wstrząsanie, znane również jako sortowanie koktajlowe, jest wariacją sortowania bąbelkowego. Podobnie jak w sortowaniu bąbelkowym, porównuje ono pary sąsiednich elementów i zamienia je miejscami, jeśli są w złej kolejności. Kluczową różnicą jest to, że sortowanie przez wstrząsanie przeprowadza dwukierunkowe przejścia po liście – najpierw w górę, a następnie w dół. Dzięki temu szybciej przemieszczane są zarówno najmniejsze, jak i największe elementy.

Jak działa sortowanie przez wstrząsanie:
  1. Przejście w górę: Porównywane są sąsiednie elementy i zamieniane miejscami, jeśli są w złej kolejności, podobnie jak w sortowaniu bąbelkowym. To przejście porusza się od początku do końca listy.
  2. Przejście w dół: Po zakończeniu pierwszego przejścia, algorytm zmienia kierunek i przeprowadza kolejne przejście od końca do początku listy, ponownie zamieniając elementy, które są w złej kolejności.
  3. Powtarzanie: Proces jest powtarzany, zmieniając kierunki, aż lista zostanie całkowicie posortowana.
Właściwości algorytmu:
  • Złożoność czasowa: O(n²) w najgorszym przypadku, podobnie jak w sortowaniu bąbelkowym.
  • Złożoność przestrzenna: O(1), ponieważ jest to algorytm sortujący na miejscu.
  • Stabilność: Jest stabilny, zachowuje kolejność równych elementów.
Przykład z liczbami: 5, 12, 3, 55, 1

Przyjrzyjmy się, jak sortowanie przez wstrząsanie działałoby na przykładowym ciągu liczb.

Początkowy zestaw danych:

5, 12, 3, 55, 1

Krok 1: Rozpoczynamy od lewej strony i porównujemy wartości ze sobą:

  • 5 > 12? Nie, więc nie zamieniamy.
  • 12 > 3? Tak, więc zamieniamy cyfry miejscami: 5, 3, 12, 55, 1
  • 12 > 55? Nie, więc nie zamieniamy.
  • 55 > 1? Tak, więc zamieniamy cyfry miejscami oraz zmieniamy kierunek ruchu, ostatni element nie będzie już sprawdzany: 5, 3, 12, 1, 55

Krok 2: Zmieniamy kierunek i porównujemy wartości ze sobą w kierunku przeciwnym:

  • 1 < 12? Tak, ale idziemy dalej w kierunku przeciwnym.
  • 12 > 3? Tak, więc zamieniamy: 5, 3, 1, 12, 55
  • 3 > 5? Nie, więc idziemy dalej.
  • 5 > 3? Tak, więc zamieniamy: 5, 1, 3, 12, 55
  • 5 > 1? Tak, więc zamieniamy: 1, 5, 3, 12, 55 i zmieniamy kierunek ruchu, pierwszy element nie będzie już sprawdzany.

Krok 3: Znowu zmieniamy kierunek i kontynuujemy sortowanie:

  • 5 > 3? Tak, więc zamieniamy: 1, 3, 5, 12, 55
  • 3 > 5? Nie, więc nie zamieniamy i kontynuujemy.
  • Skoro wszystkie elementy są już prawidłowo posortowane, algorytm dobiega końca.

Końcowy rezultat wygląda następująco: 1, 3, 5, 12, 55

Sortowanie przez wstrząsanie jest nieco bardziej efektywne niż klasyczne sortowanie bąbelkowe, ponieważ zmniejsza ilość przejść potrzebnych do przesunięcia elementów na odpowiednie pozycje, zwłaszcza w przypadku elementów „ciężkich” (dużych wartości) i „lekkich” (małych wartości). Jest jednak nadal niewydajne dla dużych zestawów danych ze względu na swoją kwadratową złożoność czasową.

Sortowanie głupie (Stupid Sort)

Sortowanie głupie zadziwiająco przypomina sortowanie bąbelkowe. Weryfikujemy sąsiednie pary elementów, jeżeli są nieuporządkowane zamieniamy je miejscami i całą operację rozpoczynamy od początku. Jeżeli przeglądnąłem wszystkie pary w zbiorze i nie wykonałem żadnych zamian to algorytm kończy swoje działanie.

Początkowy zestaw danych:

5, 12, 3, 55, 1

Krok 1: Analizujemy sąsiadujące ze sobą elementy:

  • 5 > 12? Nie, więc analizujemy kolejną parę.
  • 12 > 3? Tak, więc zamieniamy elementy miejscami i rozpoczynamy analizę od nowa: 5, 3, 12, 55, 1

Po resecie:

  • 5 > 3? Tak, więc zamieniamy elementy i rozpoczynamy analizę od nowa: 3, 5, 12, 55, 1

Kontynuujemy bez restartu, ponieważ 5 nie jest większe od 3:

  • 5 < 12? Tak, więc analizujemy kolejną parę.
  • 12 < 55? Tak, więc analizujemy kolejną parę.
  • 55 > 1? Tak, więc zamieniamy elementy miejscami i rozpoczynamy analizę od nowa: 3, 5, 12, 1, 55

Po resecie:

  • 3 < 5? Tak, więc analizujemy kolejną parę.
  • 5 < 12? Tak, więc analizujemy kolejną parę.
  • 12 > 1? Tak, więc zamieniamy elementy miejscami i rozpoczynamy analizę od nowa: 3, 5, 1, 12, 55

Po resecie:

  • 3 < 5? Tak, więc analizujemy kolejną parę.
  • 5 > 1? Tak, więc zamieniamy elementy miejscami i rozpoczynamy analizę od nowa: 3, 1, 5, 12, 55

Po resecie:

  • 3 > 1? Tak, więc zamieniamy elementy miejscami i rozpoczynamy analizę od nowa: 1, 3, 5, 12, 55

Teraz, kiedy zaczynamy analizę od początku:

  • 1 < 3? Tak, więc analizujemy kolejną parę.
  • 3 < 5? Tak, więc analizujemy kolejną parę.
  • 5 < 12? Tak, więc analizujemy kolejną parę.
  • 12 < 55? Tak, więc kończymy algorytm, ponieważ wszystkie elementy są już posortowane.

Końcowy wynik:

1, 3, 5, 12, 55

Tak więc, stosując sortowanie głupie, osiągnęliśmy cel i posortowaliśmy zbiór danych od najmniejszego do największego elementu. Ten sposób sortowania, mimo swojej niewydajności, ostatecznie doprowadził do prawidłowo uporządkowanego zestawu.