Juda ham katta sonlar bilan ishlash Reja: Merge sort

int p1 = L, p2 = m+1;

int p = L;

while (p1 <= m && p2 <= R) {

if (a[p1] <= a[p2]) {

b[p] = a[p1];

p++;

p1++;

}

else {

inv += m-p1+1;

b[p] = a[p2];

p++;

p2++;

}

}


Shell sort (Qisqartirib boruvchi qadamlar orqali saralash)
Shell saralash 1959 yilda D.Shell tomonidan taklif qilingan bo‘lib, qo‘shish orqali saralashning modifikatsiyasi hisoblanadi.

Algoritm g’oyasi
Faraz qilaylik a[0],a[1],a[2],…, a[n] boshlang’ich elementlar ketma-ketligi bo’lsin.
1-qadam.Boshlang’ich ketma-ketlikning har r₁ o’rnida joylashgan elementlari guruxlanib, har bir gurux alohida qo’shish usuli orqali saralanadi({a[0], a[r₁], a[2*r₁],…,}, {a[1], a[1+r₁], a[1+2*r₁],…,} в.ҳ.).
2-qadam. Xosil qilingan ketma-ketlikda har r₂ o’rinda joylashgan elementlar guruhlanib, har bir guruh alohida saralanadi.
k-qadam. k-1 qadamda hosil bo’lgan ketma-ketlik oddiy qo’shish usuli orqali saralanadi.


Berilgan massivni saralash Shell usuli C++

#include

/* funktsiya shellSort yordamida arrni tartiblash uchun */
void shellSort(int arr[], int n)
{ // Katta bo'shliqdan boshlang, keyin bo'shliqni kamaytiring
for (int gap = n / 2; gap > 0; gap /= 2) {
// Ushbu bo'shliqning kattaligi uchun bo'sh joyni qo'shing.
// birinchi bo'shliqlar elementlari arr [0..gap-1] allaqachon tartibda
// butun massiv bo'lguncha yana bitta element qo'shishni davom ettiring
// bo'sh joy saralangan
for (int i = gap; i < n; i += 1) {
// bo'sh joyni ajratilgan elementlarga arr [i] qo'shish
// arr [i] ni tempda saqlang va i holatida teshik qiling
int temp = arr[i];
// oldingi bo'shliqlarni tartiblangan elementlarni to'g'ri qadar o'zgartiring
// arr [i] uchun joy topildi
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
// temp (original arr [i]) ni to'g'ri joyda joylashtiring
arr[j] = temp;
} } }
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
std::cout << arr[i] << " ";
std::cout << "\n";
}
int main()
{
int arr[] = { 12, 34, 54, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
std::cout << "Array before sorting: \n";
printArray(arr, n);
shellSort(arr, n);
std::cout << "Array after sorting: \n";
printArray(arr, n);
}