Gotowe metody sortujące Java

Witajcie w kolejnej części „Piątku z sortowaniem” – serii w której odkrywamy tajemnice algorytmów sortowania. Jest to kolejna część, w której skupimy się na gotowych metodach sortujących. Tym razem, przedstawię wam te, które znajdziecie w bibliotekach Javy.

Szybko i jeszcze szybciej

Jeśli jeszcze nie czytaliście wpisu dotyczącego gotowych metod sortowania w C++, powiem wam czemu warto korzystać z takich rozwiązań. Ponownie odniosę się do znanego powiedzenia – nie warto wymyślać koła na nowo. W większości przypadków, gotowe rozwiązania, w zupełności pokryją zapotrzebowanie na sortowanie tablic oraz innych kolekcji.

Dzięki temu zaoszczędzicie wiele czasu, co jest szczególnie ważne, chociażby dla osób piszących maturę. Jeśli bowiem w poleceniu nie jest wyraźnie zaznaczone, iż powinniście zaimplementować algorytm samodzielnie, możecie spokojnie wykorzystać stworzone ku temu metody. Bez zbędnego przedłużania przejdźmy do przedstawienia poszczególnych metod.

Arrays.sort()

Najczęściej sortowanie przyda się, podczas pracy z tablicami. Nie bez powodu znajdziemy do tego odpowiednią metodę. Co ważne, ma ona wiele swoich przeciążonych wersji, dzięki czemu przesortujemy dzięki niej, praktycznie każdą tablicę. W zależności od typu elementów tablicy, wykorzystywany jest jeden z dwóch algorytmów.

Pierwszy, to sortowanie szybkie, z dwoma punktami osiowymi (Dual-Pivot Quicksort). Algorytm ten opracowany przez Vladimira Yaroslavskiy, Jona Bentley i Joshua Blocha, to zmodyfikowana wersja algorytmu sortowania szybkiego. Różni się on od swojego pierwowzory tym, że przyjmujemy dwa punkty osiowe zamiast jednego. Dzięki temu dzielimy tablicę na trzy części, które zostaną posortowane dokładniej, niż w przypadku pojedynczego punktu osiowego. Algorytm ten oferuje złożoność obliczeniową na poziomie O(nlog(n)), nawet w przypadku zbiorów w których klasyczne sortowanie szybkie osiąga pesymistyczną złożoność czasową O(n2). Drugi z wykorzystywanych algorytmów, to rekurencyjne sortowanie przez scalanie (iterative mergesort). Napiszę o nim więcej w dalszej części tekstu.

Jak jednak korzystać z tej metody? Jest to bardzo proste i możecie zobaczyć to w kodzie poniżej:K

W przypadku podania jako dwóch kolejnych argumentów indeksów tablicy, tylko podana część tablicy zostanie posortowana:K

Array.sort(Object[])

Nic nie stoi nam na przeszkodzie, by używać tej metody do sortowania tablic obiektów. Obiekty znajdujące się w tablicy, muszą jedynie implementować interfejs Comparable<>. Interfejs ten posiada metodę compareTo(T o), która służy do określenia sposobu porównywania: zwraca ona int o wartości zero jeśli obiekty są równe; mniejszy niż zero, gdy porównywany obiekt jest mniejszy; większy niż zero, gdy jest większy. Nadpisanie tej metody, pozwoli nam na sortowanie obiektów w dowolny sposób. Zastosowanie możecie zobaczyć w kodzie poniżej:K

Jak widzicie, w nadpisanej metodzie compareTo() porównujemy obiekty TestClass między sobą, poprzez porównanie wartości ASCII ich atrybutów ch, będących typem Character. W przypadku gdy znak danego obiektu ma wartość mniejszą od 90, a porównywany większą, zwracana jest wartość -1. Efekt porównywania możemy zauważyć w komentarzu na końcu kodu.



Więcej przydatnych zagadnień z Javy znajdziesz w tej książce

Collections.sort()

Java posiada gotowe metody sortowania nie tylko dla tablic, lecz również dla wszelkiego rodzaju struktur dynamicznych, takich jak chociażby listy. Do sortowania wykorzystywany jest algorytm rekurencyjnego sortowania przez scalanie. Czym dokładnie charakteryzuje się ten algorytm?

Jest on stabilny oraz adaptacyjny. Pierwszy z przymiotników znamy bardzo dobrze, jednakże drugi pojawia się w tej serii wpisów po raz pierwszy. W kontekście algorytmów sortowania adaptacyjność oznacza, że algorytm wykorzystuje fakt, iż w nieposortowanym zbiorze, niektóre z elementów znajdują się od początku na właściwych miejscach. Algorytmy adaptacyjne wykorzystują ten fakt, dzięki czemu ich działanie jest szybsze. Ten algorytm sortowania oferuje złożoność na poziomie O(nlg(n)), w przypadku gdy tablica jest częściowo posortowana. W innych przypadkach oferuje klasyczne O(nlog(n)).

Wykorzystanie tej metody jest bardzo proste:K

Jeśli chcecie posortować kolekcję w sposób malejący, lub sprawić, aby była sortowana w sposób niestandardowy, możecie skorzystać z wyrażenia lambda pełniącego rolę komparatora. Jeśli nie wiecie czym są wyrażenia lambda, odpowiedź na to pytanie znajdziecie w tym wpisie. Wyrażenie to podajemy jako argument, zwracana przez niego wartość mówi nam o wyniku porównania. Jest to jeden ze sposobów na otrzymanie kolekcji posortowanej w sposób malejący.

Arrays.parallelSort()

Kolejną ciekawą funkcją która przyda się w szczególności przy dużych zestawach danych, jest sortownie równoległe. Jest to algorytm wykorzystujący współbieżność – dzieli tablice na podtablice, które sortowane są na wielu różnych wątkach. Jak można się domyślić, sortowanie to, będzie znacząco szybsze od klasycznego sortowania, co zauważymy zwłaszcza przy dużych zbiorach danych. Wykorzystanie tej metody, wygląda identycznie, jak korzystanie z klasycznego sort():

Jeszcze więcej!

Powyższe metody, powinny wystarczyć w większości przypadków, gdy potrzebujemy posortować zbiór danych w języku Java. To by było, na tyle w tym wpisie. Jeśli wciąż jesteście głodni algorytmicznej wiedzy, zapraszam was za tydzień, na kolejną część „Piątku z sortowaniem”. Do zobaczenia!

You Might Also Like
Dodaj komentarz

icon