Question

Czym jest algorytm sortowania przez scalanie i jak wygląda w języku Python? Przygotuj 2 proste ćwiczenia związane z tym algorytmem. Prosiłbym was o krótkie objaśnienie z czym się to w ogóle je i na czym to polega, bo mam o tym opowiedzieć w klasie, tak w miarę łopatologicznie, i pomysły przynajmniej jakieś na te ćwiczenia. Wszystko ma być pod Pythona. Z góry dzięki.

Answer 1

Mam nadzieję, że pojęcia: algorytm, sortowanie, scalanie, składnia, nie są ci obce.

Mam również nadzieje, że Python nie jest ci obcy.

 

Sortowanie przez scalanie to jedna z metod sortowania.

Polega na tym, że dany ciąg liczb najpierw dzielimy, aż będziemy mieli po jednej, a później scalamy:

 

do posortowania:

(3,5,2,1)

 

dzielimy na:

(3,5) , (2,1)

dalej dzielimy:

(3),(5),(2),(1)

Mamy po jednej, scalamy(w dobrej kolejności):

(3,5),(1,2)

...

(1,2,3,5)

 

Mechanizm już jest. Kod w Pythonie(pozwoliłem sobie skopiować z wikipedii) jest w załączniku, bo jak tu wklejałem, to się nie zachowały wcięcia, które w Pythonie należą do składni.

 

Algorytm składa się z dwóch metod.

MergeSort dzieli nam aż będzie po jednej liczbie, merge scala.

 

Merge działa na zasadzie porównywania dwóch elemntów i wyborze mniejszego.

 

Pomysł na dwa krótkie ćwiczenia:

- sortowanie krótkiej listy liczb(jak wyżej)

- sortowanie słów wg. długości

 

Jak coś więcej potrzeba to pytaj.