Sortowanie to jedna z najbardziej podstawowych i przydatnych funkcji stosowanych do danych. Ma na celu uporządkowanie danych w określony sposób, który może być zwiększany lub zmniejszany zgodnie z wymaganiami. W C ++ STL znajduje się wbudowana funkcja o nazwie „sort ()”, która umożliwia nam łatwe wykonanie algorytmu sortowania. W tym artykule będziemy badać funkcję sortowania w C ++,
W tym artykule zostaną omówione następujące wskaźniki:
- Funkcja sort ()
- Przykład - aby posortować dane w porządku rosnącym
- Przykład - aby posortować dane w porządku malejącym
- Partial_sort
Przechodząc do tego artykułu o funkcji sortowania w C ++
Sortować ( )
Jest to wbudowana funkcja pliku nagłówkowego algorytmu, która służy do sortowania kontenerów, takich jak tablica, wektory w określonej kolejności. Wewnętrznie ta funkcja jest realizowana jako Szybkie sortowanie
Quicksort to algorytm dziel i rządź. Quicksort najpierw dzieli dużą listę elementów na dwie mniejsze podlisty: niższe elementy i wyższe elementy. Szybkie sortowanie, a następnie rekurencyjne sortowanie list podrzędnych.
Kroki są następujące:
1. Wybierz z listy element losowy (zwykle ostatni), nazywany przestawnym.
2. Zmień kolejność listy w taki sposób, aby wszystkie elementy o wartościach mniejszych niż pivot znajdowały się przed przestawieniem, podczas gdy wszystkie elementy o wartościach większych niż pivot pojawiały się po niej i równe wartości mogły występować w obie strony. Jest to proces nazywany operacją partycjonowania.
3. Rekurencyjnie posortuj podlistę mniejszych elementów i podlistę większych elementów, ponownie wybierz punkt zwrotny w podliście i podziel je.
Podstawowym przypadkiem rekurencji są listy o rozmiarze zero lub jeden, które nigdy nie muszą być sortowane, więc łącząc je, sortujemy naszą listę.
Szybkie sortowanie jest w praktyce szybsze niż inne algorytmy O (n log n), takie jak Sortowanie przez wstawianie lub Sortowanie bąbelkowe. Quicksort można zaimplementować za pomocą algorytmu partycjonowania w miejscu, co oznacza, że całe sortowanie można wykonać przy użyciu tylko O (log n) dodatkowej przestrzeni. Quicksort nie jest typem stabilnym.
Jego złożoność jest następująca:
Najlepszy przypadek - O (n log n)
Najgorszy przypadek - O (n ^ 2)
Przypadek średni - O (n log n)
Składnia:
sort (pierwszy, ostatni)
Tutaj,
pierwszy - jest indeksem (wskaźnikiem) pierwszego elementu w zakresie do sortowania.
last - jest indeksem (wskaźnikiem) ostatniego elementu w zakresie do sortowania.
Na przykład, chcemy posortować elementy tablicy „arr” od 1 do 10 pozycji, użyjemy sort (arr, arr + 10) i posortujemy 10 elementów w porządku rosnącym.
Wartość zwracana
Żaden
Złożoność
rekurencja C ++ Fibonacciego
Średnia złożoności sortowania to N * log2 (N), gdzie N = ostatni - pierwszy.
Zakres danych
Obiekty w zakresie [pierwszy, ostatni) są modyfikowane.
Wyjątki
Przeciążenia z parametrem szablonu o nazwie jako błędy raportu ExecutionPolicy w następujący sposób:
Jeśli algorytm nie może przydzielić pamięci, jako wyjątek zgłaszany jest std :: bad_alloc.
Jeśli wykonanie funkcji wywołanej jako część algorytmu generuje wyjątek std :: terminate.
Przechodząc do tego artykułu o funkcji sortowania w C ++
Przykład - aby posortować dane w porządku rosnącym:
#include using namespace std int main () {int array [] = {10, 35, 85, 93, 62, 77, 345, 43, 2, 10} int n = sizeof (tablica) / sizeof (tablica [0]) ) // „sizeof” podaje rozmiar całkowitej tablicy, tj. rozmiar każdego znaku * nie. znaków // więc nie ma. liczby znaków // dzielimy sizeof (tablicę) przez rozmiar dowolnego jednego znaku tablicy // tutaj jest to tablica [0] sort (tablica, tablica + n) cout<< 'nArray after sorting using ' 'default sort is : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 } Wynik :
Wyjaśnienie
W powyższym przykładzie widzimy, że funkcja sort () domyślnie sortuje tablicę w porządku rosnącym.
Przechodząc do tego artykułu o funkcji sortowania w C ++
Przykład - aby posortować dane w porządku malejącym:
Aby posortować dane tablicy w porządku malejącym, musimy wprowadzić trzeci parametr, który służy do określenia kolejności sortowania elementów. Do sortowania danych w porządku malejącym możemy użyć funkcji „Greater ()”.
#include using namespace std int main () {int array [] = {41, 53, 4, 459, 60, 7, 23, 4, 232, 10} int n = sizeof (tablica) / sizeof (tablica [0] ) sort (tablica, tablica + n, większa ()) cout<< 'Array after sorting : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 } Wynik:
domyślna wartość dla ciągu znaków w java
Exp l naród
Tutaj funkcja sort () wykonuje porównanie w sposób, który umieszcza większy element przed.
Przechodząc do tego artykułu o funkcji sortowania w C ++
Partial_sort
C ++ STL udostępnia nam funkcję częściowego sortowania, funkcja jest podobna do funkcji sort (), ale w przeciwieństwie do funkcji sort () nie jest używana do sortowania całego zakresu, a raczej służy do sortowania tylko jego części. Sortuje elementy w zakresie [pierwszy, ostatni] w taki sposób, że elementy przed elementem środkowym są sortowane w porządku rosnącym, a elementy po środku pozostają niezmienione.
Można go użyć do znalezienia największego elementu, jeśli użyjemy obiektu funkcji do sortowania według pierwszej pozycji
Przykład
#include #include #include using namespace std int main () {vector vec = {10, 45, 60, 78, 23, 21, 30} vector :: iterator iptr parts_sort (vec.begin (), vec.begin () + 1, vec.end (), większy ()) iptr = vec.begin () cout<< 'The largest element is = ' << *iptr return 0 } Wynik:
Wyjaśnienie:
Powyższy kod może być użyty do znalezienia największej liczby w serii, aby znaleźć najmniejszą liczbę w serii, wystarczy usunąć większe polecenie.
W ten sposób dotarliśmy do końca artykułu „Funkcja sortowania w C ++”. Jeśli chcesz dowiedzieć się więcej, zajrzyj do szkolenia Java firmy Edureka, zaufanej firmy zajmującej się nauką online. Edureka's Kurs ma na celu szkolenie zarówno podstawowych, jak i zaawansowanych koncepcji Java, a także różnych frameworków Java, takich jak Hibernate i Spring.
Masz do nas pytanie? Wspomnij o tym w sekcji komentarzy na tym blogu, a my skontaktujemy się z Tobą tak szybko, jak to możliwe.