ჩასმით სორტირება

ჩასმით სორტირება — მონაცემთა სტაბილური, ადგილობრივი (ანუ არ იყენებს სხვა მასივს მონაცემთა შენახვისთვის) დახარისხების ერთგვარი ალგორითმი პროგრამირებაში. მუშაობს $O(n^{2})$ დროში, მაგრამ თუ მასივი თითქმის დალაგებულია, ის დაახლოებით წრფივ დროში მუშაობს. უარეს შემთხვევაში კვადრატულობა მაინც არაეფექტიანობას უსვამს ხაზს, თუმცა მას რამდენიმე უპირატესობა გააჩნია:

• მარტივი იმპლემენტაცია
• ბევრად ეფექტიანი კვადრატული სორტირების სხვა ალგორითმებთან შედარებით
• სტაბილური, ანუ არ ცვლის სხვადასხვა ტოლი მნიშვნელობის მქონე ელემენტების თანმიმდევრობას
• ადგილობრივი, მოითხოვს მხოლოდ $O(1)$ მეხსიერებას

ამ ალგორითმის მსგავსს ხშირად ვხვდებით ყოველდღიურ ცხოვრებაშიც კი, მაგალითად მაშინ, როდესაც ვცდილობთ ხელით დავალაგოთ სათამაშო ბანქო.

ალგორითმი

ჩასმით სორტირების სიმულაცია.

ჩასმის სორტირების მუშაობის პრინციპი შემდეგია: იგი მასივს ყოფს ორ ნაწილად: დახარისხებულად, რომლის ზომა თავიდან 1-ის ტოლია, რადგან 1-ელემენტიანი მასივი ყოველთვის დახარისხებულია, და დაუხარისხებელად, რომლის პირველ ელემენტს სვამს მასზე ნაკლები ან ტოლი და მასზე მეტი მნიშვნელობის მქონე ელემენტებს შორის. ალგორითმი მეორდება მანამ, სანამ დაუხარისხებელი ნაწილის ზომა ნულზე მეტია.

იმპლემენტაცია C++-ზე

#include <iostream>
using namespace::std;
int main(){
    int n;
    // ცვლადში ჩავწეროთ მასივის ზომა
    cout<<"Shemoitanet masivis zoma"<<endl;
    cin>>n;
    // შევქმნათ n-ზომის მასივი მთელი ელემენტებით
    int mas[n];
    // for-ციკლით შევავსოთ მასივი
    cout<<"Shemoitanet masivis elementebi"<<endl;
    for(int i=0; i<n; i++)
        cin>>mas[i];

    /*სორტირებისთვის შევქმნათ გარე for-ციკლი ცვლადით i, რომელიც შეინახავს დაუხარისხებელი
     ნაწილის პირველი ელემენტის ინდექს, მისი საწყისი მნიშვნელობა კი 1-ის ტოლია.*/
    for(int i=1; i<n; i++){
        /*შევქმნათ დროებითი ცვლადი, რომელიც შეინახავს მასივის i-ურ ელემენტს,
         რადგან წანაცვლებისას ის დაიკარგება*/
        int temp=mas[i];
        // შიგა ციკლის ცვლადზე განაცხადი გარეთ გავაკეთოთ, რადგან ის მის გარეთ გვჭირდება
        int j;
        /*ციკლის ცვლადის საწყისი მნიშვნელობაა დაუხარისხებელი მასივის პირველი ელემენტი,
         თუ ციკლის მნიშვნელობა 0-ის ტოლი გახდება, ან ის დახარისხებული ნაწილის რომელიმე
         ელემენტზე დიდი აღმოჩნდება, ციკლი შეწყდება. აგრეთვე სანამ ციკლი მუშაობს, უნდა წავანაცვლოთ
         ელემენტები ერთით მარჯვნივ*/
        for(j=i; j>0&&temp<mas[j-1]; j--){
            mas[j]=mas[j-1];
        }
        // საბოლოოდ j-ში შეინახება ის ინდექსი, რომელშიც უნდა შევიტანოთ i-ური ელემენტი
        mas[j]=temp;
    }

    // გამოვიტანოთ დალაგებული მასივი
    cout<<"dalagebuli masivi:"<<endl;
    for(auto i:mas)
        cout<<i<<" ";
}

რესურსები ინტერნეტში

• შეგიძლიათ იხილოთ მედიაფაილები თემაზე „ჩასმით სორტირება“ ვიკისაწყობში.
• დახარისხება ჩასმით