Kichik massivlar uchun qo’shilgan saralash. Qo’shilgan saralash

Kichik massivlar uchun qo’shilgan saralash.
Qo’shilgan saralash-MergeSort O(NlogN)  da ishlaydigan optimal saralash algoritmlaridan biri. Eng yaxshi holatda ham, eng yomon holatda ham O(NLogN) assimptotikada ishlaydi. Hamda, u barqaror saralaydi, ya'ni sonlar ketma-ketligini buzmagan holda. Masalan, sonlardan tashqari, ularning kalit sonlari bo'lsa, kalit soni 3 bo'lgan 2 soni kalit soni 5 bo'lgan 2 sonidan oldin kelsa, MergeSortda saralangandan so'ng ham kalit soni 3 bo'lgan 2 soni oldin keladi. QuickSortda doim ham bu shart bajarilavermaydi.

Algoritmning ishlash prinsipi quyidagicha: Massivni teng ikkiga bo'lamiz. O'ng tomonni alohida saralaymiz, chap tomonni alohida. So'ng ikki saralangan qismni O(n)  ya'ni n ta operatsiyada qo'shib, to'liq saralangan massiv olamiz. Aynan shu operatsiya, ya'ni qo'shish - Merge  ning hisobiga algoritm shunday nom olgan.

Endi chap va o'ng tomonlarini saralash uchun ham, ularni ikkiga bo'lib xuddi shu ishni bajaramiz va hk. Massivni bo'lishni to unda 2 ta element qolguncha davom ettiramiz.

Faraz qilaylik, bizda Merge(a: Array of Integer, Left, Mid, Right: Integer) funksiyasi bo'lsin. Ya'ni, a massivning  L -- Mid  qismi saralangan,  Mid + 1  --  R  qismi saralangan. Shu qismlarni qo'shib, L -- R kesmada saralangan qilish. Bunda Mid  L va R kesma o'rtasi.

Shunday Merge funksiya asosida MergeSortni quyidagicha yozish mumkin:
Procedure MergeSort(A: array of integer; L, R:integer);

Var Mid: Integer;

Begin

If (L < R) then begin

Mid := (L + R) div 2; // Massivni 2 bo'lib o'rtasini olamiz

MergeSort(A, L, Mid); // chap qismi uchun rekursiv chaqiramiz

MergeSort(A, Mid + 1, R); // o'ng qismi uchun rekursiv chaqiramiz

Merge(A, L, Mid, R);

end;

End;

Endi, Merge  funksiyani realizatsiya qilsak bo'ldi. Merge ni qiladigan ishini yana bir marta aytib o'tsak.

A massiv bor, L dan R gacha elementlarini saralash kerak. Bunda Mid ni L va R o'rtasi desak, L dan Mid  gacha massiv saralangan va Mid + 1 dan R gacha saralangan. Ya'ni L dan R gacha saralash uchun bitta siklda  L--Mid  va Mid+1 -- R  qismlarini qo'shib chiqsak bo'ldi. Qo'shishda ketma-ket, avval kichik sonni keyin katta sonni qo'shib boramiz.

Merge funksiyasi

Sort funksiyasi

Merge  funksiyada yordamchi massiv ishlatishga to'g'ri keladi. Ya'ni L dan R gacha bitta massivga ko'chirib olib, keyin A massivga saralab yozib qo'yamiz. A massivni ham parametrdan olib, global o'zgaruvchi qilib yozib qo'yamiz.

Var a, helper: Array[1..1000000] of Integer;

Procedure Merge(Left, Middle, Right: integer);

Var i, j, k: Integer;
Begin
// Left dan Right gacha yordamchi massivga ko'chirib olamiz
for i := Left to Right do helper[i] := a[i];
i := Left; // Left - Middle qism uchun

j := Middle + 1; // Middle+1 - Right qism uchun

k := Left;
While (i <= Middle) and (j <= Right) do begin

If helper[i] <= helper[j] then begin

a[k] := helper[i];

inc(i);

end else begin

a[k] := helper[j];

inc(j);

end;

inc(k); // keyingi elementga o'tamiz
end;
// Left - Mid qismida element qolib ketishi mumkin, ularni alohida qaraymiz:
While (i <= middle) do begin

a[k] := helper[i];

inc(i);

inc(k);

end;
While (j <= right) do begin

a[k] := helper[j];

inc(j);

inc(k);

end;

End;

MergeSort ni kamchiligi, qo'shimcha massiv ishlatilishida. Olimpiadada ham asosan QuickSort ishlatiladi, chunki tez yoziladi.