Sortowanie na maturze z informatyki: wybór, wstawianie, scalanie

Sortowanie na maturze z informatyki rzadko sprowadza się do przepisania gotowego algorytmu. Częściej trzeba wskazać, który z nich zachowa się lepiej na opisanych danych, albo prześledzić kilka przebiegów i podać stan tablicy. Oba te zadania wymagają rozumienia mechaniki, a nie zapamiętanego kodu.

Sortowanie przez wybór wykonuje zawsze tyle samo porównań

Algorytm dzieli tablicę na część uporządkowaną z lewej i nieuporządkowaną z prawej. W każdym przebiegu przeszukuje całą część nieuporządkowaną, znajduje w niej element najmniejszy i zamienia go z pierwszym elementem tej części. Po każdym przebiegu część uporządkowana rośnie o jeden.

Ważną cechą tego algorytmu jest niezależność od danych wejściowych. Tablica już posortowana wymaga dokładnie tylu samo porównań co tablica ułożona odwrotnie, ponieważ znalezienie minimum zawsze oznacza przejrzenie całej reszty. Zamian jest za to niewiele, co najwyżej jedna na przebieg. To czyni sortowanie przez wybór sensownym wyborem wtedy, gdy pojedyncze przestawienie elementu jest kosztowne, a porównanie tanie.

Sortowanie przez wstawianie zależy od tego, jak dane wyglądają na starcie

Tutaj algorytm bierze kolejny element z części nieuporządkowanej i wsuwa go we właściwe miejsce części uporządkowanej, przesuwając większe elementy o jedną pozycję w prawo. Działa tak, jak układa się karty trzymane w ręce.

Liczba operacji zależy wprost od stopnia uporządkowania danych. Dla tablicy już posortowanej każdy element zatrzymuje się po pierwszym porównaniu, więc praca rośnie liniowo z liczbą elementów. Dla tablicy uporządkowanej odwrotnie każdy element wędruje przez cały uporządkowany prefiks i liczba operacji rośnie kwadratowo. Ta wrażliwość na dane jest zaletą, bo w zadaniach o dopisaniu kilku rekordów do gotowej, posortowanej listy sortowanie przez wstawianie bije pozostałe metody.

Dwa proste algorytmy obok siebie

Wiersz o stabilności bywa pomijany w powtórce, a rozstrzyga w zadaniach o sortowaniu według dwóch kryteriów. Algorytm stabilny zachowuje wzajemną kolejność elementów o równych kluczach, więc posortowanie najpierw po nazwisku, a potem po klasie, zostawi w obrębie każdej klasy porządek alfabetyczny. Algorytm niestabilny tej gwarancji nie daje i drugie sortowanie potrafi rozsypać wynik pierwszego.

Sortowanie przez scalanie działa w innym rzędzie wielkości

Sortowanie przez scalanie dzieli tablicę na połowy, sortuje każdą z nich tą samą metodą, a następnie scala dwie uporządkowane części w jedną. Liczba poziomów podziału rośnie logarytmicznie z liczbą elementów, a na każdym poziomie scalanie przechodzi przez wszystkie elementy raz, co daje rząd n log n niezależnie od układu danych wejściowych.

Cena jest pamięciowa: scalanie wymaga miejsca na tablicę pomocniczą. W zadaniu proszącym o porównanie metod ta cena jest właśnie tym, co odróżnia dobrą odpowiedź od wyliczanki. Sam mechanizm podziału na podproblemy opisuje szerzej wpis o rekurencji na maturze.

Co znaczy „porównaj efektywność" w poleceniu

Porównanie efektywności nie wymaga dowodu formalnego. Wymaga wskazania, jak liczba operacji zmienia się wraz ze wzrostem liczby danych, i powiązania tego z konkretną sytuacją z zadania. Odpowiedź wymieniająca same rzędy złożoności, bez odniesienia do opisanych danych, odpowiada na inne pytanie niż zadane.

Druga rzecz, o której łatwo zapomnieć: rząd złożoności mówi o zachowaniu przy rosnącej liczbie danych, a nie o czasie na konkretnej tablicy. Dla kilkunastu elementów algorytm kwadratowy bywa szybszy od scalania, bo nie płaci za podział i pamięć pomocniczą. W zadaniu o małej, prawie uporządkowanej tablicy poprawna odpowiedź może więc wskazywać wstawianie, mimo gorszego rzędu w najgorszym przypadku.

Jak prześledzić przebiegi na kartce

Zadania „na kartce" zwykle proszą o stan tablicy po określonej liczbie przebiegów. Najbezpieczniej zapisywać go w tabeli, wiersz na przebieg, i zaznaczać granicę między częścią uporządkowaną a resztą. Przy sortowaniu przez wybór granica przesuwa się o jeden po każdej zamianie. Przy wstawianiu przesuwa się po każdym wstawieniu, ale elementy wewnątrz prefiksu zmieniają pozycje.

Konwencje zapisu samego algorytmu są takie same jak przy każdym innym zadaniu algorytmicznym i opisuje je wpis o zasadach zapisu pseudokodu.

Najczęstsze pytania

Które sortowanie jest szybsze: przez wybór czy przez wstawianie?

To zależy od danych. W najgorszym przypadku oba wykonują liczbę operacji rosnącą kwadratowo. Na danych prawie uporządkowanych wstawianie jest wyraźnie szybsze, bo kończy po pierwszym porównaniu dla większości elementów. Wybór zachowuje się tak samo niezależnie od układu danych.

Czy trzeba znać na pamięć kod algorytmów sortowania?

Nie na pamięć, ale trzeba umieć go zapisać samodzielnie w pseudokodzie albo w wybranym języku. Ocenia się poprawność algorytmu, czyli warunki pętli, zakresy indeksów i moment zamiany, a nie zgodność ze wzorcem z podręcznika.

Co to znaczy, że algorytm sortowania jest stabilny?

Że elementy o równych kluczach zachowują wzajemną kolejność z wejścia. Ma to znaczenie przy sortowaniu według kilku kryteriów po kolei. Sortowanie przez wstawianie oraz przez scalanie są stabilne, klasyczne sortowanie przez wybór z zamianą elementów nie jest.

Czy sortowanie przez scalanie zawsze opłaca się bardziej?

Przy dużych zbiorach zwykle tak, bo liczba operacji rośnie znacznie wolniej. Przy małych tablicach narzut podziału i dodatkowa pamięć potrafią przeważyć, a przy danych prawie uporządkowanych wstawianie kończy pracę szybciej. Odpowiedź w zadaniu powinna odwoływać się do rozmiaru i układu danych opisanych w treści.

Jak zapisać liczbę porównań, gdy zadanie prosi o wzór?

Wyprowadzając go z liczby przebiegów i liczby porównań w każdym z nich, a nie zgadując gotową formułę. Przy sortowaniu przez wybór pierwszy przebieg przegląda n minus jeden elementów, drugi o jeden mniej, i tak dalej, co daje sumę ciągu malejącego o jeden.

Jak to sprawdzisz w zdawce

W zdawce zadania z sortowania rozbite są na elementy rubryki, więc osobno oceniany jest pomysł algorytmu, osobno zakresy indeksów i warunki pętli, a osobno uzasadnienie wyboru metody. Kod uruchamiany jest na zestawie danych obejmującym przypadki graniczne, w tym tablicę pustą i już posortowaną. Uzasadnienia ocenia model wedle tej samej rubryki, a punktów nie może być więcej, niż przewiduje zadanie. Ocenę możesz zgłosić do sprawdzenia. Metodę opisuje strona o zasadach oceniania.

Sprawdź to na porównaniu dwóch metod: uzasadnij wybór algorytmu dla małej, prawie uporządkowanej tablicy i zobacz, czy w odpowiedzi zabrakło odniesienia do danych z treści, czy dopiero rzędu liczby operacji.