დალაგება გროვებით

Heap Sort

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

ქვემოთ მოცემულ სურათზე ნაჩვენებია გროვებით დალაგების ალგორითმის მუშაობის პროცესი ანიმაციურად.

        მოვიყვანოთ ალგორითმის განხორციელების კონკრეტული მაგალითი. პროგრამული კოდი დაწერილია C-ზე:

void Heapify( int k, int a[], int N)
{
  int v;
  int leftChild, rightChild, maxValueChild;
  v = a[k];
  while ( k < N/2 )
  {
  leftChild = (!k)?1:2*k;
  rightChild = leftChild+1;
  if( rightChild < N ) //მიმდინარე ელემენტს ყავს ორივე შვილი
  {
  if( a[leftChild] < a[rightChild] ) //შევადაროთ შვილების მნიშვნელობები
  maxValueChild = rightChild;
  else
  maxValueChild = leftChild;
  }else if( leftChild < N )  //ელემენტს ყავს მხოლოდ მარცხენა შვილი
  maxValueChild = leftChild;

                if( v >= a[maxValueChild] ) //შევადაროთ მშობელს, თუ არ აღემატება გავჩერდეთ
  break;

  a[k] = a[maxValueChild]; //ავიტანოთ მაქსიმალური მნიშვნელობის  მქონე შვილი მშობლის ადგილზე
  k = maxValueChild; //ელემენტის მიმდინარე პოზიციად შევინახოთ  მაქსიმალური მნიშვნელობის  მქონე შვილის პოზიცია
  }
  a[k] = v; //გადმოვიტანოთ მოძრავი ელემენტი დადგენილ პოზიციაზე
}

void HeapSort( int* a, unsigned int N )

{

        int k, v;

  for( k=N/2; k>=0; --k ) //გავირბინოთ ყველა ელემენტზე ფოთლების გარდა

                Heapify( k, a, N );

        for( k=N-1; k>0; --k )

        {

                v = a[0]; //ვიმახსოვრებთ გროვის ძირს v-ში

                a[0] = a[--N]; //გროვის ძირში გადმოგვაქვს გროვის ბოლო ელემენტი

                Heapify( 0, a, N ); //ვახდენთ გროვის ძირითადი თვისების აღდგენას

                a[k] = v; //ვსვავთ ელემენტს დალაგებული მასივის თავში

        }

}

        საბოლოოდ გროვებით სორტირების დროითი სირთულე არის O(n log(n)). კარგ შემტხვევაში დროითი სირთულე მცირდება O(n)-მდე.