Zbierając jakieś dane w aplikacji i wyświetlając je, przychodzi czasem potrzeba ułożenia ich w odpowiedniej kolejności.

Przeczytaj jak się sortuje dane, co jest ważne w umiejętności sortowania i kiedy sortowanie jest niezbędne do działania programu.

Dane mogą trafiać do aplikacji w różny sposób. Mogą być one wpisane pojedynczo przez użytkownika, importowane z jakiegoś zewnętrznego źródła, lub wczytywane z bazy danych. Czasem będą one poukładane w kolejności chronologicznej, alfabetycznej, lub dowolnej innej, ale czasem będą zlepkiem różnych wpisów bez ładu.

Strategia

Aby uporządkować te dane niezbędne jest podjęcie decyzji w jaki sposób mają one zostać poukładane.

W przypadku prostych zbiorów na przykład tabeli imion [„Jadzia”, „Zosia”, „Ania”], lub liczb [5, 4, 8], wybór wydaje się być prosty, ale przyjrzyj się tabeli z datami:

["22.10.2018", "1.05.2001", "30.04.1998"]

Ułożenie jej w kolejności alfabetycznej da nam rezultat:

["1.05.2001", "22.10.2018", "30.04.1998"]

Nawet pozbywając się kropek i traktując daty jak zwykłe liczby (1052001, 22102018, 30041998) również nie otrzymamy kolejności chronologicznej.

Jak więc posortować te wartości?

Daty w systemach komputerowych zapisywane są jako liczba sekund które upłynęły od 1 stycznia 1970. Gdy przekształcimy zapis „1.05.2001” na liczbę sekund i według tego samego algorytmu przetworzymy pozostałe wartości, to sortowanie będzie już banalnie proste.

Ważne jest zatem jakie mamy dane i w zależności od tego musimy zastosować odpowiednią strategię sortowania.

 

Sortowanie danych skomplikowanych

Wiesz już jak ważna jest odpowiednia strategia przy sortowaniu.

W praktyce, aby uruchomić sortowanie zbioru danych, najczęściej uruchamia się funkcję sort(zbior_danych), lub podobną która wykonuje sortowanie domyślne.

W dokumentacji swojego języka programowania na pewno znajdziesz szczegóły jaka strategia jest przyjmowana domyślnie. W przypadku prostych list, czy tabel najprawdopodobniej zadziała ona zgodnie z oczekiwaniami.

Ale w przypadku danych bardziej rozbudowanych już nie koniecznie.

Wyobraź sobie elektroniczny dziennik z listą uczniów i ich ocenami z egzaminów.

Nazwisko	Imię	Matematyka	Język polski	Historia
Kowalski	Jan	3	5	4
Nowak	Michał	4	3	5
Potocka	Anna	3	5	5
Kowalski	Adam	5	3	2
Noga	Piotr	3	3	3

Jaką strategię przyjąć żeby otrzymać listę  uczniów od najlepszych do najgorszych?

Po pierwsze musimy ustalić co to znaczy „lepszy uczeń”, a co to znaczy „gorszy”.

Załóżmy że:

• Lepszy uczeń to ten który ma wyższą średnią z ocen od drugiego.
• Jeśli średnia obu porównywanych uczniów jest taka sama, to lepszy jest ten, który ma lepszą ocenę z języka polskiego.
• Jeśli ocena z języka polskiego jest taka sama, to lepszy jest ten, który ma lepszą ocenę z matematyki.

We wspomnianej wcześniej funkcji sort można dodatkowo podać informację w jaki sposób sortowanie ma się odbywać. Robi się to poprzez podanie funkcji, którą wewnętrzne mechanizmy polecenia sort mają użyć do porównania ze sobą dwóch elementów zbioru czyli tzw. comparer’a (comparator’a), a po polsku: „porównywacza”.

Comparer to prosta funkcja biorąca dwa elementy zbioru, porównująca je ze sobą i zwracająca informację który z tych elementów ma być wcześniej, a który dalej w kolejności.

Jeśli dla dwóch elementów ten pierwszy ma być wcześniej w hierarchii, comparer musi zwrócić wartość niższą od 0, jeśli dalej – musi zwrócić wyższą od 0, lub jeśli są jednakowe – wartość 0.

Tak więc nasz porównywacz dla uczniów musi porównać średnią ocen obu uczniów, i ewentualnie oceny z języka polskiego i matematyki.

Skoro wszystko jasne, to bierzemy się za kodowanie:

function PorownajUczniow(uczen1, uczen2){
}

Nasz porównywacz przyjmuje dwa parametry: uczen1 i uczen2, a zwraca wynik w postaci liczby całkowitej (ujemnej, 0, lub dodatniej w zależności od ocen uczniów).

Najpierw musimy policzyć średnią ocen obu uczniów:

var srednia1 = (uczen1.jezykPolski + uczen1.matematyka + uczen1.historia) / 3;
var srednia2 = (uczen2.jezykPolski + uczen2.matematyka + uczen2.historia) / 3;

if (srednia1 < srednia2)
  return -1;
else
if (srednia1 > srednia2)
  return 1;

Zgodnie z założeniami jeśli średnia pierwszego ucznia jest mniejsza zwracamy wynik ujemny, jeśli większa: dodatni i wychodzimy z funkcji.

Może się jednak zdarzyć, że średnia wyjdzie dokładnie taka sama. Wtedy porównujemy oceny z języka polskiego:

if (uczen1.jezykPolski < uczen2.jezykPolski)
   return -1;
else
if (uczen1.jezykPolski > uczen2.jezykPolski)
   return 1;

I znów różne oceny sprawiają, że wskazujemy na pierwszego ucznia, lub drugiego.

Ostatecznie porównujemy oceny z matematyki:

if (uczen1.matematyka < uczen2.matematyka)
   return -1;
else
if (uczen1.matematyka > uczen2.matematyka)
   return 1;

Jeśli nie jesteśmy w stanie wybrać lepszego ucznia na podstawie średniej ocen, ani ocen z przedmiotów, oznacza to, że są tak samo dobrzy. Ostatecznie nasza funkcja porównująca powinna zwrócić wartość 0.

return 0;

Całość naszego comparera wygląda więc następująco:

function PorownajUczniow(uczen1, uczen2)
{
   if (srednia1 < srednia2)
     return -1;
   else
   if (srednia1 > srednia2)
      return 1;
   if (uczen1.jezykPolski < uczen2.jezykPolski)
      return -1;
   else
   if (uczen1.jezykPolski > uczen2.jezykPolski)
      return 1;
   if (uczen1.matematyka < uczen2.matematyka)
      return -1;
   else
   if (uczen1.matematyka > uczen2.matematyka)
     return 1;
   return 0;
}

Ps. w funkcji tej celowo pominąłem  sprawdzenie jednej małej rzeczy. Domyślisz się której? O odpowiedzi poproszę w komentarzu.

Sortowanie nie tylko układa w kolejności

Układanie elementów zbioru w kolejności to dosyć istotny temat, ale jest jeszcze inne zastosowanie sortowania, jeszcze ważniejsze.

Bez sortowania danych utrudnione lub wręcz niemożliwe byłoby uruchamianie niektórych operacji na zbiorach np. wyszukiwania.

Wyobraź sobie bibliotekę szkolną z książkami ułożonymi w dowolny sposób, bez żadnej kolejności. Znalezienie w niej konkretnej książki wymagałoby sprawdzenia każdej po kolei i dopiero natrafiając na tą właściwą można byłoby zakończyć szukanie.

Jeśli mamy książki ułożone według nazwisk autorów, wystarczy poszukać gdzieś w okolicach pierwszej litery nazwiska pisarza, przejrzeć kilka pozycji i już. Mało tego… dzięki odpowiedniej kolejności możemy szybko sprawdzić czy dana książka jest w naszej kolekcji, czy nie.

Dokładnie tak samo działają mechanizmy wyszukiwania elementów w zbiorze danych.

Jeśli zbiór nie jest posortowany, szukanie może trwać długo, lub może w ogóle nie zadziałać.

Na deser

Sortowanie oryginału vs. sortowanie kopii

Zwróć uwagę, czy funkcja sortująca której używasz w swoim języku programowania sortuje tablicę którą jej wskażesz, czy zwraca jej posortowaną kopię, nie zmieniając oryginału.

W tym drugim przypadku wywołanie funkcji sort() bez przypisania nigdzie wyniku jej działania, może wyglądać jakby sortowanie nie zadziałało.

Nie zdziw się też, jeśli będziesz mieć do dyspozycji obie możliwości.

Uproszczone porównanie

Pisząc funkcję porównującą elementy na podstawie ich właściwości liczbowych, czasem warto pokusić się o uproszczony zapis w następującej postaci:

if (uczen1.srednia == uczen2.srednia)
   return 0;
else
   return uczen1.srednia - uczen2.srednia;

Można taki zapis wykorzystać tylko wtedy, gdy wynik działania comparer’a może być liczbą zmiennoprzecinkową. Jest tak na przykład w języku JavaScript.

Jeśli jest inaczej, funkcja ta nie zadziała prawidłowo (np. zaokrąglając liczby 0.1 i 0.99 do 0, dając w rezultacie równość (php)), lub zwróci błąd.

Comparer zwracający true/false

W niektórych językach (np c++) funkcja porównująca musi zwracać wartość logiczną true (prawda) jeśli element 1 ma być przed przed elementem 2, lub false (fałsz) w innym przypadku.

Wówczas warunki funkcji porównującej można jeszcze bardziej uprościć i napisać mniej więcej tak:

return (uczen1.srednia - uczen2.srednia) < 0;

Wiesz już zatem najważniejsze rzeczy o sortowaniu które przydadzą Ci się podczas programowania. Oczywiście nie wyczerpałem tematu w 100%, więc jeśli masz pytania: pytaj w komentarzu.

Ps. Celowo nie poruszyłem tu tematu algorytmów sortowania. Osobiście uważam, że w codziennej pracy programisty nie jest ta wiedza niezbędna, choć oczywiście świadomość istnienia różnych metod sortowania nie przeszkadza 😉