Tayyorlagan mustaqil ishi

Chiqish natijasi:
Tartiblanadigan qator:
45 23 53 43 18
Qobiq turidan keyin qator:
18 23 43 45 53
Qisqichbaqasimon tartib qo'shib qo'yish tartibida juda katta yaxshilanish vazifasini bajaradi va qatorni tartiblash uchun hatto qadamlarning yarmini ham bajarmaydi.


9.Heapsort
Heapsort - bu ro'yxat tartibida to'plash uchun ma'lumotlarning tuzilishi (min-evap yoki max-heap) ishlatiladigan usul. Dastlab biz tartiblanmagan ro'yxatdagi uyumni yaratamiz va shuningdek, qatorni tartiblash uchun to'plardan foydalanamiz.
Heapsort samarali, ammo tez emas yoki birlashtirish.

Yuqoridagi rasmda ko'rsatilgandek, avval saralanadigan massiv elementlaridan maksimal darajada uyum hosil qilamiz. Keyin biz to'pni kesib, oxirgi va birinchi elementni almashtiramiz. Hozirgi vaqtda oxirgi element allaqachon saralangan. Keyin biz yana qolgan elementlardan maksimal uyumni quramiz.
To'pni yana kesib o'ting va birinchi va oxirgi elementlarni almashtiring va saralangan ro'yxatga oxirgi elementni qo'shing. Bu jarayon uyada saralangan ro'yxatning birinchi elementiga aylanadigan bitta element qolmaguncha davom etadi.


Endi C ++ yordamida Heap Sortni joriy qilaylik.

#include using namespace std; // function to heapify the tree void heapify(int arr[], int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l < n && arr[l] > arr[largest]) largest = l; // If right child is larger than largest so far if (r < n && arr[r] > arr[largest]) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr[root], arr[largest]); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr[], int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr[0], arr[i]); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr[], int n) { for (int i=0; icout << arr[i] << " "; cout << "\n"; } // main program int main() { int heap_arr[] = {4,17,3,12,9}; int n = sizeof(heap_arr)/sizeof(heap_arr[0]); cout<<"Input array"<displayArray(heap_arr,n); heapSort(heap_arr, n); cout << "Sorted array"<displayArray(heap_arr, n); }