O’zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini

O’ZBEKISTON RESPUBLIKASI AXBOROT
TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI
RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL–XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
FARG’ONA FILIALI
“ Kompyuter injineringi ”
FAKULTETI

“MA’LUMOTLAR TUZILMASI VA ALGORITMLAR ” FANIDAN

1-Dedline

BAJARDI : DADAXONOVA MUNOJOT

QABUL QILDI: XONTORAYEV SARDOR

MAVZU: CUBE SORT

Kub tartiblash algoritmi (inglizcha: "Cube Sort") bir tartiblash algoritmidir, lekin osiyo mamlakatda keng tarqalgan emas. U mazkur algoritm odatda yangi tizimlarda va standart tartiblash funksiyalaridan foydalanilganda ishlatilmaydi. Bu, muhim nisbatda og'ir hisoblanadi.

Algoritmda asosiy qadam - kublarni bir-biriga solishtirishdir. Har bir kubning ichida tartiblangan elementlardan tashkil topgan bir nechta bo'lgan massiv mavjud bo'ladi. Algoritmning umumiy jarayoni quyidagicha ifodalangan:

1. Barcha elementlarni kublarga bo'lib tushirish.
2. Har bir kubdagi elementlarni o'zaro solishtirish.
3. Har bir kubni o'z ichidagi elementlarni o'zaro solishtirishni davom ettirish.
4. Har bir kubning o'z ichidagi elementlarni solishtirishni yakunlash.

Kub tartiblash algoritmi asosan o'n kvadrat vaqt talab qiladi. Bu sababli, undan foydalanish tavsiya etilmaydi, chunki boshqa, tezroq vaqt talab qiladigan tartiblash algoritmalar mavjud.

Asosiy kub tartiblash algoritmi odatda o'lcham (size) bo'yicha qanday qilib kublarni ajratish lozimligini aniqlash uchun xususiy algoritmalar bilan birgalikda ishlatiladi. Lekin umumiy holatda, yuqorida ko'rsatilgan algoritmning esas tamoyillarini o'z ichiga oladi. Kub sort (quadratic sort) algoritmi, o'n^2 (n kvadrat) vaqt hamda toifali saqlanuvchi joylar (o'n), yoki boshqa so'z bilan ifodalangan holda, o'n to'g'ri o'lchovli elementlar ro'yxatini tartiblash uchun ishlatiladi. Bu algoritm odatda kichik ro'yxatlar uchun yoki ro'yxat avvaldan yuzlab qatnashgan holda juda tez yoziladi. Chunki u o'n^2 tartibda har bir elementni boshqa har bir element bilan solishtiradi. Kub sort, haqiqatan ham o'zgaruvchanlarni tartiblash uchun ishlatiladigan bir tartiblash algoritmi hisoblanadi. Kub sort algoritmi "Qat'iy bo'lish" usuli bilan ifodalangan.

Kub sort qadam-qadam bilan amalga oshadi:

1. **Royxatni ikki qismga bo'lish:** Asosiy qadam, berilgan royxatni ikki teng qismini ajratishdir.

2. **Qismlar bo'yicha tarqatish:** Har bir qismni alohida tartibda saralash amaliyoti qo'lga chiqariladi. Bu tartiblash amaliyoti odatda boshqa tartiblash algoritmiga asoslangan bo'lsa-da, kub sort uchun unikal ravishda amalga oshiriladi.

3. **Birikmalarining biriktirish:** So'ngra, ikkala qismni birlashtirish va yangi qismlarni ajratish jarayoni davom etadi. Bu bosqichda har bir elementni mos katta qismini topib, ularni bir-biriga qo'shadi.

Bu algoritm odatda o'n kvadrat vaqt murakkablikda ishlaydi. Chunki har bir qismlarni tartiblash uchun kub sort bo'yi n bor vaqt talab qiladi, va bir nechta qismlar bir-biriga qo'shish jarayoni ham qaysi tartiblash algoritmidan foydalansa, o'sha algoritm vaqt murakkabligini oshiradi. Shuning uchun, kub sort asosan o'rta hajmdagi royxatlarni tartiblash uchun ishlatiladi.

Bu algoritm odatda juda oddiy va amaliy hisoblanadi, ammo katta ro'yxatlarda ishlovchi vaqt muddati yuqori bo'lishi mumkin. Yuqorida aytib o'tilgan sabablarga ko'ra, kub sort kichik ro'yxatlarda yoki amaliy maqsadlarga mos kelishi mumkin. Aksincha, katta ma'lumotlarda yoki tezlik zarur bo'lgan muammolarda boshqa, o'zaro biriktirilgan algoritmlar, masalan, "quick sort" yoki "merge sort" kabi, ishlatilishi tavsiya etiladi.