გადათვლით დახარისხება

გადათვლით დახარისხება — დახარისხების ერთგვარი ალგორითმი პროგრამირებაში. დახარისხების ეს მეთოდი მხოლოდ კერძო შემთხვევებშია გამოყენებადი, როდესაც დასალაგებელი კონტეინერის ელემენტები არის მთელი რიცხვები, და დიაპაზონი არის კონტეინერის ელემენტების რაოდენობის რიგის. მეთოდის სისწრაფე პროპორციულია კონტეინერის ელემენტების მნიშვნელობათა დიაპაზონისა და კონტეინერის ელემენტების რაოდენობის ჯამისა. მეთოდის გამოყენებისთვის საჭიროა დამხმარე კონტეინერი, რომლის ელემენტების რაოდენობა ტოლია დასახარისხებელი კონტეინერის დიაპაზონის (ანუ, უდიდესი და უმცირესი ელემენტის სხვაობის). გადათვლით დახარისხების დროს საწყისი კონტეინერის ელემენტები განიხილება როგორც სხვა (დამხმარე)კონტეინერის ინდექსები. ალგორითმის იდეა შემდეგია: კონტეინერის ნებისმიერი $x$ ელემენტისათვის წინასწარ დავთვლით ამ კონტეინერის რამდენი ელემეტია $x$-ზე ნაკლები (ვთქვათ $m$), მაშინ ის შეგვიძლია საბოლოო კონტეინერში პირდაპირ ჩავწეროთ $(m+1)$–ე ადგილზე, ანუ ინდექსით $m$. თუ შემავალ კონტეინერში გვხვდება ერთმანეთის ტოლი რიცხვები, მაშინ დამატებით უნდა ვიზრუნოთ, რომ ტოლი რიცხვები ერთმანეთის მეზობლად და ძველი რიგის შენარჩუნებით განლაგდეს.

მიუხედავად თავისი კერძოობისა, ამ მეთოდს ორი უპირატესობა აქვს ბევრ სხვა მეთოდთან შედარებით: მისი შესრულების დრო არის $O(n+k)$ რიგის და ეს არის მდგრადი ალგორითმი, რაც ნიშნავს შემდეგს: საწყის მასივში ერთმანეთის ტოლი ელემენტები საბოლოო (უკვე დალაგებულ) მასივში ინარჩუნებენ თავიანთ ფარდობით რიგს ერთმანეთის მიმართ.

ალგორითმი

განვიხილოთ პროგრამული კოდი. ვიგულისხმოთ, რომ კონტეინერი ვექტორია. ვთქვათ, საწყისი ვექტორი არის $a$, დამხმარე ვექტორი არის $c$, ხოლო $b$ ვექტორი არის საბოლოო, ანუ პასუხი. სტრიქონ 1-ში განისაზღვრება დამხმარე ვექტორის უდიდესი ინდექსი, - რადგან დამხმარე ვექტორის ინდექსებს წარმოადგენენ საწყისი ვექტორის ელემენტები. შემდეგ, ელემენტების რაოდენობის მისაღებად, ეს სიდიდე უნდა გაიზარდოს ერთით, რადგან უდიდიესი ინდექსი ელემენტების რაოდენობაზე ერთით ნაკლებია. დამხმარე ვექტორის ინიციალიზაციის დროს (სტრიქონი 3), დამხმარე $c$ ვექტორი იქმნება და ივსება ნულებით. დამხმარე ვექტორში ზუსტად იმდენი ნულია, რამდენიც არის ელემენტების დიაპაზონი საწყის ვექტორში. სტრიქონებში 4-5, დამხმარე $c$ ვექტორის $c[i]$ ელემენტი ხდება $a$ ვექტორის იმ ელემენტების რაოდენობის ტოლი, რომლებიც $i$ ინდექსის ტოლია. სტრიქონებში 6 და 7, დამხმარე $c$ ვექტორში $c[i]$ ელემენტად იწერება $a$ ვექტორის იმ ელემენტების რაოდენობა, რომლებიც არ აღემატებიან $i$ ინდექსს. ბოლოს, ყოველი ელემენტი თავსდება $b$ ვექტორში მის ადგილზე (სტრიქონები 8 და 9). ეს ადგილი განისაზღვრება შემდეგნაირად. თუ შემომავალ ვექტორში ყველა ელემენტი განსხვავებულია, მაშინ დალაგებულ ანუ გამომავალ ვექტორში $a[i]$ მოთავსდება $c[a[i]]-1$ ინდექსით, რადგან ზუსტად ამდენი ელემენტი არის $a[i]$ - ზე ნაკლები; თუ შემავალი მასივი შეიცავს ერთმანეთის ტოლ ელემენტებს, მაშინ ელემენტები მოთავსდება ისევ $c[a[i]]-1$ ინდექსით, მაგრამ ყოველი ელემენტის ჩაწერისას $c[a[i]]$ უნდა შევამციროთ $1$-ით (ერთმანეთს რომ არ გადაეწეროს).

ალგორითმი

მეთოდი 1:

void countingSort(vector<int>& a, vector<int>& b){
    int k = *max_element(a.begin(), a.end());
    k++;
    vector<int> c(k);
    for (int i=0; i< a.size(); i++)
        c[a[i]]++;
    for (int i=1; i<k; i++)
        c[i] += c[i-1];
    for (int i= a.size()-1; i>=0; i--){
        b[c[a[i]]-1] = a[i];
        c[a[i]]--;
    }
}

მეთოდი 2:

void countingSort(vector<int>&a){
      int k=*max_element(a.begin(),a.end());
      k++;
      vector<int>freq(k);
      for(int i=0; i<a.size(); i++)
            freq[a[i]]++;

      int i=0,j=0;
      while(i<k)
            if(freq[i]>0)a[j++]=i,freq[i]--;
            else i++;
}

ლიტერატურა

• კობა გელაშვილი, მონაცემთა სტრუქტურები. მე-8 თავი: გადათვლით დახარისხება.