შერჩევითი სორტირება

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

შერჩევითი დალაგების სიმულაცია. დაუხარისხებელი ნაწილის უმცირესი ელემენტის ამავე ნაწილის თავში დამატებით.

იმპლემენტაცია 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,
    რომელიც შეინახავს დაუხარისხებელი ნაწილის ბოლო ინდექსის მნიშვნელობას.ცხადია,
    ის თავიდან მასივის ბოლო ელემენტის ინდექსის ტოლია*/
    for(int i=n-1; i>0; i--){
        //შევქმნათ ცვლადი, რომელიც თითოეული დაუხარისხებელი ნაწილის უდიდესი ელემენტის ინდექსს შეინახავს
        int largest=0;
        //გადავარჩიოთ ელემენტები i-ს ჩათვლით
        for(int j=1; j<=i; j++){
            // თუ მიმდინარე ელემენტი largest-ზე დიდია, largest-ი გახდება მიმდინარე ელემენტის ტოლი.
            if(mas[j]>mas[largest])
                largest=j;
        }
        /*შიდა ციკლის დასრულების შემდეგ ადგილები გავუცვალოთ დაუხარისხებელი ნაწილის
         * ბოლო ელემენტსა და უდიდეს ელემენტს*/
        swap(mas[largest],mas[i]);
    }
    // გამოვიტანოთ დალაგებული მასივი
    cout<<"dalagebuli masivi:"<<endl;
    for(auto i:mas)
        cout<<i<<" ";
}

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

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