Sortowanie

Sortowanie to ogólnie pojęcie oznaczające przestawianie elementów kontenera w logicznej kolejności.

Sortowanie jest jedną z najbardziej podstawowych i fundamentalnych technik stosowanych do przetwarzania danych za pomocą funkcji. Oznacza to, że sortowanie pozwala nam ułożyć sekwencję elementów w określony, wybrany przez nas sposób, zgodnie z logiczną kolejnością.

Algorytmy sortowania pomagają manipulować danymi, a także rozwiązywać wiele problemów matematycznych i programistycznych.

*Aby używać tych metod, musimy dołączyć plik nagłówkowy algorithm na początku pliku C++ za pomocą #include <algorithm>.

Poznasz wbudowane funkcje z biblioteki algorytmów STL, które służą do sortowania danych. 
Omówimy trzy funkcje:

• sort()
• is_sorted()
• partial_sort()

Metoda sort

Metoda sort() z STL sortuje zawartość podanego zakresu. Metoda wymaga iteratora początkowego i końcowego, a następnie sortuje elementy z tego zakresu w kolejności rosnącej.

Możemy użyć jej w dwóch wersjach:

• sort(starting_iterator, ending_iterator) — sortuje zakres określony przez iteratory w kolejności rosnącej
• sort(starting_iterator, ending_iterator, comparing_function) — sortuje zakres określony przez iteratory, ale według funkcji podanej jako trzeci parametr

vector<int> numbers = {3, 5, 1, 2, 4};

sort(numbers.begin(), numbers.end());

for(auto i = numbers.begin(); i != numbers.end(); i++)
	cout << *i << " ";

Output:
1 2 3 4 5

Jak widać w powyższym kodzie, metoda sort() posortowała wektor w kolejności rosnącej.

bool compare(int a, int b)
{
	return a > b; // zwróć 1, jeśli a jest większe od b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4};
	
	sort(numbers.begin(), numbers.end(), compare);
	
	for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
5 4 3 2 1

Widać więc, jak użyliśmy drugiej wersji metody sort. Tworzymy funkcję compare() tak, aby zwracała true, jeśli a jest większe od b. Dzięki temu możemy sortować wektor w kolejności malejącej.

Metoda is_sorted

Metoda is_sorted() to funkcja STL, która zwraca true lub false, zależnie od tego, czy podany zakres jest posortowany. 

Metoda is_sorted() ma również dwie wersje, dokładnie tak jak metoda sort():

• is_sorted(starting_iterator, ending_iterator) — sprawdza, czy zakres określony przez dwa iteratory jest posortowany w kolejności rosnącej; zwraca true, jeśli tak, a w przeciwnym razie zwraca false
• is_sorted(starting_iterator, ending_iterator, comparing_function) — sprawdza, czy zakres określony przez dwa iteratory jest posortowany według funkcji porównującej.

vector<int> numbers = {3, 5, 1, 2, 4};

cout << is_sorted(numbers.begin(), numbers.end()) << endl;

sort(numbers.begin(), numbers.end());

cout << is_sorted(numbers.begin(), numbers.end());

Output:
0
1

bool compare(int a, int b)
{
	return a > b; // zwróć 1, jeśli a jest większe od b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4};
	
	cout << is_sorted(numbers.begin(), numbers.end(), compare) << endl;
	
	sort(numbers.begin(), numbers.end(), compare);
	
	cout << is_sorted(numbers.begin(), numbers.end(), compare);

Output:
0
1

Metoda partial_sort

Metoda parital_sort() sortuje pierwszą połowę elementów w podanym zakresie, a pozostałe elementy pozostawia w pierwotnym stanie. 
Ma również dwie wersje:

• partial_sort(start, middle, end) — sortuje zakres od start do end w taki sposób, że elementy od iteratora początkowego do iteratora środkowego są posortowane w kolejności rosnącej, a elementy od iteratora środkowego do iteratora końcowego pozostają w pierwotnym stanie
• partial_sort(start, middle, end, compare) — sortuje zakres od start do end tak, że elementy od start do middle są sortowane według funkcji porównującej, a elementy od middle do end pozostają w pierwotnym stanie

vector<int> numbers = {3, 5, 1, 2, 4, 10, 7};

partial_sort(numbers.begin(), numbers.begin() + 4, numbers.end());

for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
1 2 3 4 5 10 7

bool compare(int a, int b)
{
	return a > b; // zwróć 1, jeśli a jest większe od b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4, 10, 7};
	
	partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end(), compare);
	
	for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
10 7 5 1 2 3 4

Jak widać, metoda partial_sort() działa nieco inaczej, ale nie przejmuj się tym — rzadko będziesz używać sortowania częściowego. 

Na razie zapamiętaj, czym jest sortowanie, dobrze zapamiętaj metody sort() i is_sorted() oraz poćwicz ich używanie.