Gotowe metody sortujące w C++

Nadszedł piąty dzień tygodnia, a wraz z nim dawka wiedzy dotyczącej sortowania. Ten wpis „Piątku z sortowaniem”, będzie jednak nieco odmienny od pozostałych. Nie będziemy bowiem omawiać kolejnego z algorytmów sortowania. Tym razem przyjrzymy się gotowym metodom sortującym, które znajdziemy w bibliotekach C++.

Czemu?

Na wstępie powiedzmy sobie krótko, czemu warto korzystać z gotowych metod sortujących. Odpowiedź na to pytanie, możemy znaleźć w popularnym powiedzeniu – „Nie warto wymyślać koła na nowo”. Po co więc marnować czas pisząc funkcje, które mamy pod nosem? Tyczy się to zwłaszcza osób które planują pisać maturę. Jak sami wiecie, czas na rozwiązanie zadań jest ograniczony. Jeśli w poleceniu nie jest wyraźnie zaznaczone, że należy samemu zaimplementować algorytm sortujący, bądź nie wolno korzystać z gotowych metod sortujących, możecie spokojnie skorzystać z poniższych funkcji! Oszczędzicie na tym wiele cennych minut.

Oczywiście nie każdy problem, będzie możliwy do rozwiązania, z wykorzystaniem gotowych funkcji. Czasem będziemy musieli rozpatrzeć szczególne przypadki, które zmienią zasadę działania algorytmów. Jednakże w większości przypadków, gotowe rozwiązania, są w zupełności wystarczające. Bez dłuższego przeciągania, przejdźmy do omówienia poszczególnych metod.

std::sort() – C++

Pierwszą z funkcji sortowania, którą przyjdzie nam omówić, jest sort(). Znajdziemy go w bibliotece <algorithm>. Funkcja ta, korzysta z algorytmu sortowania introspektywnego (introsort). Jest to algorytm hybrydowy, który łączy w sobie algorytmy sortowania szybkiego i sortowania przez kopcowanie. Algorytm ten eliminuje problem złożoności O(n2) występującej w najgorszym przypadku algorytmu sortowania szybkiego.

Wykorzystanie tej funkcji jest bardzo proste. Jako pierwszy argument funkcja przyjmuje iterator wskazujący na początek zakresu sortowania. Drugi z argumentów wskazuje natomiast na jego koniec. W wykorzystywanych przykładach będziemy używać zarówno zwykłych tablic jak i vector’ów. Zauważ, że w poniższym wywołaniu funkcji sort() początkiem naszego zbioru jest sama nazwa tablicy jako adres jej pierwszego elementu. Natomiast końcem zbioru jest ten sam adres powiększony o ilość elementów w tym zbiorze.

Jeśli potrzebujemy posortować tablicę rosnąco, możemy dodać trzeci argument do naszej funkcji. Argument ten to funkcja porównująca dwa elementy. Musi zwracać false, jeżeli pierwszy argument powinien znajdować się za drugim, natomiast true w przeciwnym wypadku. W tym miejscu możemy chociażby skorzystać z funkcji greater<>(), która sprawi, że nasza tablica zostanie posortowana w sposób malejący. Nic nie stoi nam jednak na przeszkodzie, by napisać własną funkcję w tym celu.

Jeśli potrzebujemy przesortować chociażby vector<>, sort() również świetnie się sprawdzi. Analogicznie podajemy wskaźniki na początek i koniec naszego zbioru.K

Pytanie co w sytuacji, gdy nasz zbiór złożony jest z elementów o typie innym niż typy wbudowane? W sytuacji gdy nasz zbiór przechowuje elementy będące instancjami typów zdefiniowanych przez nas takich jak unie, struktury czy klasy z pomocą przychodzą nam wyrażenia lambda. Jeśli nie wiesz czym są, odpowiedź znajdziesz, w tym wpisie.

W poniższym przykładzie skonstruujemy strukturę Point zawierającą dwa składniki x oraz y. Powiedzmy, że vector takich punktów chcielibyśmy posortować względem współrzędnej x. W tym celu w miejscu trzeciego parametru funkcji sort() definiujemy wyrażenie lambda porównujące wartość składnika x dwóch sąsiednich elementów zbioru.

Należy jednak pamiętać, że algorytm ten nie jest stabilny. Nie musimy się jednak załamywać, jeśli potrzebujemy algorytmu stabilnego, znajdziemy go również wśród gotowych rozwiązań.

std::stable_sort – C++

Jest to kolejna z funkcji sortowania, którą znajdziemy w bibliotece <algorithm>. Funkcja ta korzysta z algorytmu sortowania przez scalanie. Jak łatwo się domyślić, algorytm ten, jest algorytmem stabilnym. Jeśli nie wiecie, czym jest algorytm stabilny, możecie przeczytać wpis dotyczący sortowania przez wstawianie. W nim tłumaczę również, czym charakteryzuje się algorytm stabilny.

Funkcja ta, przyjmuje takie same argumenty, jak funkcja sort(). Na początku podajemy więc wskaźnik na początek zbioru, później wskaźnik, a na koniec oraz ewentualną funkcję porównującą.K

std::partial_sort – C++

Funkcja ta, jest raczej ciekawostką, niż czymś czego będziemy używać na co dzień. Przyjmujące trzy parametry, first, middle i last, partial_sort(), sortuje elementy w taki sposób, że elementy przed środkowym indeksem, są elementami najmniejszymi z tablicy. Wszystkie pozostałe elementy, są pozostawione w losowym ułożeniu.K

concurrency::parallel_sort() – c++

Kolejnym ciekawym algorytmem jest paralel_sort(), który znajdziemy w bibliotece <ppl.h>. Jest to algorytm który współbieżnie wykonuje prace nad kolekcjami danych. Ten algorytm jest przydatny, gdy istnieje zestaw danych, który może korzystać z równoczesnego sortowania. W szczególności sortowanie równoległe jest przydatne przy dużych zestawach danych. Traci on jednak na szybkości, gdy sortujemy małe zbiory danych.

Podobnie jak wcześniejsze funkcje, przyjmuje ona za argumenty wskaźnik na początek oraz koniec sortowanego zbioru. Korzystamy z niej w następujący sposób:K

Posortuj je wszystkie

Powyższe przykłady nie są wszystkimi gotowymi metodami sortowania, do których mamy dostęp. Istnieje jeszcze wiele innych metod sortujących, które znajdziemy nie tylko w bibliotece <algorithm>. To na tyle w tej części „Piątku z sortowaniem”. Do zobaczenia za tydzień!

You Might Also Like
Dodaj komentarz