Przeczytaj
Implementacja algorytmu sortowania przez wybieranie w porządku niemalejącym w języku C++
Pracujesz w firmie, w której zajmujesz się rozkładaniem towarów na półki. W ostatniej dostawie przyszło sporo nowych długopisów w różnych cenach. Kierownik kazał ci je posortować i poukładać na półkach zgodnie z cenami – od najmniejszych do największych.
Napisz program sortujący w porządku niemalejącym n‑elementową tablicę zawierającą ceny długopisów. Cena jest równocześnie identyfikatorem towaru. Program przetestuj dla tablicy zbior = [2, 65, 83, 13, 61, 89, 13, 27, 1, 36, 89, 20, 19, 10, 149, 64, 27, 91, 13, 8].
Specyfikacja:
Dane:
n– liczba elementów w tablicy; liczba naturalnazbior–n-elementowa tablica zawierająca ceny długopisów; tablica liczb naturalnych
Wynik:
zbior– posortowana niemalejąco tablica
Na podstawie zaprezentowanego przykładu odpowiedz na pytanie, do jakiej grupy algorytmów należy algorytm sortowania przez wybieranie – stabilnych czy niestabilnych?
Jaka jest jego złożoność czasowa?
Algorytm sortowania przez wybieranie należy do grupy algorytmów niestabilnychalgorytmów niestabilnych.
Oznacza to, że w przypadku, kiedy sortujemy elementy o takiej samej wartości, mogą one zmienić pozycję względem siebie.
Jego złożoność czasowa wynosi O(nIndeks górny 22) i rośnie wykładniczo wraz ze wzrostem elementów w nieposortowanym zbiorze. Sortowanie odbywa się w miejscu.
W celu zamiany miejscami dwóch zmiennych można także wykorzystać funkcję swap(). Wywołanie jej przyjęłoby następującą postać: swap(zbior[i], zbior[minimalnyIndeks]);. Gdy używamy omawianej funkcji, nie musimy korzystać ze zmiennej pomocniczej.
Zadania:
Pracujesz w banku. Twoim przełożonym zależy na usprawnieniu procesu przeszukiwania bazy klientów; szef działu technicznego zasugerował, by zastosować algorytm wyszukiwania binarnegowyszukiwania binarnego, który omówiono w e‑materiale Wstęp do algorytmów sortowaniaWstęp do algorytmów sortowania. Zanim będzie można to zrobić, trzeba posortować dane klientów.
Napisz program sortujący w porządku niemalejącym n‑elementową tablicę zawierającą dane klientów. Każdy z klientów ma przyporządkowany do siebie numer identyfikatora.
Swój program przetestuj dla tablicy
zbior = [5, 7, 86, 32, 64, 54, 2].
Specyfikacja:
Dane:
zbior– tablican- elementowa zawierająca dane klientów; tablica liczb naturalnychn– liczba elementów w tablicyzbior;dodatnia liczba naturalna
Wynik:
posortowana niemalejąco tablica
zbior
Słownik
algorytmy, w których elementy o równej wartości nie występują po posortowaniu w tej samej kolejności, jaką miały w zbiorze nieposortowanym
w przypadku algorytmów stabilnych podczas sortowania w uporządkowanej tablicy nie zmienia się kolejność elementów o tych samych wartościach klucza – przykładowo, gdy w tablicy znajdą się obok siebie dwie liczby o wartości 6, to nie zostaną one zamienione miejscami
metoda odnajdowania elementów w uporządkowanych zbiorach; polega ona na wielokrotnym dzieleniu przeszukiwanego zbioru na dwie części i porównywaniu wartości szukanej z wyznaczonym elementem środkowym; gdy zbiór ma parzystą liczbę elementów, za element środkowy uznaje się jeden z dwóch elementów będących najbliżej środka
pętla działająca wewnątrz innej pętli