Przeczytaj
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 (omówiony w e‑materiale Wstęp do algorytmów sortowaniaWstęp do algorytmów sortowania). Zanim będzie można to zrobić, trzeba posortować identyfikatory klientów.
Napisz program sortujący niemalejąco
n-elementową tablicę, zawierającą identyfikatory klientów. Każdy z klientów ma przyporządkowany do siebie numer identyfikatora.Swój program przetestuj dla tablicy
zbior = [5, 7, 3, 4, 1, 6, 8, 10, 24, 14].
Specyfikacja problemu:
Dane:
n– liczba naturalna; liczba elementów tablicytabzbior–n-elementowa tablica liczb naturalnych
Wynik:
zbior– posortowana niemalejąco n‑elementowa tablica liczb naturalnych
Porównaj swoje rozwiązanie z przedstawionym w prezentacji.
Napisz program sortujący niemalejąco dane zawarte w pliku identyfikatory.txt.
Plik identyfikatory.txt zawiera 100 liczb naturalnych należących do przedziału . Każda liczba zapisana jest w osobnym wierszu. Zadbaj o prawidłowe wczytanie danych z pliku. Rozwiązanie zapisz do pliku identyfikatory_posortowane.txt.
Przykładowe dane
Plik identyfikatory.txt
Rozwiązanie
Plik identyfikatory_posortowane.txt
Złożoność czasowa
Złożoność czasowa algorytmu wynosi i rośnie wykładniczo wraz ze wzrostem elementów w nieposortowanym zbiorze. Przeciętna złożoność czasowa jest taka sama, jak pesymistyczna, ponieważ algorytm sortowania przez wybieranie dla danej długości ciągu zawsze wykona taką samą liczbę porównań. Złożoność czasowa jest również taka sama dla ciągu wejściowego, który byłby już posortowany.
Stabilność
Algorytm sortowania przez wybieranie nie jest algorytmem stabilnym. Oznacza to, że nie utrzymuje kolejności występowania dla elementów o tym samym kluczu. W przypadku sortowania przez wybieranie, sortowanie odbywa się w miejscu.
Załóżmy, że mamy do posortowania nierosnąco tablicę: [4,4,3,2,5,1].
Znajdują się w niej dwie liczby 4. Żeby zobrazować, że algorytm nie jest stabilny, oznaczmy je odpowiednio 4a i 4b: [4a, 4b, 3, 2, 5, 1].
W pierwszym wykonaniu głównej pętli algorytmu zamienimy wartość 5 z wartością 4a: [5, 4b, 3, 2, 4a, 1].
Zwróć uwagę na to, że przy sortowaniu nierosnącym szukamy maksimum, nie minimum (jak wcześniej).
W drugiej iteracji nic się nie zmieni – wartość 4b pozostanie na swoim miejscu, ponieważ w nieposortowanej jeszcze części tablicy nie ma wartości większej niż 4.
W kolejnej iteracji zamienimy wartość 3 z wartością 4a: [5, 4b, 4a, 2, 3, 1].
Po posortowaniu tablica będzie wyglądała następująco: [5, 4b, 4a, 3, 2, 1]. Widzimy, że w nieposortowanej tablicy 4a znajdowało się przed 4b. W posortowanej tablicy natomiast mamy sytuację odwrotną: 4b jest przed 4a. Na przykładzie pokazaliśmy, że algorytm sortowania przez wybieranie nie jest algorytmem stabilnym.
Słownik
algorytmy, w których elementy o równej wartości klucza nie występują po posortowaniu w tej samej kolejności, jaką miały w zbiorze nieposortowanym
w przypadku algorytmów stabilnych w uporządkowanej tablicy nie zmienia się kolejność elementów o tych samych wartościach klucza, np. gdy w tablicy znajdą się dwie liczby o wartości 6, ta mająca niższy indeks przed posortowaniem tablicy, po zakończeniu działania algorytmu wciąż będzie miała mniejszy indeks
metoda odnajdowania elementów w uporządkowanych zbiorach; polega ona na wielokrotnym dzieleniu przeszukiwanego zbioru na dwie części i na porównywaniu wartości szukanej z elementem znajdującym się w środku dzielonego obszaru
pętla działająca wewnątrz innej pętli