jario_

Sortowanie bąbelkowe, przez wybór i wstawianie w Javie

Zaktualizowano 22 października 2026

Sortowanie bąbelkowe, sortowanie przez wybór i sortowanie przez wstawianie to trzy klasyczne proste algorytmy sortowania, a w Javie każdy z nich zajmuje tylko kilka linijek. Na przykład wyszukiwanie binarne potrzebuje posortowanej tablicy. Ale jak posortować tablicę? W tym artykule poznasz wszystkie trzy metody. Nie są najszybsze, ale łatwo je zrozumieć i pojawiają się prawie na każdym egzaminie.

Sortowanie bąbelkowe (Bubble Sort)

Wszystkie trzy metody sortują w miejscu (in place): pracują bezpośrednio na przekazanej tablicy i poza kilkoma zmiennymi nie potrzebują dodatkowej pamięci. Ich podstawowym elementem jest zamiana dwóch elementów miejscami za pomocą zmiennej pomocniczej.

Sortowanie bąbelkowe działa w przebiegach od lewej do prawej i zawsze porównuje dwóch sąsiadów. Jeśli lewy element jest większy, zamienia je miejscami. Po pierwszym przebiegu największy element stoi na samym końcu po prawej, po drugim drugi co do wielkości stoi przed nim i tak dalej. Dlatego przebieg i musi porównywać już tylko do a.length - 1 - i.

Wcześniejsze zakończenie: jeśli w przebiegu nie było ani jednej zamiany, tablica jest posortowana i pętla kończy się przez break.

import java.util.Arrays;
public class Main {    public static void bubbleSort(int[] a) {        for (int i = 0; i < a.length - 1; i++) {            boolean swapped = false;            for (int j = 0; j < a.length - 1 - i; j++) {                if (a[j] > a[j + 1]) {                    int tmp = a[j];                    a[j] = a[j + 1];                    a[j + 1] = tmp;                    swapped = true;                }            }            System.out.println("Pass " + (i + 1) + ": " + Arrays.toString(a));            if (!swapped) {                break;            }        }    }
    public static void main(String[] args) {        int[] a = {6, 2, 9, 1, 5};        bubbleSort(a);    }}

Sortowanie przez wybór (Selection Sort)

Sortowanie przez wybór szuka w nieposortowanej reszcie indeksu najmniejszego elementu i zamienia go na pierwszą wolną pozycję. Po lewej rośnie w ten sposób posortowany obszar, krok po kroku o jeden element.

W każdym kroku jest co najwyżej jedna zamiana, łącznie więc tylko n - 1. Za to sortowanie przez wybór zawsze wykonuje tyle samo porównań, nawet gdy tablica jest już posortowana: czy element jest najmniejszy, wie dopiero wtedy, gdy obejrzy całą resztę.

import java.util.Arrays;
public class Main {    public static void selectionSort(int[] a) {        for (int i = 0; i < a.length - 1; i++) {            int min = i;            for (int j = i + 1; j < a.length; j++) {                if (a[j] < a[min]) {                    min = j;                }            }            int tmp = a[i];            a[i] = a[min];            a[min] = tmp;            System.out.println("Step " + (i + 1) + ": " + Arrays.toString(a));        }    }
    public static void main(String[] args) {        int[] a = {6, 2, 9, 1, 5};        selectionSort(a);    }}

Sortowanie przez wstawianie (Insertion Sort)

Sortowanie przez wstawianie działa jak układanie kart w ręce: po lewej leży posortowany obszar. Następny element zapamiętujesz w key. Wszystkie większe elementy w posortowanym obszarze przesuwają się o jedną pozycję w prawo, a key trafia w powstałą lukę.

Elementy są przy tym przesuwane, a nie zamieniane. Warunek j >= 0 && a[j] > key musi mieć dokładnie tę kolejność: jeśli j wynosi już -1, && nie dopuszcza do odczytu a[-1].

Jeśli tablica jest prawie posortowana, prawie nic nie trzeba przesuwać. Wtedy sortowanie przez wstawianie jest bardzo szybkie.

import java.util.Arrays;
public class Main {    public static void insertionSort(int[] a) {        for (int i = 1; i < a.length; i++) {            int key = a[i];            int j = i - 1;            while (j >= 0 && a[j] > key) {                a[j + 1] = a[j];                j--;            }            a[j + 1] = key;            System.out.println("Insert " + key + ": " + Arrays.toString(a));        }    }
    public static void main(String[] args) {        int[] a = {6, 2, 9, 1, 5};        insertionSort(a);    }}

Złożoność i stabilność

Dla tablicy z n elementami sortowanie bąbelkowe wykonuje w najgorszym przypadku (n - 1) + (n - 2) + … + 1 = n · (n - 1) / 2 porównań. To rośnie jak n²: przy dwa razy większej liczbie elementów trwa to około cztery razy dłużej. Zapisuje się to jako O(n²). Jak zrobić to w O(n log n), pokazują sortowanie przez scalanie i quicksort.

  • Sortowanie bąbelkowe (z wcześniejszym zakończeniem): najlepszy przypadek O(n), gdy tablica jest już posortowana, najgorszy O(n²), stabilne.
  • Sortowanie przez wybór: zawsze O(n²) porównań, także w najlepszym przypadku, niestabilne.
  • Sortowanie przez wstawianie: najlepszy przypadek O(n), gdy tablica jest już posortowana, najgorszy O(n²), gdy jest posortowana odwrotnie, stabilne.

Stabilne oznacza: elementy o tym samym kluczu zachowują swoją kolejność. Ma to znaczenie, gdy sortujesz obiekty według jednego atrybutu, na przykład ranking według punktów. Sortowanie bąbelkowe i przez wstawianie zamieniają lub przesuwają element tylko wtedy, gdy jest ściśle większy. Sortowanie przez wybór nie jest stabilne, bo zamiana może przerzucić element daleko do tyłu, obok równych mu elementów.

import java.util.Arrays;
public class Main {    record Card(String suit, int rank) {}
    // Stable: equal ranks keep their order.    public static void insertionSort(Card[] cards) {        for (int i = 1; i < cards.length; i++) {            Card key = cards[i];            int j = i - 1;            while (j >= 0 && cards[j].rank() > key.rank()) {                cards[j + 1] = cards[j];                j--;            }            cards[j + 1] = key;        }    }
    // Not stable: the swap can jump over equal ranks.    public static void selectionSort(Card[] cards) {        for (int i = 0; i < cards.length - 1; i++) {            int min = i;            for (int j = i + 1; j < cards.length; j++) {                if (cards[j].rank() < cards[min].rank()) {                    min = j;                }            }            Card tmp = cards[i];            cards[i] = cards[min];            cards[min] = tmp;        }    }
    public static void main(String[] args) {        Card[] cards = {            new Card("hearts", 5), new Card("spades", 5), new Card("clubs", 2)        };        Card[] a = cards.clone();        insertionSort(a);        System.out.println("Insertion: " + Arrays.toString(a));        Card[] b = cards.clone();        selectionSort(b);        System.out.println("Selection: " + Arrays.toString(b));    }}

Dwie karty o randze 5: sortowanie przez wstawianie zostawia kier przed pikiem, sortowanie przez wybór zamienia je miejscami.

Typowe błędy

  • Wewnętrzna pętla o krok za daleko

    Jeśli porównujesz a[j] z a[j + 1], j może biec tylko dopóki j < a.length - 1 - i. Z j < a.length - i pierwszy przebieg sięga do a[a.length] i dostajesz ArrayIndexOutOfBoundsException. I odwrotnie: przy zbyt małej granicy ostatnia para nigdy nie zostanie porównana, a wynik jest źle posortowany, bez żadnego komunikatu o błędzie.

  • Zapamiętana wartość zamiast indeksu

    W sortowaniu przez wybór min musi być indeksem najmniejszego elementu, a nie jego wartością. Znając tylko wartość, na końcu nie wiesz, z którą pozycją zrobić zamianę:

    int min = a[i];   // wrong: valueint min = i;      // right: index, compare a[j] < a[min]

  • Utrata stabilności przez >=

    Jeśli sortowanie przez wstawianie przesuwa elementy przy a[j] >= key zamiast a[j] > key, tablica jest wprawdzie posortowana, ale równe elementy wyprzedzają się nawzajem. Przy liczbach tego nie widać, przy rankingu z równą liczbą punktów już tak. To samo dotyczy sortowania bąbelkowego: zamieniaj tylko przy >.

Zadania z tego tematu

Przećwicz to, czego się nauczyłeś, od razu w przeglądarce. Testy natychmiast sprawdzają twoje rozwiązanie.

Powiązane artykuły