Sortowanie to fundamentalny problem w informatyce, który polega na uporządkowaniu elementów w danym zbiorze zgodnie z określonym porządkiem, najczęściej rosnącym lub malejącym. Algorytmy sortujące są jednymi z najczęściej omawianych i analizowanych algorytmów w świecie programowania, ponieważ są szeroko stosowane w różnych dziedzinach, od baz danych po przetwarzanie danych w czasie rzeczywistym. W tej lekcji omówimy kilka popularnych algorytmów sortujących, takich jak sortowanie bąbelkowe, sortowanie przez wstawianie, sortowanie szybkie i sortowanie przez scalanie. Przedstawimy szczegółową analizę każdego z tych algorytmów, w tym ich złożoność czasową i pamięciową, a także omówimy ich zalety i wady w różnych sytuacjach.

Sortowanie bąbelkowe (Bubble Sort)

Sortowanie bąbelkowe to jeden z najprostszych i najbardziej intuicyjnych algorytmów sortujących. Działa na zasadzie porównywania sąsiednich elementów i zamieniania ich miejscami, jeśli są w złej kolejności. Proces ten jest powtarzany wielokrotnie, aż wszystkie elementy zostaną uporządkowane.

Implementacja sortowania bąbelkowego

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

Analiza złożoności czasowej

• Najlepszy przypadek: O(n), gdy dane są już posortowane.
• Najgorszy przypadek: O(n²), gdy dane są posortowane w odwrotnej kolejności.
• Średni przypadek: O(n²), ponieważ w większości przypadków algorytm musi przejść przez wiele iteracji, aby uporządkować dane.

Złożoność pamięciowa

Złożoność pamięciowa wynosi O(1), ponieważ algorytm działa w miejscu (in-place) i nie wymaga dodatkowej przestrzeni pamięci.

Zalety i wady

• Zalety: Łatwy do zrozumienia i zaimplementowania, działa dobrze na małych zbiorach danych.
• Wady: Bardzo nieefektywny dla dużych zbiorów danych, złożoność czasowa O(n²) sprawia, że jest niepraktyczny w większości rzeczywistych zastosowań.

Sortowanie przez wstawianie (Insertion Sort)

Sortowanie przez wstawianie polega na wstawianiu każdego elementu na odpowiednie miejsce w już posortowanej części tablicy. Jest to podejście inkrementacyjne, które działa dobrze na małych zbiorach danych lub gdy dane są już częściowo posortowane.

Implementacja sortowania przez wstawianie

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

Analiza złożoności czasowej

• Najlepszy przypadek: O(n), gdy dane są już posortowane.
• Najgorszy przypadek: O(n²), gdy dane są posortowane w odwrotnej kolejności.
• Średni przypadek: O(n²), ponieważ algorytm wymaga przesunięcia wielu elementów w najgorszym scenariuszu.

Złożoność pamięciowa

Złożoność pamięciowa wynosi O(1), ponieważ algorytm działa w miejscu i nie wymaga dodatkowej pamięci.

Zalety i wady

• Zalety: Prosty do zaimplementowania, efektywny dla małych zbiorów danych i danych częściowo posortowanych.
• Wady: Niska wydajność dla dużych zbiorów danych, złożoność czasowa O(n²) sprawia, że jest mniej efektywny w porównaniu z bardziej zaawansowanymi algorytmami.

Sortowanie szybkie (Quick Sort)

Sortowanie szybkie (Quick Sort) to jeden z najwydajniejszych algorytmów sortujących, który wykorzystuje technikę „dziel i zwyciężaj”. Polega na wyborze elementu zwanego pivotem i podziale danych na dwie części: mniejsze od pivota i większe od pivota. Następnie sortuje każdą część rekurencyjnie.

Implementacja sortowania szybkiego

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; ++j) {
        if (arr[j] < pivot) {
            ++i;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Analiza złożoności czasowej

• Najlepszy przypadek: O(n log n), gdy pivot dzieli dane na dwie równe części.
• Najgorszy przypadek: O(n²), gdy pivot jest zawsze najgorszym możliwym wyborem (np. najmniejszy lub największy element).
• Średni przypadek: O(n log n), co sprawia, że jest bardzo wydajny w większości przypadków.

Złożoność pamięciowa

Złożoność pamięciowa wynosi O(log n) w przypadku rekurencyjnego stosu wywołań, co czyni go bardziej pamięciooszczędnym niż niektóre inne algorytmy sortowania.

Zalety i wady

• Zalety: Bardzo wydajny, szczególnie dla dużych zbiorów danych, dobrze zoptymalizowany w większości przypadków.
• Wady: W najgorszym przypadku może mieć złożoność O(n²), ale można to zminimalizować poprzez losowy wybór pivota.

Sortowanie przez scalanie (Merge Sort)

Sortowanie przez scalanie (Merge Sort) to algorytm sortujący również wykorzystujący technikę „dziel i zwyciężaj”. Działa na zasadzie dzielenia zbioru danych na mniejsze części, sortowania każdej części, a następnie scalania ich w jedną posortowaną całość.

Implementacja sortowania przez scalanie

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int* L = new int[n1];
    int* R = new int[n2];
    
    for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
    for (int i = 0; i < n2; ++i) R[i] = arr[mid + 1 + i];
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    
    delete[] L;
    delete[] R;
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

Analiza złożoności czasowej

• Najlepszy przypadek: O(n log n).
• Najgorszy przypadek: O(n log n), co oznacza, że algorytm jest bardzo stabilny pod względem wydajności.
• Średni przypadek: O(n log n), co czyni go jednym z najbardziej efektywnych algorytmów sortujących.

Złożoność pamięciowa

Złożoność pamięciowa wynosi O(n) ze względu na dodatkową przestrzeń potrzebną do scalania danych.

Zalety i wady

• Zalety: Stabilny i wydajny, niezależnie od początkowego rozkładu danych.
• Wady: Wymaga dodatkowej pamięci, co czyni go mniej efektywnym w kontekście pamięciooszczędności.

Podsumowanie

Sortowanie jest kluczowym zagadnieniem w informatyce, a różne algorytmy sortujące mają swoje unikalne zalety i wady. W tej lekcji omówiliśmy sortowanie bąbelkowe, sortowanie przez wstawianie, sortowanie szybkie i sortowanie przez scalanie. Każdy z tych algorytmów ma swoje zastosowania w zależności od rozmiaru danych i wymagań dotyczących wydajności. Dzięki tej wiedzy możesz wybrać odpowiedni algorytm do konkretnego problemu, optymalizując czas i pamięć w swoich aplikacjach.

Następna lekcja ==> Struktury danych o dynamicznej budowie