იხილეთ წყარო გვერდისთვის ჩასმით სორტირება

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

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

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

== ალგორითმი ==
[[ფაილი:Insertion-sort-example-300px.gif|მინი|230x230px| ჩასმით სორტირების სიმულაცია. |ალტ=]]
ჩასმის სორტირების მუშაობის პრინციპი შემდეგია: იგი მასივს ყოფს ორ ნაწილად: დახარისხებულად, რომლის ზომა თავიდან 1-ის ტოლია, რადგან 1-ელემენტიანი მასივი ყოველთვის დახარისხებულია, და დაუხარისხებელად, რომლის პირველ ელემენტს სვამს მასზე ნაკლები ან ტოლი და მასზე მეტი მნიშვნელობის მქონე ელემენტებს შორის. ალგორითმი მეორდება მანამ, სანამ დაუხარისხებელი ნაწილის ზომა ნულზე მეტია.

==იმპლემენტაცია C++-ზე==
<source lang="cpp">
#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<<" ";
}
</source>

== რესურსები ინტერნეტში ==
{{commonscat-inline|Insertion sort}}
* [https://lightscribes.wordpress.com/2015/07/22/%E1%83%A1%E1%83%9D%E1%83%A0%E1%83%A2%E1%83%98%E1%83%A0%E1%83%94%E1%83%91%E1%83%98%E1%83%A1-%E1%83%90%E1%83%9A%E1%83%92%E1%83%9D%E1%83%A0%E1%83%98%E1%83%97%E1%83%9B%E1%83%94%E1%83%91%E1%83%98-2/ დახარისხება ჩასმით]

[[კატეგორია:პროგრამირება]]
[[კატეგორია:ალგორითმები]]