Mühazirə 1 Giriş Əsas anlayışlar. "Məlumat"

Birləşmə metodu ilə çeşidləmə

Bu metodun əsasını iki nizamlı massivin (faylın) birləşdirilməsi nəticəsində bir nizamlı massivin (faylın) alınması təşkil edir.

Metodun mahiyyəti. Fərz edək ki, x və y artan ardıcıllıqla nizamlanmış massivlərdir. Onların birləşdirilməsindən nizamlı z massivi yaradılmalıdır. Birləşdirmə x və y massivlərinin elementlərini növbə ilə z massivinə yerləşdirilməsi ilə aparılır. X və Y massivlərinin elementləri cüt-cüt müqayisə olunur və kiçiyi növbəti element kimi z-ə göndərilir. Müqayisə üçün növbəti element seçilmiş elementin aid olduğu massivdən götürülür. Aydındır ki, z massivinin uzunluğu x və y massivlərinin uzunluqlarının cəminə bərabərdir.
Birləşmə metodu ən çox fayl strukturları üçün, yəni xarici çeşidləmədə istifadə olunur.


Birləşmə ilə çeşidləmənin alqoritmi (Birləşmə alqoritmi)

Bu alqoritmi iki nizamlı x₁<=x₂<=….<=x_m və y₁<=y₂<=…<=y_n massivin bir z₁<=z₂<=….<=z_m+n nizamlı massivdə birləşməsini təmin edir.

1. Başlanğıc təyinatlar.
i:=1; j:=1; k:=1 qəbul etməli.
2. Kiçik elementin təyini.
Əgər x_i<=y_j olsa 2-ci mərhələyə, əks halda 5-ci mərhələyə keçməli.

3. xi-ni çıxarmalı.

z_k:=x_i; k:=k+1; i:=i+1 Əgər i<=m olsa, 2-ci mərhələyə qayıtmalı.

4. y massivinin bütün elementlərini z-ə köçürməli.

z_k:=y_j; z_k+1:=y_j+1; ….; z_m+n:=y_n; 7-ci mərhələyə keçməli.
5. yj-ni çıxarmalı.
z_k:=y_j; k:=k+1; j:=j+1; Əgər j<=n olsa , 2-ci mərhələyə qayıtmalı.
6. x massivinin bütün elementlərini z-ə köçürməli.
z_k:=x_i; z_k+1:=x_i+1 ;….; z_m+n:=x_m;
7. Son. Alqoritmi qurtarmalı.
EHM-lə çeşidləmə üçün nəzərdə tutulmuş bu alqoritmi ilk dəfə Fon Neyman vermişdir.