Logo Platforma Edukacyjna – kursy do matury i egzaminów z informatyki
AlgorytmySortowanie

Porównanie algorytmów sortowania

Wybierz od dwóch do czterech sortowań i puść je na tej samej tablicy. Zobaczysz, które dobiegnie do mety pierwsze i ile porównań oraz zamian wykona po drodze.

  1. Sortowanie bąbelkowe

    5
    3
    8
    1
    9
    2
    7
    4
    6
    Porównania
    0
    Zamiany i zapisy
    0

  2. Sortowanie przez wstawianie

    5
    3
    8
    1
    9
    2
    7
    4
    6
    Porównania
    0
    Zamiany i zapisy
    0

  3. Sortowanie przez scalanie

    5
    3
    8
    1
    9
    2
    7
    4
    6
    Porównania
    0
    Zamiany i zapisy
    0

  4. Sortowanie szybkie

    5
    3
    8
    1
    9
    2
    7
    4
    6
    Porównania
    0
    Zamiany i zapisy
    0
1 / 54

Jak czytać wyścig

  • Każdy tor sortuje tę samą tablicę, więc różnica w wyniku bierze się wyłącznie z algorytmu.
  • Zegar odmierza takty. Jeden takt to jedno porównanie albo jedna zamiana lub zapis w tablicy.
  • Pod torem widać dwa liczniki: porównania oraz zamiany razem z zapisami. Ich suma to liczba taktów, po której tor dobiega do mety.
  • Sortowanie przez zliczanie nie porównuje elementów wcale. Liczy wystąpienia wartości, dlatego wygrywa na tablicach z małym zakresem liczb.

Co warto sprawdzić

  • Wpisz tablicę już posortowaną, np. 1, 2, 3, 4, 5, 6, 7, 8, 9. Sortowanie przez wstawianie wykona wtedy tylko 8 porównań, a szybkie – aż 36, bo pivot z końca zakresu za każdym razem okazuje się największy.
  • Bąbelkowe i przez wybór wykonują 36 porównań przy każdej tablicy z 9 elementów, bo ich pętle nie zależą od danych. Różni je liczba zamian.
  • Odwróć tablicę: bąbelkowe zamienia wtedy każdą parę, czyli 36 razy, a przez wybór tylko 4 razy.

Zobacz także

Sortowanie bąbelkowe
Porównuje sąsiadów i zamienia ich miejscami, gdy stoją w niewłaściwej kolejności.O(n²)
Sortowanie przez wstawianie
Wstawia kolejny element w odpowiednie miejsce już uporządkowanego fragmentu.O(n²)
Sortowanie przez wybór
W każdej rundzie wybiera najmniejszy element z nieuporządkowanej części.O(n²)
Sortowanie przez scalanie
Dzieli dane na części, sortuje je rekurencyjnie i scala w całość.O(n log n)
Sortowanie szybkie
Pivot dzieli dane na dwa fragmenty, które są następnie sortowane rekurencyjnie.O(n log n) śr.
Sortowanie przez zliczanie
Zlicza wystąpienia wartości zamiast je porównywać; wymaga ograniczonego zakresu danych.O(n + k)