Przeczytaj
Implementacja algorytmu sortowania przez scalanie w języku Python
Wstęp
Sortowanie przez scalanie oparte jest na metodzie „dziel i zwyciężaj”metodzie „dziel i zwyciężaj”. Algorytm ten polega na podzieleniu sortowanej struktury danych na dwie części, następnie na rekurencyjnymrekurencyjnym sortowaniu każdej z tych części i ponownym scaleniuscaleniu już posortowanych części w jedną całość.
Napisz program w języku Python sortujący nierosnąco liczby z listy lista, wykorzystując algorytm sortowania przez scalanie (merge sort).
Specyfikacja:
Dane:
lista– lista liczb rzeczywistych; lista liczb, które należy posortować
Wynik:
lista posortowana nierosnąco
Założenia implementacji:
Tablicę liczb rzeczywistych będziemy reprezentować jako listę z języka Python. Nasza funkcja sortująca będzie przyjmowała trzy parametry: lista, indeks_poczatku, indeks_konca. Wczytaną tablicę posortujemy nierosnąco, zaczynając od pierwszego jej elementu (oznaczonego indeksem indeks_poczatku), a kończąc na ostatnim (indeks_konca). Proces sortowania będzie składał się z dwóch etapów:
dzielenia listy na dwie mniejsze części,
łączenia realizowanego przez funkcję
scal_dwie_czesci().
W celu uruchomienia funkcji rekurencyjnej musimy podać jej argumenty początkowe. Z racji tego, że chcemy posortować całą listę argument indeks_poczatku przyjmie wartość 0, a argument indeks_konca otrzyma wartość indeksu ostatniego elementu, czyli len(lista) - 1 (długość listy pomniejszona o jeden).
Słownik
proces polegający na wywoływaniu funkcji przez siebie samą aż do napotkania przypadku podstawowego
metoda, która polega na rekurencyjnym podzieleniu problemu na mniejsze, podobne problemy, znalezieniu ich rozwiązań, a następnie ponownym połączeniu ich w jedną całość, by otrzymać rozwiązanie całego problemu
łączenie dwóch posortowanych tablic, poprzez porównanie początkowych elementów z każdej tablicy, a następnie pobieranie pierwszego elementu z tablic, który jest większy/mniejszy i wstawianie go na koniec nowej, scalonej tablicy; wynikiem tej metody jest posortowana tablica zawierająca wszystkie elementy z obu tablic wejściowych