Dərs vəsaiti baki -2018 azərbaycan döVLƏt neft və SƏnaye universiteti

5.Nizamlama və axtarış üsulları

5.1.Qeyri-rekursiv nizamlama üsulları
Eyni tipli elementlərdən təşkil olunmuş informasiyanın yadda saxlanılmasının ən münasib forması bu elementlərin nizamlanmış ardıcıllığından ibarətdir. İnformasiyanın nizamlanması lazım olan elementi asanlıqla tapmaq üçün yerinə yetirilir. Məsələn, ATS-də telefon nömrələrinin siyahısı, jurnalda tələbələrin soyadları və s. nizamlanmış halda saxlanarsa, burada gərəkli elementi axtarıb tapmaq daha asan və sürətli olar.
Fərz edək, ədədlər ardıcıllığı verilmişdir, ümumi halda nizamsızdır, yəni heç bir qanunauyğunluqla düzülməyən elementlər ardıcıllığıdır. Bu ardıcıllıqdan elementlərinin yerini dəyişməklə yeni ardıcıllıq quraq: , belə ki, münasibəti ödənsin, belə ardıcıllığa artma sırası ilə nizamlanmış ardıcıllıq deyilir. Azalma sırası ilə nizamlanmış ardıcıllığın tərifində “ ≤ “ işarəsi əvəzinə “≥” işarəsi olacaq. Aşağıda sadəlik üçün elə misallara baxılacaq ki, elementlər arasında yalnız ciddi bərabərsizlik işarəsi, məsələn, “ ˂ ” işarəsi olsun. Qeyd edək ki, əgər ardıcıllıqda elementlər ədədlərdən yox, başqa tipli elementlərdən ibarət olarsa, bu halda da onları müəyyən yolla nizamlamaq olar. Məsələn, əgər elementlər hərflərdən ( və ya sözlərdən) ibarət olarsa, və s. inikaslarını qurmaqla nizamlamanı yerinə yetirmək olar. Nəticədə hərflər və ədədlər arasında qarşılıqlı birqiymətli inikas qurulur, buna izomorfizm deyilir. a˂b˂c, aa˂ac və s. kimi münasibətlər qurula bilir[10,18].
Nizamlama üsullarını iki qismə bölmək olar:1) qeyri-rekursiv nizamlama üsulları, 2) rekursiv nizamlama üsulları[4].
Birinciyə aid olan ən vacib üsullar bunlardır: seçmə, qabarcıqlı və yerləşdirmə nizamlama üsulları, ikinciyə aid olan mühüm üsullar isə bunlardır: sürətli nizamlama və birləşdirmə ilə nizamlama üsulları.
1) Seçmə üsulu ilə nizamlama. Bu üsulu yerinə yetirmək üçün verilmiş {x_i} ardıcıllığından başqa əlavə i₀ identifikatorundan istifadə olunur. Artma sırası ilə nizamlama (bundan sonra nizamlama dedikdə məhz artma sırası ilə başa düşüləcək) zamanı soldan başlayaraq birinci iterasiyanın nəticəsində ən kiçik elementin nömrəsi i₀ identifikatoruna mənimsədilir. Birinci iterasiyanın sonunda x₁ elementinin yerinə i₀ nömrəli element və x₁-in köhnə qiyməti isə ilkin ardıcıllığın i₀ nömrəli elementinin yerinə yazılır. Bu əməliyyatı x₁↔x_i0 kimi işarə edək. Həqiqətdə bu əməliyyat belə yerinə yetirilir: a:=x₁, x₁:= x_i0, x_i0:=a. Burada a hər hansı yardımçı identifikatordur. İkinci iterasiyada sonuncu ardıcıllığın ikinci elementindən başlayaraq bir daha a və i₀ identifikatorlarından istifadə etməklə x₂↔x_i0 əməliyyatı yerinə yetirilir və s. Bu qayda ilə qurulan yerdəyişmələrə görə seçmə üsulunu bəzən yerdəyişmə üsulu adlandırırlar. Soldan başlamaqla nizamlamanı şərh etdik. Sağdan başlamaqla nizamlama buna əks istiqamətdə yerinə yetirilir, yəni birinci addımda maksimal element siyahının sağında yerləşdirilməklə sola doğru azalma istiqamətində yerinə yetirilir. Soldan sağa artma ilə seçmə üsulunun alqoritmi aşağıdakı kimidir:
Seçmə üsulunun proseduru:
i= dəyişməklə h=1 addımı ilə dövr:
i₀= i;
j= dəyişməklə h=1 addımı ilə dövr:
əgər x_j˂x_i0 olarsa, onda yerinə yetir i₀ :=j;
dövrün sonu;
x_i↔x_i0;
dövrün sonu;
prosedurun sonu.
Məsələn, fərz edək, 3,2,1,6,5,4 ardıcıllığını nizamlamaq lazımdır. Ardıcıllığın birinci elementi olan 3 ədədindən başlayaraq i₀=1 qəbul edirik, x_i0=3. 3-ü 2 ədədi ilə müqayisə edirik. 2˂3 olduğu üçün və bunun dayandığı pozisiyanın nömrəsi 2-yə bərabər olduğu üçün i₀=2 qəbul edirik. Sonra 2-ni növbəti mövqedə dayanan 1 ədədi ilə müqayisə edirik. 1˂2 olduğundan i₀=3 qəbul edirik. Növbəti pozisiyaların heç birində 1-dən kiçik ədəd olamadığı üçün bu iterasiyanın (dövrün) sonunda 1↔3 əməliyyatını yerinə yetiririk. Nəticədə 1,2,3,6,5,4 ardıcıllığını alırıq. 2-ci mövqedən, yəni 2 ədədindən başlayaraq i₀=2 qəbul edirik, x_i0=2. Bu dövrün nəticəsində məlum olur ki, bundan kiçik ədəd yoxdur. Ona görə də ardıcıllıqda heç bir yerdəyişmə baş vermir. Növbəti dövrdə i₀=3 qəbul edərək həmin qənaətə gəlmək mümkündür. Növbəti dövrdə i₀=4 qəbul edərək 5˂6 olduğundan i₀=5( yəni 5 ədədinin ünvanını i₀-a mənimsədirik). Bundan sonra 5 və 4-ü müqayisə edirik. 4˂5 olduğundan i₀=6 qəbul edirik. Ona görə də 4 ədədi ilə 6 ədədinin yerini dəyişərək 1,2,3,4,5,6 ardıcıllığını alırıq. Daha yerdəyişmə baş vermir və nizamlama proseduru sona çatır.