Mavzu: murakkab saralash algortmlari juda ham katta sonlar bilan ishlash

Saralanadigan qator quyidagicha:

Endi har bir o'tish uchun biz hozirgi elementni uning oldingi elementlari bilan taqqoslaymiz. Shunday qilib, birinchi o'tishda biz ikkinchi elementdan boshlaymiz.

Shunday qilib, N elementlari bo'lgan massivni to'liq tartiblash uchun biz N soni o'tishini talab qilamiz.
Yuqoridagi chiqish kiritish tartibida ishlatilgan to'liq tartiblangan qatorni ko'rsatadi.
6.Quick sort (Tez saralash)
Quicksort - ma'lumotlarni saralash uchun ishlatilishi mumkin bo'lgan eng samarali algoritm. Ushbu usulda "bo'linish va g'alaba qozonish" strategiyasidan foydalaniladi, bunda muammo bir nechta kichik dasturlarga bo'linadi va ushbu kichik dasturlarni echib bo'lgandan so'ng ular to'liq tartiblangan ro'yxat uchun birlashtiriladi.
Quicksortda biz avval pivot elementi atrofida ro'yxatni ajratamiz, so'ngra boshqa elementlarni pivot elementiga muvofiq tegishli holatga joylashtiramiz.

Yuqoridagi rasmda ko'rsatilgandek, Quicksort texnikasida biz massivni pivot elementiga tenglashtiramiz, shunday qilib, aylantiruvchidan kichik bo'lgan barcha elementlar chap tomonda, pivotdan kattaroqlari o'ng tomonda joylashgan. Keyin biz ushbu ikkita massivni mustaqil ravishda yig'amiz va ularni tartiblashtiramiz va natijada tartiblangan qatorga ega bo'lish uchun ularni birlashtiramiz yoki engamiz.
Quicksortning kaliti - bu aylanma elementni tanlash. Bu massivning birinchi, oxirgi yoki o'rta elementi bo'lishi mumkin. Belgilangan elementni tanlab olishdan keyingi birinchi qadam - bu massivni kerakli darajada ajratishimiz uchun pivotni to'g'ri joyga o'rnatish.
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 (Birlashtirib saralash)
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.