Przypadek sortowania
Sortowanie tablicy to proces układania wszystkich elementów tablicy w określonej kolejności. Istnieje wiele różnych przypadków, w których sortowanie tablicy może być przydatne. Na przykład Twój program pocztowy zazwyczaj wyświetla e-maile w kolejności ich otrzymania, ponieważ nowsze e-maile są zazwyczaj uważane za bardziej trafne. Gdy przejdziesz do listy kontaktów, nazwy są zazwyczaj ułożone w kolejności alfabetycznej, ponieważ w ten sposób łatwiej jest znaleźć szukaną nazwę. Obie te prezentacje obejmują sortowanie danych przed prezentacją.
Sortowanie tablicy może sprawić, że przeszukiwanie tablicy będzie wydajniejsze nie tylko dla ludzi, ale także dla komputerów. Rozważmy na przykład przypadek, w którym chcemy wiedzieć, czy imię pojawia się na liście nazwisk. Aby sprawdzić, czy nazwa znajdowała się na liście, musielibyśmy sprawdzić każdy element tablicy, aby zobaczyć, czy nazwa się pojawia. W przypadku tablicy zawierającej wiele elementów przeszukanie ich wszystkich może być kosztowne.
Załóżmy jednak, że nasza tablica nazw jest posortowana alfabetycznie. W tym przypadku musimy szukać jedynie do momentu, w którym natrafimy na nazwę alfabetycznie większą od tej, której szukamy. W tym momencie, jeśli nie znaleźliśmy nazwy, wiemy, że nie istnieje ona w pozostałej części tablicy, ponieważ wszystkie nazwy, których nie sprawdziliśmy w tablicy, z pewnością są większe alfabetycznie!
Okazuje się, że istnieją jeszcze lepsze algorytmy do wyszukiwania posortowanych tablic. Za pomocą prostego algorytmu możemy przeszukać posortowaną tablicę zawierającą 1 000 000 elementów, korzystając tylko z 20 porównań! Wadą jest oczywiście to, że sortowanie tablicy jest stosunkowo drogie i często nie warto sortować tablicy, aby przyspieszyć wyszukiwanie, chyba że będziesz ją przeszukiwać wiele razy.
W niektórych przypadkach sortowanie tablicy może sprawić, że wyszukiwanie stanie się niepotrzebne. Rozważmy inny przykład, w którym chcemy znaleźć najlepszy wynik testu. Jeśli tablica jest nieposortowana, musimy przejrzeć każdy element tablicy, aby znaleźć najwyższy wynik testu. Jeśli lista jest posortowana, najlepszy wynik testu będzie na pierwszej lub ostatniej pozycji (w zależności od tego, czy posortowaliśmy rosnąco, czy malejąco), więc nie musimy w ogóle szukać!
Jak działa sortowanie
Sortowanie odbywa się zazwyczaj poprzez wielokrotne porównywanie par elementów tablicy i zamienianie ich, jeśli spełniają określone wcześniej kryteria. Kolejność porównywania tych elementów różni się w zależności od zastosowanego algorytmu sortowania. Kryteria zależą od sposobu sortowania listy (np. w kolejności rosnącej lub malejącej).
Aby zamienić dwa elementy, możemy skorzystać z funkcji std::swap() ze standardowej biblioteki C++, która jest zdefiniowana w nagłówku narzędzia.
#include <iostream>
#include <utility>
int main()
{
int x{ 2 };
int y{ 4 };
std::cout << "Before swap: x = " << x << ", y = " << y << '\n';
std::swap(x, y); // swap the values of x and y
std::cout << "After swap: x = " << x << ", y = " << y << '\n';
return 0;
}Ten program wypisuje:
Before swap: x = 2, y = 4 After swap: x = 4, y = 2
Zauważ, że po zamianie wartości x i y zostały zamienione miejscami!
Wybór sort
Istnieje wiele sposobów sortowania tablicy. Sortowanie przez wybór jest prawdopodobnie najłatwiejszym do zrozumienia rodzajem, co czyni go dobrym kandydatem do nauczania, mimo że jest jednym z wolniejszych rodzajów.
Sortowanie przez wybór wykonuje następujące kroki, aby posortować tablicę od najmniejszej do największej:
- Zaczynając od indeksu tablicy 0, przeszukaj całą tablicę, aby znaleźć najmniejszą wartość
- Zamień najmniejszą wartość znalezioną w tablicy na wartość o indeksie 0
- Powtórz kroki 1 i 2 zaczynając od następnego indeksu
Innymi słowy, znajdziemy najmniejszy element w tablicy i zamienimy go na pierwszą pozycję. Następnie znajdziemy kolejny najmniejszy element i zamienimy go na drugą pozycję. Proces ten będzie powtarzany aż do wyczerpania się elementów.
Oto przykład działania tego algorytmu na 5 elementach. Zacznijmy od przykładowej tablicy:
{ 30, 50, 20, 10, 40 }
Najpierw znajdujemy najmniejszy element, zaczynając od indeksu 0:
{ 30, 50, 20, 10, 40 }
Następnie zamieniamy go z elementem o indeksie 0:
{ 10, 50, 20, 30, 40 }
Teraz, gdy pierwszy element jest posortowany, możemy go zignorować. Teraz znajdujemy najmniejszy element, zaczynając od indeksu 1:
{ 10, 50, 20, 30, 40 }
I zamień go z elementem w indeksie 1:
{ 10, 20, 50, 30, 40 }
Teraz możemy zignorować pierwsze dwa elementy. Znajdź najmniejszy element zaczynając od indeksu 2:
{ 10, 20, 50, 30, 40 }
I zamień go z elementem o indeksie 2:
{ 10, 20, 30, 50, 40 }
Znajdź najmniejszy element zaczynając od indeksu 3:
{ 10, 20, 30, 50, 40 }
I zamień go z elementem o indeksie 3:
{ 10, 20, 30, 40, 50 }
Na koniec znajdź najmniejszy element zaczynając od indeksu 4:
{ 10, 20, 30, 40, 50 }
I zamień go z elementem o indeksie 4 (co nie ma miejsca cokolwiek):
{ 10, 20, 30, 40, 50 }
Gotowe!
{ 10, 20, 30, 40, 50 }
Zauważ, że ostatnie porównanie będzie zawsze dokonywane ze sobą (co jest zbędne), więc możemy właściwie zatrzymać 1 element przed końcem tablicy.
Sortowanie przez wybór w C++
Oto jak ten algorytm jest implementowany w C++:
#include <iostream>
#include <iterator>
#include <utility>
int main()
{
int array[]{ 30, 50, 20, 10, 40 };
constexpr int length{ static_cast<int>(std::size(array)) };
// Step through each element of the array
// (except the last one, which will already be sorted by the time we get there)
for (int startIndex{ 0 }; startIndex < length - 1; ++startIndex)
{
// smallestIndex is the index of the smallest element we’ve encountered this iteration
// Start by assuming the smallest element is the first element of this iteration
int smallestIndex{ startIndex };
// Then look for a smaller element in the rest of the array
for (int currentIndex{ startIndex + 1 }; currentIndex < length; ++currentIndex)
{
// If we've found an element that is smaller than our previously found smallest
if (array[currentIndex] < array[smallestIndex])
// then keep track of it
smallestIndex = currentIndex;
}
// smallestIndex is now the index of the smallest element in the remaining array
// swap our start element with our smallest element (this sorts it into the correct place)
std::swap(array[startIndex], array[smallestIndex]);
}
// Now that the whole array is sorted, print our sorted array as proof it works
for (int index{ 0 }; index < length; ++index)
std::cout << array[index] << ' ';
std::cout << '\n';
return 0;
}Najbardziej mylącą częścią tego algorytmu jest pętla wewnątrz innej pętli (tzw. pętla zagnieżdżona). Zewnętrzna pętla (startIndex) iteruje po każdym elemencie jeden po drugim. Dla każdej iteracji pętli zewnętrznej do znalezienia najmniejszego elementu w pozostałej tablicy (zaczynając od startIndex+1) używana jest pętla wewnętrzna (currentIndex). najmniejszyIndex śledzi indeks najmniejszego elementu znalezionego przez pętlę wewnętrzną. Następnie najmniejszy indeks jest zamieniany na startIndex. Na koniec zewnętrzna pętla (startIndex) przesuwa jeden element do przodu i proces się powtarza.
Wskazówka: Jeśli nie wiesz, jak działa powyższy program, pomocne może być przejrzenie przykładowego przypadku na kartce papieru. Zapisz początkowe (nieposortowane) elementy tablicy poziomo na górze kartki. Narysuj strzałki wskazujące, które elementy startIndex, currentIndex i najmniejszyIndex są indeksowane. Ręcznie prześledź program i przerysuj strzałki w miarę zmiany indeksów. Dla każdej iteracji zewnętrznej pętli rozpoczynaj nową linię pokazującą bieżący stan tablicy.
Sortowanie nazw działa przy użyciu tego samego algorytmu. Po prostu zmień typ tablicy z int na std::string i zainicjalizuj odpowiednimi wartościami.
Ponieważ sortowanie tablic jest tak powszechne, standardowa biblioteka C++ zawiera funkcję sortowania o nazwie std::sort. std::sort żyjącą w nagłówku <algorithm> i można ją wywołać dla takiej tablicy:
#include <algorithm> // for std::sort
#include <iostream>
#include <iterator> // for std::size
int main()
{
int array[]{ 30, 50, 20, 10, 40 };
std::sort(std::begin(array), std::end(array));
for (int i{ 0 }; i < static_cast<int>(std::size(array)); ++i)
std::cout << array[i] << ' ';
std::cout << '\n';
return 0;
}Domyślnie std::sort sortuje w kolejności rosnącej za pomocą operatora< do porównywania par elementów i zamiany ich, jeśli to konieczne (podobnie jak w naszym przykładzie sortowania przez wybór powyżej).
Porozmawiamy więcej o std::sort w następnym rozdziale.
Czas quizu
Pytanie nr 1
Ręcznie pokaż, jak działa sortowanie przez wybór w następującej tablicy: { 30, 60, 20, 50, 40, 10 }. Pokaż tablicę po każdej przeprowadzonej zamianie.
Pytanie nr 2
Przepisz powyższy kod sortowania wyboru, aby posortować w kolejności malejącej (najpierw największe liczby). Chociaż może się to wydawać skomplikowane, w rzeczywistości jest zaskakująco proste.
Pytanie nr 3
To będzie trudne, więc bądź ostrożny.
Inne proste sortowanie nazywa się „sortowaniem bąbelkowym”. Sortowanie bąbelkowe polega na porównaniu sąsiadujących par elementów i zamianie ich, jeśli spełnione są kryteria, tak aby elementy „bąbelkowały” do końca tablicy. Chociaż istnieje kilka sposobów optymalizacji sortowania bąbelkowego, w tym quizie pozostaniemy przy niezoptymalizowanej wersji, ponieważ jest najprostsza.
Niezoptymalizowane sortowanie bąbelkowe wykonuje następujące kroki, aby posortować tablicę od najmniejszej do największej:
A) Porównaj element tablicy 0 z elementem tablicy 1. Jeśli element 0 jest większy, zamień go z elementem 1.
B) Teraz wykonaj to samo dla elementów 1 i 2 oraz każdej kolejnej pary elementów, aż dojdziesz do końca tablicy. W tym momencie zostanie posortowany ostatni element tablicy.
>C) Powtórz pierwsze dwa kroki jeszcze raz, aż tablica zostanie posortowana.
Napisz kod, który bąbelek sortuje następującą tablicę zgodnie z powyższymi regułami:
int array[]{ 6, 3, 2, 9, 7, 1, 5, 4, 8 };Wydrukuj posortowane elementy tablicy na końcu programu.
Wskazówka: jeśli uda nam się posortować jeden element w każdej iteracji, oznacza to, że będziemy musieli wykonaj iterację mniej więcej tyle razy, ile jest liczb w naszej tablicy, aby zagwarantować, że cała tablica zostanie posortowana.
Wskazówka: Porównując pary elementów, uważaj na zakres tablicy.
Pytanie nr 4
Dodaj dwie optymalizacje do algorytmu sortowania bąbelkowego, który napisałeś w poprzednim pytaniu quizu:
- Zauważ, że przy każdej iteracji sortowania bąbelkowego największa pozostała liczba jest umieszczana na końcu tablicy. Po pierwszej iteracji sortowany jest ostatni element tablicy. Po drugiej iteracji sortowany jest także przedostatni element tablicy. I tak dalej… Przy każdej iteracji nie musimy ponownie sprawdzać elementów, o których wiemy, że są już posortowane. Zmień pętlę tak, aby nie sprawdzała ponownie elementów, które zostały już posortowane.
- Jeśli przejdziemy przez całą iterację bez wykonywania zamiany, będziemy wiedzieć, że tablica musi być już posortowana. Zaimplementuj sprawdzenie, czy w tej iteracji dokonano jakichkolwiek zamian, a jeśli nie, zakończ pętlę wcześniej. Jeżeli pętla została zakończona wcześniej, wypisz, w której iteracji sortowanie zakończyło się wcześniej.
Twoje dane wyjściowe powinny pasować do tego:
Early termination on iteration 6 1 2 3 4 5 6 7 8 9