OʻZBEKISTON RESPUBLIKASI OLIY VA O‘RTA MAXSUS
TA’LIM VAZIRLIGI
MIRZO ULUG‘BEK NOMIDAGI MILLIY UNIVERSITETININIG
JIZZAX FILIALI
AMALIY MATEMATIKA FAKULTETI
«KOMPYUTER ILMLARI VA DASTURLASHTIRISH» kafedrasi
“ALGORITMLAR VA BERILGANLAR STRUKTURASI”
FANIDAN
MUSTAQIL ISH
Mavzu: Razryadli saralash (Radix sort)
Bajardi: “____ATT________” yoʻnalishi _2_kurs__21-21_ guruh________
talabasi: Qo’zibekov Ahad___________________________________
Tekshirdi: Tojiyev Maruf____________________________________
Jizzax – 2023
14-variant
Mavzu : Razryadli saralash (Radix sort)
Reja:
Radix Sort nima?
Radix Sort qanday ishlaydi?
Radix Sort-dan foydalanishning afzalliklari:
Radix Sort-dan foydalanish cheklovlari:
KIRISH.
Radix sort birinchi marta matematik va faylasuf Charlz Sanders Peirce tomonidan 1887 yilda kiritilgan. U lug'atda so'zlarni saralash usulidan foydalangan. Keyinchalik, 1954 yilda Garold Syuard perfokartalarni saralash texnikasini qo'llagan holda algoritmni ishlab chiqishga hissa qo'shdi.Radix sort tushunchasi qadimgi Hindistonda buddist rohiblar tomonidan kiritilgan Radix sanoq tizimiga asoslangan. Ular arifmetik hisob-kitoblarni amalga oshirish uchun hisoblash taxtasi tizimidan foydalanishadi. Ular to'qqizta raqamni ifodalash uchun 1 dan 9 gacha bo'lgan raqamlardan foydalanishadi va keyin tsiklni takrorlab, tsikl raqamini ko'rsatish uchun har bir raqamning ustiga chiziq qo'yishadi. Bu elementlarni joylashuv qiymatlari asosida tartiblash orqali Radix saralash usuliga o‘xshaydi.O'shandan beri raqamli ma'lumotlarni elementlar o'rtasida taqqoslashga hojat qoldirmasdan samarali saralash uchun Radiks bilan tartiblash kompyuter fanida keng qo'llanila boshlandi. U maʼlumotlarni tahlil qilish, tabiiy tilni qayta ishlash va tasvirni qayta ishlash kabi turli xil ilovalarda qoʻllanilgan.Umuman olganda, vaqt o'tishi bilan Radix sortning joriy etilishi va takomillashtirilishi informatikadagi samarali tartiblash algoritmlarini talab qiladigan ko'plab muammolarni hal qilishga yordam berdi
1.Radix Sort nima?
Razryadli saralash (Radix sort) algoritmi, massivni sonlar ruyxatini saralash uchun ishlatiladi. Bu algoritm, tahrirlovchi jadvallarni ishlashda va boshqa bir nechta muhim amaliyotlarda ham foydalaniladi.Radix sort, har bir raqamga qarab jadvalni saralaydi. Ya'ni, birinchi raqamdan boshlab oxirgi raqamgacha bo'lgan raqamlarni o'z ichiga oladi va har bir raqam uchun "radix"ni yaratadi. Har bir radixda saralangan elementlar, keyingi radikslar bo'yicha qayta tartiblangan holda saqlanadi.Bu algoritmning asosiy qadamalaridan biri, elementlarni ularning oxirgi raqamlariga qarab saralamasdir. Keyin uni ularning oxirgi to'rtliklariga qarab saralamasdan o'tkazish kerak. Jami shu ko'rinishda, algoritm oxirgi raqamlar bo'yicha tahlil qilib, keyingi radikslarga keltirilgan elementlarni saralaydi.Radix sortning avtomatik ravishda tartiblash bilan bog'liq masalalar tug'iladi. Masalan, "10" sonini "2" dan oldinga yozish bilan bog'liq masala mavjud. Bunday holatlarda Radix sort ishga tushirilmaydi. Shuningdek, bu algoritmning saralash jarayoni har doim to'g'ri va to'liq bo'lishi kerak.Radix sort - bu bir xil muhim pozitsiya va qiymatga ega bo'lgan raqamlarni guruhlash orqali butun son kalitlari bilan ma'lumotlarni saralaydigan qiyosiy bo'lmagan butun sonlarni saralash algoritmi. Bu chiziqli vaqtli murakkablik algoritmi boʻlib, katta maʼlumotlar toʻplamlari uchun tez saralash, birlashtirish yoki yigʻma tartiblash kabi taqqoslashga asoslangan saralash algoritmlariga qaraganda tezroq.Algoritm tartiblangan kalitlarning har bir raqamini o'ngdan chapga takrorlash orqali ishlaydi. Har bir iteratsiyada tugmalar o'sha joydagi raqamga qarab tartiblanadi. Ushbu jarayon tugmachalardagi har bir muhim raqam uchun takrorlanadi. Radiksli tartiblash har qanday radiks bazasi bilan ma'lumotlarni saralash uchun amalga oshirilishi mumkin, lekin u odatda ikkilik, o'nlik yoki o'n oltilik raqamlar bilan ishlatiladi.Radix tartiblash O(kn) vaqt murakkabligiga ega, bu erda k - eng katta kalitdagi raqamlar soni va n - tartiblangan kalitlar soni. Chiqish va oraliq massivlarni saqlash uchun qoʻshimcha xotira talab qilinadi va agar tugmalardagi raqamlar soni juda koʻp boʻlsa, uning ishlashi yomonlashishi mumkin.
Cheklovlarga qaramay, radix sort katta maʼlumotlar toʻplamlarini butun sonli kalitlar bilan saralash uchun foydali algoritm boʻlib, u tez-tez informatika va maʼlumotlarni tahlil qilish, tasvirni qayta ishlash va kompyuter grafikasi kabi muhandislik dasturlarida qoʻllaniladi.Radix Sort - bu algoritmdir, haqiqatda, raqamlar kabi belgilangan bir turga ega ma'lumotlarni saralash uchun ishlatiladi. Bu algoritmni boshqa saralash turlari bilan solishtirib ko'rsak, Radix Sort eng yaxshi va tezroq ishlaydigan algoritmlardan biri hisoblanadi.
2.Radix Sort qanday ishlaydi?
Radix Sort qanday ishlaydi?
Radix sortning asosiy o'zgaruvchilari quyidagilardir:
• Sana uzunligi
• Ma'lumot sonini ifodalovchi radix Algoritmnning asosiy qadamari quyidagicha:
1. Ma'lumotlarni tarjima qilish: Ma'lumotlar tarjima qilinishi va ularni saralash uchun foydalanish mumkin bo'lgan formatga o'tkazilishi lozim. Misol uchun, sonlar decimal formatida bo'lsa va 3 raqamli bo'lsa, har bir raqamni o'zi bilan saralash mumkin.
2. Radix bo'yicha olish: Ma'lumotlar radix bo'yicha ajratiladi. Bu ya sana uzunligi yoki ma'lumotlarning maxsus bir xususiyati (masalan, sonlar uchun 10) bo'lishi mumkin.
3. Hech qanday saralamagan holda elementlarni saralash: Bu qadamda biz ma'lumotlarni bitta tartibda birlashtirishni istamaymiz. Istisno holatlarda, bitta radixdan foydalanish yuqori darajadagi har bir radixdan foydalanish bilan ta'minlanadi.
4. Radix bo'yicha saralash: Bu qadamda, ma'lumotlar o'zlarining o'zida saralgan va ularga asoslangan tartibda saraliladi.
5. Qiymatlar bo'yicha saralash: Agar ikki yoki undan ko'p element bir xil qiymatga ega bo'lsa, ularni oddiy tarzda saralamaslik mumkin. Shuning uchun, ularni boshqa bir algoritm orqali saralash kerak.
Radix Sortning afzalliklari:
• O'nlab elementli listalar uchun juda tez ishlashadi.
• Barcha qiymat turlari uchun foydalidir.
• Haqiqiy va samarali algoritmdir.
• Radix Sortning oxirgi qadamida elementlarni boshqa algoritmlar yordamida sanoq nusxalandi mumkin.
Radix Sortning kamchiliklari:
• Algoritmda katta ma'lumotlar uchun xotira ko'pligi zarur.
• Ma'lumotlar to'plamining tarjimasi kerak bo'ladi.
• Ma'lumotlarni ajratish kerak, bu qanchalik muhimligini nazarda tutingizga bog'liq.
Radix Sort - bu tartiblash algoritmi bo'lib, ma'lumotlarni alohida raqamlar yoki raqamlarning tarkibiy qismlarini guruhlash va ularning qiymatiga qarab tartiblash orqali tartiblaydi. U odatda qatorlarni, maʼlumotlar bazalarini va koʻplab komponentlarga ega boʻlgan boshqa maʼlumotlar turlarini saralash uchun ishlatiladi. Algoritm ma'lumotlarni eng muhim raqamga, so'ngra keyingi eng muhim raqamga va shunga o'xshash eng muhim raqamga yetguncha saralash orqali ishlaydi. Bu jarayon maʼlumotlar toʻliq saralanmaguncha takrorlanadi. Radix tartiblash O(nk) vaqt murakkabligiga ega, bu erda n - saralanadigan elementlar soni va k - har qanday elementdagi raqamlarning maksimal soni. Ko'pincha saralanayotgan ma'lumotlar ko'p sonli komponentlarga ega bo'lsa, ularning ishlashini yaxshilash uchun tez saralash yoki birlashtirish kabi boshqa tartiblash algoritmlari bilan birgalikda ishlatiladi.
Umuman olganda, radix sort katta hajmdagi maʼlumotlarni tez va samarali saralash uchun foydali algoritmdir, ayniqsa maʼlumotlar alohida komponentlarga osonlik bilan boʻlinadigan formatda boʻlsa.
Misollar:
Misol uchun, quyidagi sonlarni tartiblashni ko'ramiz:
170, 45, 75, 90, 802, 24, 2, 66
1-qadam: Birinchi xonadagi belgilarga asoslangan holda tartiblash
170, 90, 802, 2, 24, 45, 75, 66
2-qadam: Ikkinchi xonadagi belgilarga asoslangan holda tartiblash
802, 2, 24, 45, 66, 170 ,75 ,90
Natijada eng katta son aniqlovchi birinchi xona bo'lsa ham yana qolgan barcha sonlar uchun ikkinchi xona ustiga ish bajariladi. Bunday jamlanmalar oxiriga kelishadi va natijada amalga oshirilgan tartib bilan yakuniy ro'yxat hosil qilinadi.
Bu erda eng kam ahamiyatli raqamdan boshlanadigan radix tartiblash misoli keltirilgan:
Tartiblanmagan butun sonlar massivini ko'rib chiqing [170, 45, 75, 90, 802, 2, 24, 66]. Birinchi qadam elementlarni ularning qiymati bo'yicha eng kam muhim raqamga, ya'ni birliklar raqamiga qarab tartiblashdir. Saralangan ro'yxat quyidagicha bo'ladi:
[170, 90, 802, 2, 24, 45, 75, 66]Keyingi, algoritm elementlarni qiymatiga qarab keyingi eng muhim raqamga, ya'ni o'nlik raqamiga saralaydi. Saralangan ro'yxat quyidagicha bo'ladi:[802, 2, 24, 45, 66, 170, 75, 90]
Jarayon qolgan raqamlar uchun takrorlanadi, natijada yakuniy tartiblangan ro'yxat paydo bo'ladi:
[2, 24, 45, 66, 75, 90, 170, 802]
Ko'rib turganingizdek, massiv endi radix sort yordamida o'sish tartibida tartiblangan. Radix sortning afzalliklaridan biri shundaki, u turli uzunlikdagi butun sonlarni saralash uchun ishlatilishi mumkin. Misol uchun, yuqoridagi radix tartiblash misolida uchta raqamgacha bo'lgan butun sonlar mavjud. Radiksli tartiblash ikkilik yoki oʻn oltilik kabi turli xil radikallar bilan ham ishlatilishi mumkin. Ikkilik radiksli saralashda saralash elementlarning bitlari asosida amalga oshiriladi, oʻn oltilik radiksli saralashda esa elementlarning oʻn oltilik raqamlariga asoslanadi.
Radix Sort bir qancha afzalliklarga ega, bu esa uni muayyan vaziyatlar uchun foydali tartiblash algoritmiga aylantiradi:
1. U katta ma'lumotlar to'plamlari uchun samarali: Radix Sort chiziqli vaqt murakkabligiga ega O(d(n+k)), ya'ni uning vaqt murakkabligi faqat eng katta sondagi raqamlar soniga proportsionaldir. saralanadigan elementlar va kirish raqamlari diapazoni. Bu raqamlarning kattaroq maʼlumotlar toʻplamini saralashda samarali boʻladi.
2. Bu barqaror tartiblash algoritmi: Radix Sort bir xil kalit qiymatiga ega bo'lgan elementlarning tartibini o'zgartirmaydi, bu xususiyat barqarorlik deb ataladi. Radix Sort-ning bu xususiyati, ayniqsa, bir xil kalit qiymatiga ega bo'lgan elementlarning asl tartibini saqlash muhim bo'lgan bir nechta maydonlarga ega yozuvlar kabi ma'lum turdagi ma'lumotlarni saralashda foydalidir.
3. Radix Sort ma'lum bir bazadagi raqamlarni tartiblash uchun ishlatilishi mumkin: Radix Sort, ayniqsa, ikkilik, sakkizlik yoki o'n oltilik kabi ma'lum bir bazadagi raqamlarni tartiblashda foydalidir. Buning sababi, Radix Sort raqamlarni raqamlari bo'yicha ajratadi, ya'ni undan raqamlarni bir nechta asosda tartiblash uchun foydalanish mumkin.
4. Bu boshqa taqqoslashga asoslangan saralash algoritmlariga qaraganda tezroq boʻlishi mumkin: Raqamlarni saralashda Radix Sort boshqa solishtirishga asoslangan saralash algoritmlariga qaraganda tezroq boʻlishi mumkin, masalan, tezkor saralash yoki muayyan holatlarda birlashtirish. Buning sababi shundaki, u elementlar o'rtasida hech qanday taqqoslashni o'z ichiga olmaydi, faqat elementlarni raqamlariga qarab hisoblash va taqsimlashni o'z ichiga oladi.
Umuman olganda, Radix Sort muayyan vaziyatlar uchun qimmatli algoritmdir. Bu, ayniqsa, raqamlarning katta maʼlumotlar toʻplamini saralashda, raqamlarni maʼlum bazada tartiblashda, bir xil kalit qiymatiga ega boʻlgan elementlar tartibini saqlashda foydalidir va muayyan holatlar uchun taqqoslashga asoslangan tartiblash algoritmlariga qaraganda tezroq boʻlishi mumkin.
Radix Saralash
• Boshqa saralash usullaridan farqli o'laroq, radix saralash
kalitlarning tuzilishini ko'rib chiqadi
• Kalitlar M tayanchda ifodalangan deb faraz qiling
sanoq tizimi (M = radix), ya'ni M = 2 bo'lsa,
kalitlar ikkilik tizimda ifodalanadi
• Saralash dagi bitlarni solishtirish orqali amalga oshiriladi
bir xil pozitsiya
• Alfanumerik kalitlarga kengaytma
torlar
|
