|
Tashqi saralash algoritmlari
|
| bet | 13/16 | | Sana | 15.11.2023 | | Hajmi | 29,81 Mb. | | #99092 |
Bog'liq Dilshoda Algoritm mustaqilTashqi saralash algoritmlari
Saralash paytida tashqi xotiradan foydalanadigan saralash algoritmlari ushbu turkumga kiradi. Ular ichki tartiblash algoritmlariga qaraganda nisbatan sekinroq. Masalan, birlashtirish tartiblash algoritmi. U har biri RAMga mos keladigan qismlarni saralaydi, so'ngra tartiblangan bo'laklarni birlashtiradi.
Birlashtirish saralash massivni kichikroq kichik massivlarga bo‘lish, har bir kichik massivni saralash va so‘ng saralangan pastki massivlarni yana birlashtirib, yakuniy tartiblangan massivni hosil qilish orqali ishlaydigan tartiblash algoritmi sifatida aniqlanadi.
Oddiy qilib aytganda, birlashtirish tartiblash jarayoni massivni ikki yarmiga bo'lish, har bir yarmini tartiblash va keyin tartiblangan yarmini yana birlashtirishdir. Bu jarayon butun massiv saralanmaguncha takrorlanadi.
Birlashtirish tartibi
Sizni qiziqtirgan narsa bu algoritmning o'ziga xosligi nimada. Bizda allaqachon bir qator tartiblash algoritmlari bor, nega bizga bu algoritm kerak? Birlashtirishning asosiy afzalliklaridan biri shundaki, u vaqt murakkabligi O(n log n)ga ega, ya’ni u katta massivlarni nisbatan tez saralay oladi. Bu turg'un tartibdir, ya'ni tartiblash jarayonida teng qiymatli elementlarning tartibi saqlanib qoladi.
Birlashtirish saralash katta ma'lumotlar to'plamlarini saralash uchun mashhur tanlovdir, chunki u nisbatan samarali va amalga oshirish oson. U tez-tez saralash tartibining umumiy ish faoliyatini yaxshilash uchun tez saralash kabi boshqa algoritmlar bilan birgalikda ishlatiladi.
Merge sort ish jarayoni:
Buni rekursiv algoritm sifatida tasavvur qiling-a, massivni keyingi bo'linib bo'lmaguncha doimiy ravishda yarmiga bo'ladi. Bu shuni anglatadiki, agar massiv bo'sh bo'lib qolsa yoki faqat bitta element qolsa, bo'linish to'xtaydi, ya'ni bu rekursiyani to'xtatish uchun asosiy holatdir. Agar massiv bir nechta elementga ega bo'lsa, massivni ikkiga bo'ling va har bir yarmida birlashma tartibini rekursiv ravishda chaqiring. Nihoyat, ikkala yarmi tartiblanganda, birlashtirish operatsiyasi qo'llaniladi. Birlashtirish operatsiyasi - bu ikkita kichikroq tartiblangan massivlarni olish va ularni kattaroq qilish uchun birlashtirish jarayoni.
|
| |
