Nazariy qism
Birlashmali saralash (Merge Sort) algoritmi asosiy beshta saralash algoritmlari (pufakchali saralash, tezkor saralash va boshqalar) dan biri bo`lib, chiziqli saralash algoritmlaridan farqli ravishda "bo`lib tashla va hukmronlik qil" tipidagi algoritm hisoblanadi.
Bu tipdagi algoritmlar katta hajmdagi masalalarni nisbatan kichik bo`lgan va oson yechiladigan qismlarga ajratgan holda bajaradi. Bunday algoritmlar masalalarni hal qilishda vaqtdan katta yutuq qilish imkonini beradi.
Birlashmali saralashda biz berilgan massivni uzunligi faqat 1 elementga teng bo`lgan qismlar qolmaguncha o`rtasidan ajratamiz. Keyin bu qismlar to`g`ri tartibda birlashtiriladi.
Keling ushbu massivni qaraylik:
Uni teng ikkiga ajratamiz:
Va yana har bir qismni ikkiga ajratamiz, toki 1 elementli qismlar qolmagunicha:
Massivni maksimal qisqa qismlarga ajratgandan so`ng, ularni to`g`ri tartibda birlashtiramiz, ya'ni:
Dastlab, 2 elementli saralangan guruhlarni olamiz va ularni 4 elementli guruhlarga birlashtiramiz va yakunida hammasini birlashtirgan holda saralangan massivni hosil qilamiz.
Algoritm ishlashi uchun quyidagi amallarni amalga oshirish kerak:
Massivni guruhlarga rekursiv ajratish amali ( sort).
To`g`ri tartibda birlashtirish amali (merge).
Topshiriq
9. Talabalarni birinchi va ikkinchi imtihoni natijalari bo’yicha kamayish tartibida.
#include
using namespace std;
void showstack(stack s) //s nomli stekni ko’rsatuvchi “showstack” nomli
funksiya e’lon qilinmoqda.
{
while (!s.empty()) //stek bo’shligi tekshirilmoqda
{
cout << '\t' <
s.pop();
}
cout << '\n';
}
int main ()
{
stack s; // s nomli stek e’lon qilinmoqda
Do'stlaringiz bilan baham: |
