W kolejnym materiale dotyczącym algorytmiki dowiesz się o bardzo prostym algorytmie sortującym 😊. Nosi nazwę "sortowanie przez wybieranie" 🔔. Prosty do zrozumienia, a nawet do zaprogramowania, także włazić i żadne "ale" 😁!
SORTOWANIE PRZEZ WYBIERANIE OPANUJESZ W MIG!
Zagadnienie, na które będziesz wpadać mnóstwo razy, brzmi: jak posortować zbiór danych rosnąco lub malejąco 😄?
Problem: uporządkowanie zbioru elementów w kolejności rosnącej/malejącej według ustalonego kryterium
Jest tajemnicą poliszynela, że w XX wieku opracowano wiele różnych sposobów na sortowanie zbiorów danych. Jedną "z odpowiedzi" jest sortowanie przez wybieranie (ang. selection sort) 💡!
Działanie polega na zbadaniu wartości każdego z elementów na podstawie ustalonego przez nas kryterium i wybraniu spośród nich tego, który ma najmniejszą bądź największą wartość (zależy czy sortujemy rosnąco, czy malejąco) ℹ️. Gdy taki element zostanie wyznaczony, algorytm wykonuje 2 następujące czynności jednocześnie 👇:
- usuwa element z listy z danymi wejściowymi,
- dodaje element do drugiej (osobnej) listy przeznaczonej dla posortowanych elementów.
Powtarza to samo po nitce do kłębka, aż lista wprowadzona do algorytmu stanie się pusta, a na wyjściu otrzymujemy nowy zbiór danych z tymi samymi elementami, tylko według "ustawionej" kolejności. Więcej nie trzeba tłumaczyć 😉!
 |
Sortowanie przez wybieranie polega na każdorazowym wyznaczaniu elementu o najmniejszej/największej wartości i "przenoszeniu" z jednego zbioru danych do drugiego, aż do wyczerpania danych wejściowych.
ILE TO MOŻE TRWAĆ?
Teraz rzućmy okiem na złożoność czasową ⌚.
Operujemy na N-elementowym zbiorze. Dla każdego elementu, występuje jego przeniesienie z jednej listy do drugiej ⏩. Pisząc jeszcze dokładniej, to usunięcie z jednego zbioru danych i dodanie do drugiego. W ten sposób układane są elementy 🧩. Zanim jednak dojdzie do przeniesienia elementu do drugiego miejsca, musimy wskazać jaki to ma być. Ponadto, trzeba każdorazowo "ustalać rekordzistę" 🎯.
Wynika z tego, iż złożoność czasowa sortowania przez wybieranie, zgodnie z notacją dużego O, wynosi 👇:
O(n2)
Wzrost kwadratowy. Ponieważ N razy sprawdzamy, który element jest największy (lub najmniejszy) według naszego kryterium i N razy wykonujemy przeniesienie do drugiego zbioru 💡.
Za każdym razem ta lista się kurczy, więc tak naprawdę mamy potem:
(n - 1)2, (n - 2)2, ..., 1
natomiast stałe w notacji dużego O nie są brane pod uwagę ⚠️.
Aby otrzymać posortowany zbiór danych, musimy dojść do samego końca (nie ma tak, że można wyznaczyć rozwiązanie gdzieś w połowie 😅), zatem każdorazowo zostanie spełniony przypadek najgorszy (liczba iteracji naszego algorytmu będzie równa górnej granicy) ℹ️.
KOD ŹRÓDŁOWY
Tyle z teoretycznej części, a teraz zostawiam Ci kod źródłowy napisany w języku Java, prezentujący sortowanie przez wybieranie 😁. Bardzo prosty i bardzo krótki, więc szybko się polubicie 😊!
KLASA "MAIN"
public class Main {
public static void main(String[] args) {
new Launcher();
}
}Klasa "Main" jest miejscem uruchomienia programu, więc nie wymaga wyjaśniania 🙃!
KLASA "RESULTSPRINTER"
import java. io.PrintStream;
import java. util.ArrayList;
public class ResultsPrinter {
private final PrintStream printStream = System.out;
public void printIntegerList(ArrayList<Integer> numbers, String message) {
if(numbers != null) {
printStream.println(message + numbers);
}
}
}To jest klasa poboczna, który służy jedynie do wypisywania rezultatów działania algorytmu 👍. Nie należy do części samego algorytmu, więc możesz ją całkowicie usunąć, jeśli nie potrzebujesz komunikatów w konsoli 👌.
Jedyna metoda jaka tu występuje, to skorzystanie z metody "println" do napisania podanej w parametrze treści oraz aktualnego stanu wskazanej listy ("ArrayList") ✅.
KLASA "LAUNCHER"
import java. util.Arrays;
import java. util.ArrayList;
import java. util.Comparator;
public class Launcher {
private final ArrayList<Integer> unsortedNumbers = new ArrayList<>(Arrays.asList(5, 78, -90, 835, -6));
private final ArrayList<Integer> sortedNumbers = new ArrayList<>();
private final ResultsPrinter resultsPrinter = new ResultsPrinter();
public Launcher() {
printNumbersLists();
sortNumbers();
printNumbersLists();
}
private void printNumbersLists() {
resultsPrinter.printIntegerList(unsortedNumbers, "Nieposortowane liczby: ");
resultsPrinter.printIntegerList(sortedNumbers, "Posortowane liczby: ");
}
private void sortNumbers() {
while (!unsortedNumbers.isEmpty()) {
findSmallestNumber();
}
}
private void findSmallestNumber() {
var optionalSmallestNumber = unsortedNumbers.stream().min(Comparator.comparingInt(number -> number));
optionalSmallestNumber.ifPresent(this::onSmallestNumberWasFound);
}
private void onSmallestNumberWasFound(Integer integer) {
sortedNumbers.add(integer);
unsortedNumbers.remove(integer);
}
}Tak oto jesteśmy przy klasie z algorytmem 🔥!
Tak jak pisałem, mamy dwie listy 👇:
- dane wejściowe (do dodawania liczb w miejsce definicji, możesz użyć "Arrays.asList" ℹ️),
- osobna jako pusta.
Czyli jedna jest serią "porozrzucanych" wartości, a druga jest pusta i do niej będą wkładane elementy raz po raz 📦. Tworzymy je u samej góry, razem z instancją klasy do wypisywania komunikatów (część niezwiązana z algorytmem).
W konstruktorze znajdują się tylko wywołania 3 metod 3️⃣:
- wypisujemy stan początkowy list,
- uruchamiamy algorytm,
- wypisujemy stan końcowy list.
Metoda odpowiedzialna za sortowanie przez wybieranie, korzysta z pętli "while", która wykonuje się tak długo, jak długo są jeszcze jakieś elementy w danych nieposortowanych ℹ️.
Przedostatnia metoda w kolejności, reprezentuje pojedynczą iterację pętli ⚠️. Tutaj korzystam z elementu paradygmatu funkcyjnego, jakim jest ten oto ciąg:
var optionalSmallestNumber = unsortedNumbers.stream().min(Comparator.comparingInt(number -> number));W języku Java, "stream" oznacza konwersję kolekcji na strumień, który otwiera drogę do metod operujących na zbiorze danych 🤩. "min" porównuje każdy element ze sobą i zwraca ten, którego wartość jest najmniejsza (jeżeli interesuje Cię sortowanie od największego do najmniejszego, wystarczy zamienić metodę na "max" 😉) 🚀. To:
Comparator.comparingInt(number -> number)oznacza skorzystanie z wbudowanego "stream" do porównywania ze sobą dwóch liczb całkowitych. Jeżeli chcesz dowiedzieć się więcej o wymienionych terminach, przejdź do załączonych artykułów 🚨.
Na wyjściu zwracany jest element, natomiast operując na kolekcjach, musimy założyć, że coś się posypie np. nie dało się wyznaczyć takiego elementu, bo wszystkie są "null" (piszę hipotetycznie) 😧. Dlatego typ danych jaki zostanie przyjęty, to "Optional" 🔴! "Optional" stanowi "osłonę" przed wartościami "null" (więcej o typie "Optional" możesz przeczytać w załączonym artykule ℹ️).
Skoro typ "Optional" ma chronić przed próbą operowania na referencji której nie ma, trzeba otoczyć instrukcje metodą "ifPresent":
optionalSmallestNumber.ifPresent(this::onSmallestNumberWasFound);która za parametr przyjmuje wyrażenie lambda typu "Consumer" - metodę z jednym parametrem niezwracającą żadnej wartości 😮! Jeżeli jest zdefiniowana jakaś referencja, to podana metoda zostanie wywołana ✔️. W tym wypadku stosuję referencję do metody, ponieważ "zestaw" parametrów oczekiwany w miejscu wyrażenia lambda, pokrywa się z definicją metody 🌟.
Metoda jaka ma się wykonać, to te 2 rzeczy wykonane "atomowo", czyli:
- dodanie liczby do listy dla posortowanych danych,
- usunięcie liczby z listy danych wejściowych.
Po wykonaniu tej operacji, program powraca do pętli "while", aż dojdzie do całkowitego opróżnienia pierwszej listy 0️⃣. Tak oto powstaje lista liczb całkowitych posortowanych w kolejności rosnącej 📈. Gdy teraz zostaną wypisane zawartości obu list, to zobaczysz efekt symetryczny do poprzedniego: poprzednio lista posortowana "stała" pusta, a po posortowaniu lista z danymi wejściowymi taka będzie 😄.
Algorytm wyjaśniony ✅! Sortowanie przez wybieranie jest prostym do zrozumienia podejściem w kierunku posortowania kolekcji z danymi 🧠. Podajesz kryterium, wprowadzasz dane i masz 💛!