|
Tayyorlagan mustaqil ishi
|
| bet | 6/10 | | Sana | 30.11.2023 | | Hajmi | 336,4 Kb. | | #108869 |
Bog'liq VVVVVChiqish natijasi:
Kirish qatori
12 23 3 43 51
Massiv Quicksort bilan tartiblangan
3 12 23 43 51
Yuqoridagi yorliqni bajarishda, bizda serialning oxirgi elementi bo'lgan pivot elementi atrofida kirish massivini ajratish uchun foydalaniladigan qism tartibi mavjud. Keyin biz rasmda ko'rsatilgandek sub-massivlarni alohida tartiblash uchun rekordni rekursiv ravishda chaqiramiz.
7.Merge Sort
Bu "bo'linish va zabt etish" strategiyasidan foydalanadigan yana bir usul. Ushbu texnikada biz birinchi navbatda ro'yxatni teng yarmga ajratamiz. Keyin ikkala ro'yxat saralanishi uchun biz ushbu ro'yxatlar bo'yicha tartiblash texnikasini mustaqil ravishda amalga oshiramiz. Va nihoyat, biz to'liq tartiblangan ro'yxatni olish uchun ikkala ro'yxatni ham birlashtiramiz.
Birlashtirish va tez tartiblash boshqa tartiblash texnikalariga qaraganda tezroq. Ro'yxat kattalashgan taqdirda ham ularning ishlashi saqlanib qoladi.
Keling, Merge Sort texnikasining rasmini ko'raylik.
Yuqoridagi rasmda, birlashtirish tartiblash texnikasi har bir pastki chiziqda bitta element mavjud bo'lmaguncha, dastlabki massivni subarrayslarga qayta-qayta ajratib qo'yganini ko'ramiz. Bu amalga oshirilgandan so'ng, subarrayslar mustaqil ravishda saralanadi va to'liq tartiblangan qatorni yaratish uchun birlashtiriladi.
Keyingi, C ++ tilidan foydalanib, Birlashtirish tartibini amalga oshiramiz.
#include
using namespace std;
void merge(int *,int, int , int );
void merge_sort(int *arr, int low, int high)
{
int mid;
if (low < high){
//divide the array at mid and sort independently using merge sort
mid=(low+high)/2;
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
//merge or conquer sorted arrays
merge(arr,low,high,mid);
}
}
// Merge sort
void merge(int *arr, int low, int high, int mid)
{
int i, j, k, c[50];
i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
c[k] = arr[i];
k++;
i++;
}
else {
c[k] = arr[j];
k++;
j++;
}
}
while (i <= mid) {
c[k] = arr[i];
k++;
i++;
}
while (j <= high) {
c[k] = arr[j];
k++;
j++;
}
for (i = low; i < k; i++) {
arr[i] = c[i];
}
}
// read input array and call mergesort
int main()
{
int myarray[30], num;
cout<<"Enter number of elements to be sorted:";
cin>>num;
cout<<"Enter "<for (int i = 0; i < num; i++) { cin>>myarray[i];
}
merge_sort(myarray, 0, num-1);
cout<<"Sorted array\n";
for (int i = 0; i < num; i++)
{
cout<}
}
|
|
| |
