|
Tayyorlagan mustaqil ishi
|
| bet | 8/10 | | Sana | 30.11.2023 | | Hajmi | 336,4 Kb. | | #108869 |
Bog'liq VVVVVChiqish 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);
}
|
|
| |
