Proste Algorytmy Sortowania

Omówiliśmy już Sortowanie Bąbelkowe, które jest chyba najgorsze z możliwych. Zaraz obok niego stoją dwa algorytmy, z którymi będziesz miał do czynienia wielokrotnie. Mają taką samą złożoność czasową, czyli $O(N^2)$, jednak w praktyce zachowują się różnie.

1. Sortowanie przez Wybieranie (Selection Sort)

Działa identycznie do tego, jak układasz karty w ręce. Masz pełno kart na stole. Przeszukujesz je, wybierasz tę najmniejszą, i wstawiasz na pierwsze miejsce. Następnie z pozostałych szukasz najmniejszej i wstawiasz na drugie, itd.

W praktyce szukamy minimum (indeksu), a następnie zamieniamy (swap) z miejscem, na które ma trafić.

Python

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # Zamieniamy miejscami
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

C++

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j; 
            }
        }
        
        swap(arr[min_idx], arr[i]);
    }
}

2. Sortowanie przez Wstawianie (Insertion Sort)

Bierzemy każdą kolejną liczbę i "wpychamy" ją w posortowaną już lewą połówkę, dopóki nie znajdzie odpowiedniego (dla swojej wielkości) miejsca. Przypomina to wrzucanie książki do stojącego już szeregu tomów encyklopedii.

Python

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        wpychany = arr[i]
        j = i - 1
        
        while j >= 0 and arr[j] > wpychany:
            arr[j + 1] = arr[j]
            j -= 1
            
        arr[j + 1] = wpychany

C++

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

[!TIP] Dlaczego mówi się, że Insertion Sort bywa przydatny? Bo jeśli wrzucimy do niego tablicę, która jest już "prawie w całości" posortowana, pętla while od razu będzie się przerywać. W takich szczególnych wypadkach czas jego wykonania dąży do fenomenalnego, liniowego O(N)!