Massivin çeşidlənməsi problemini həll etmək üçün bir neçə əsas alqoritm var. Onların arasında ən məşhurlarından biri insertion sortdur. Aydınlığına və sadəliyinə, lakin səmərəliliyinə görə bu üsul əsasən proqramlaşdırmanın tədrisində istifadə olunur. Bu, əsas çeşidləmə mexanizmlərini başa düşməyə imkan verir.
Alqoritmin təsviri
Daxiletmə çeşidləmə alqoritminin mahiyyəti ondan ibarətdir ki, ilkin massiv daxilində düzgün sıralanmış seqment formalaşır. Hər bir element yoxlanılan hissə ilə bir-bir müqayisə edilir və lazımi yerə daxil edilir. Beləliklə, bütün elementləri təkrarladıqdan sonra onlar düzgün ardıcıllıqla düzülür.
Elementlərin seçilmə qaydası istənilən ola bilər, onlar özbaşına və ya hansısa alqoritmə uyğun seçilə bilər. Çox vaxt ardıcıl sadalama ardıcıl seqmentin formalaşdığı massivin əvvəlindən istifadə edilir.
Çeşidləmənin başlanğıcı belə görünə bilər:
- Massivin birinci elementini götürün.
- Müqayisə etmək üçün heç nə olmadığı üçün elementin özünü sifariş edildiyi kimi götürünardıcıllıqla.
- İkinci elementə keçin.
- Bunu çeşidləmə qaydasına əsasən birincisi ilə müqayisə edin.
- Lazım gələrsə, elementləri yerlərdə dəyişdirin.
- İlk iki elementi sıralı ardıcıllıqla götürün.
- Üçüncü elementə keçin.
- İkincisi ilə müqayisə edin, lazım gələrsə dəyişdirin.
- Əvəz edilibsə, onu birincisi ilə müqayisə edin.
- Üç elementi sıralı ardıcıllıqla götürün.
Və s. orijinal massivin sonuna qədər.
Real həyatda daxiletmə çeşidi
Aydınlıq üçün bu çeşidləmə mexanizminin gündəlik həyatda necə istifadə edildiyinə dair bir nümunə verməyə dəyər.
Məsələn, pul kisəsini götürün. Əskinas bölməsində yüz, beş yüz və min dollarlıq əskinaslar nizamsız şəkildə yatır. Bu qarışıqlıqdır, belə bir hodgepodge-da dərhal düzgün kağız parçasını tapmaq çətindir. Əskinaslar massivi çeşidlənməlidir.
Birincisi 1000 rublluq əskinasdır, ondan dərhal sonra isə - 100. Yüzü götürüb qabağına qoyuruq. Ardıcıl üçüncü 500 rubl, bunun üçün layiqli yer yüz ilə min arasındadır.
Eyni şəkildə biz "Axmaq" oynayarkən alınan kartları çeşidləyirik ki, onları idarə etməyi asanlaşdıraq.
Operatorlar və köməkçi funksiyalar
Daxiletmə çeşidləmə metodu giriş kimi çeşidlənəcək ilkin massivi, müqayisə funksiyasını və lazım gələrsə, elementlərin sadalanması qaydasını müəyyən edən funksiyanı qəbul edir. Əksər hallarda əvəzinə istifadə olunurmüntəzəm döngə bəyanatı.
Birinci elementin özü sifarişli çoxluqdur, ona görə də müqayisə ikincidən başlayır.
Alqoritm tez-tez iki dəyəri mübadilə etmək üçün köməkçi funksiyadan istifadə edir (mübadilə). O, yaddaşı sərf edən və kodu bir qədər yavaşladan əlavə müvəqqəti dəyişəndən istifadə edir.
Alternativ elementlər qrupunu kütləvi şəkildə dəyişdirmək və sonra cari elementi boş yerə daxil etməkdir. Bu halda, növbəti elementə keçid müqayisə müsbət nəticə verdikdə baş verir ki, bu da düzgün sıranı göstərir.
İcra nümunələri
Xüsusi tətbiq əsasən istifadə olunan proqramlaşdırma dili, onun sintaksisi və strukturlarından asılıdır.
Dəyərlərin mübadiləsi üçün müvəqqəti dəyişəndən istifadə edərək Klassik C tətbiqi:
int i, j, temp; üçün (i=1; i =0; j--) { if (massiv[j] < temp) fasilə; massiv[j + 1]=massiv[j]; massiv[j]=temp; } }
PHP Tətbiqi:
insertion_sort(&$a) { üçün ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Burada əvvəlcə çeşidləmə şərtinə uyğun gəlməyən bütün elementlər sağa sürüşdürülür, sonra isə cari element boş yerə daxil edilir.
Ware dövrəsindən istifadə edən Java kodu:
ictimai statik etibarsız insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Kodun ümumi mənası dəyişməz olaraq qalır: massivin hər bir elementi ardıcıl olaraq əvvəlkilərlə müqayisə edilir və lazım gəldikdə onlarla dəyişdirilir.
Təxmini iş vaxtı
Aydındır ki, ən yaxşı halda alqoritmin daxil edilməsi artıq düzgün şəkildə sifariş edilmiş massiv olacaqdır. Bu vəziyyətdə, alqoritm sadəcə olaraq hər bir elementi mübadilə etmədən düzgün yerdə olduğundan əmin etmək üçün yoxlamalı olacaq. Beləliklə, işləmə vaxtı birbaşa O(n) massivinin uzunluğundan asılı olacaq.
Ən pis halda daxiletmə tərs qaydada çeşidlənmiş massivdir. Bunun üçün çoxlu sayda permütasyon tələb olunacaq, icra vaxtı funksiyası elementlərin kvadratının sayından asılı olacaq.
Tamamilə sıralanmamış massiv üçün permütasyonların dəqiq sayı düsturla hesablana bilər:
n(n-1)/2
burada n orijinal massivin uzunluğudur. Beləliklə, 100 elementi düzgün ardıcıllıqla tənzimləmək üçün 4950 dəyişdirmə lazımdır.
Daxiletmə üsulu kiçik və ya qismən çeşidlənmiş massivləri çeşidləmək üçün çox səmərəlidir. Lakin hesablamaların yüksək mürəkkəbliyi səbəbindən onu hər yerdə tətbiq etmək tövsiyə edilmir.
Alqoritm bir çox başqa mürəkkəb çeşidləmə üsullarında köməkçi kimi istifadə olunur.
Bərabər dəyərləri çeşidləyin
Daxiletmə alqoritmi stabil adlanan növlərə aiddir. Bu o deməkdir ki,o, eyni elementləri dəyişdirmir, lakin onların orijinal sırasını qoruyur. Sabitlik indeksi bir çox hallarda düzgün sifariş üçün vacibdir.
Yuxarıdakılar rəqsdə daxiletmə növünün gözəl vizual nümunəsidir.
