Katedra Informatyki Stosowanej PŁ

dr inż. Anna Fabijańska

Podstawy Programowania

Laboratorium 6

Sortowanie przez scalanie

Zadanie 1:

Wynikiem scalenia dwóch uporządkowanych zbiorów: {1 3 6 7 9} { 2 3 4 6 8 }
jest zbiór postaci {1 2 3 3 4 6 6 7 8 9}. Napisać funkcję do scalania dwóch
zbiorów uporządkowanych.

Algorytm scalania zbiorów uporządkowanych:

1. porównaj ze sobą pierwsze elementy z każdego ze scalanych zbiorów;
2. mniejszy element wstaw do nowego zbioru (wynikowego) usuwając go

jednocześnie ze zbioru źródłowego;

3. powtarzaj czynności 1 i 2, aż oba scalane zbiory będą puste.

Zaprezentować działanie napisanej funkcji w programie. Uzupełnić program
o funkcję sprawdzającą, czy scalane zbiory są posortowane.

Zadanie 2:

Napisać funkcję dokonującą sortowania ciągu liczb całkowitych przez scalanie.
Funkcja powinna działać rekurencyjnie, wykorzystując algorytm typu „rządz
i dziel”. Zaprezentować działanie napisanej funkcji w programie.

Algorytm sortowania przez scalanie:

1. jeśli zbiór zawiera więcej niż jeden element, to podziel go na dwie równe

podzbiory (lub prawie równe, jeśli zbiór sortowany ma nieparzystą liczbę
elementów);

2. posortuj pierwszy podzbiór stosując ten sam algorytm;
3. posortuj drugi podzbiór stosując ten sam algorytm;
4. połącz dwa uporządkowane podzbiory w jeden zbiór uporządkowany.

Sortowanie przez scalanie zastosowane do 7-elementowego zbioru [źródło: Wikipedia]