Ocena brak

Opisz schemat działania algorytmu sortowania przez scalanie

Autor /Barnim7777 Dodano /29.12.2011

Sortowanie przez scalanie polega na podzieleniu za pomocą procedury rekurencyjnej n –elementowej listy wejściowej na n pojedynczych elementów. Następnie algorytm wykonuje kolejno porównania: najpierw par elementów (tworząc posortowane ciągi 2 –elementowe), potem ciągów 2 elementowych (tworząc posortowane ciągi 4 elementowe), i tak do chwili gdy nie powstanie posortowana n –elementowa lista.

Najistotniejszym etapem tego algorytmu jest etap scalania. W etapie tym następuje porównanie dwóch identycznych części (n –elementowych ciągów) i przekształcenie ich tak by utworzyły 2n –elementowy, posortowany ciąg wynikowy. Porównanie odnosi się zawsze do dwóch pierwszych elementów ciągów wejściowych, a do nowopowstającego, posortowanego ciągu wynikowego przepisywany jest mniejszy element porównania.

Opis słowny algorytmu:

Procedura SORTUJ listę L;

1. jeśli lista zawiera tylko jeden element to jest posortowana

2. w przeciwnym razie wykonaj co następuje

a. podziel listę L na L1 i L2

b. wywołaj SORTUJ listę L1

c. wywołaj SORTUJ listę L2

d. scal posortowane listy L1 i L2 w jedną posortowaną liste L (etap iteracyjny)

3. wróć do poziomu wywołania

Do góry