Dzyń! Otwieram nowy materiał dotyczący algorytmiki. Dzisiaj dowiecie się o algorytmie sortującym (bardzo prostym zresztą) jaki się zwie "sortowanie przez wybieranie". Prosty do zrozumienia, a nawet do zaprogramowania, także włazić, żadne "ale" i cichosza ;)!
| Tweet |
SORTOWANIE PRZEZ WYBIERANIE TYLKO JEDNĄ Z METOD SORTOWANIA
Jest tajemnicą poliszynela, że w dwudziestym wieku opracowano wiele różnych sposobów na ten sam problem: jak kurczę posortować zbiór danych rosnąco lub malejąco?
Problem: uporządkowanie zbioru elementów w kolejności rosnącej / malejącej wg ustalonego kryterium
Odpowiedź na to pytanie przynosi między innymi rodzaj sortowania przez wybieranie (ang. "selection sort"). To wybieranie polega na "przetrząśnięciu" całego zbioru danych i badaniu wartości każdego z elementów (kryterium ustalamy sami). W zależności od tego, czy interesuje nas sortowanie w kolejności rosnącej lub malejącej, program wybiera element o największej / najmniejszej wartości i wykonuje dwa w jednym: usuwa go ze starej nieuporządkowanej listy i dodaje do nowej, w której znajdą się elementy już posortowane. I tak po nitce do kłębka, aż zwróci na wyjściu nowy zbiór danych z tymi samymi elementami, tylko według "ustawionej" kolejności. Myślę, że metoda prosta do zrozumienia.
ZŁOŻONOŚĆ OBLICZENIOWA?
Jak napisałem na samym początku, najważniejsza operacja polega na przeniesieniu elementu z jednej listy do drugiej, natomiast pisząc dokładniej to usuwa ze starego zbioru danych i dodaje do odrębnego, układając w ten sposób elementy. Ponieważ każdorazowo trzeba ustalać "rekordzistę" zanim przeniesie się go do osobnej kolekcji z danymi, mamy więc O(n2), gdyż n razy sprawdzamy elementy który z nich ma największe (lub najmniejsze) kryterium i tyle samo 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 itd., jednakże stałe w notacji dużego O nie są brane pod uwagę. Sortowanie wymaga dojścia do samego końca (nie ma tak, że można znaleźć rozwiązanie gdzieś w połowie), zatem każdorazowo będzie spełniać przypadek najgorszy.
KOD ŹRÓDŁOWY
Teraz zostawiam Was z kodem źródłowym napisanym w języku Java prezentującym sortowanie przez wybieranie. Już nie jest tak długi jak ten rozwiązujący problem wędrującego komiwojażera aproksymacyjnie ;):
KLASA "MAIN"
public class Main {
public static void main(String[] args) {
new SelectionSort();
}
}KLASA "NUMBERSLIST"
import java. util.List;
import java. util.ArrayList;
public class NumbersList extends ArrayList<Integer> {
public NumbersList() {
super();
}
public NumbersList(List<Integer> numbers) {
super(numbers);
}
public int smallestNumber() {
int smallest = get(0);
for (int i = 1; i < size(); ++i) {
int current = get(i);
if(current < smallest) {
smallest = current;
}
}
return smallest;
}
}KLASA "SELECTIONSORT"
import java. io.PrintStream;
import java. util.Arrays;
import java. util.ArrayList;
public class SelectionSort {
private final NumbersList unsortedNumbers = new NumbersList(Arrays.asList(5, 78, -90, 835, -6));
private final NumbersList sortedNumbers = new NumbersList();
public SelectionSort() {
printArrays();
sortNumbers(unsortedNumbers, sortedNumbers);
printArrays();
}
private void printArrays() {
PrintStream ps = System.out;
ps.println("Given numbers: " + unsortedNumbers);
ps.println("Sorted numbers: " + sortedNumbers);
}
private void sortNumbers(NumbersList unsorted, ArrayList<Integer> sorted) {
while (unsorted.size() > 0) {
int smallest = unsorted.smallestNumber();
sorted.add(smallest);
unsorted.remove((Object)smallest);
}
}
}Po zdefiniowaniu punktu uruchomieniowego aplikacji, tworzymy sobie klasę dla listy numerków i wewnątrz niej dodajemy metodę wybierającą najmniejszy element celem sortowania w górę (gdy chcecie żeby sortowanie przez wybieranie odbywało się malejąco, zmieńcie treść na szukanie największego elementu). Zawarłem pobieranie pierwszego elementu na dzień dobry, żeby uniknąć przypadku zwracania "null" kiedy lista jest pusta (choć i tak wyskoczy wyjątek kiedy wywoła się metodę na liście pozbawionej jakichkolwiek argumentów). "super" umożliwia mi sięgnięcie do konstruktora klasy nadrzędnej jaką jest "ArrayList", bo bez tego byłyby nici z wygodnego wprowadzenia wielu wartości w jednej linijce kodu ("Arrays.asList").
Najciekawsze jest w klasie "SelectionSort". Podstawowa rzecz to zdefiniowanie sobie dwóch instancji list dla przechowywania liczb całkowitych. Jedna ma dysponować serią "porozrzucanych" wartości, a druga ma stać pusta i do niej będą wkładane elementy raz po raz. W konstruktorze, poza sortowaniem, wprowadziłem wywołania metod wypisujących na terminalu aktualny stan obu list, aby udowodnić że jest tak jak piszę przez cały artykuł. Główny punkt programu znajduje się w metodzie "sortNumbers". Po wprowadzeniu dwóch parametrów dla obu list, program wchodzi do pętli "while" i wykonuje sortowanie przez wybieranie, do czasu opróżnienia listy z numerkami nieposortowanymi. Iteracja każdorazowo znajduje element o najmniejszej wartości (wywołanie metody z klasy "NumbersList") i "atomowo" wykonuje dwie operacje pod rząd: dodaje numerek do listy posortowanej i jednocześnie wywala go z listy nieposortowanej.
Po całkowitym opróżnieniu listy nieposortowanej, pętla kończy swoje działanie i tak oto powstaje lista liczb całkowitych posortowanych w kolejności rosnącej. Gdy teraz zostaną wypisane zawartości obu list, to zobaczycie częściową symetrię: poprzednio lista posortowana "stała" pusta, a teraz pusta okaże się lista z danymi wejściowymi (tymi "porozrzucanymi").
Nareszcie meta! Sortowanie przez wybieranie jest prostym do zrozumienia podejściem w kierunku posortowania kolekcji z danymi. Podajesz kryterium, wprowadzasz dane...i masz!