Bit-bit tartibida saralash

Bit-bit tartibida saralash
Ko'pgina saralash dasturlarida fayllardagi yozuvlarni buyurtma qilish uchun ishlatiladigan tugmalar juda murakkab bo'lishi mumkin. Masalan, telefon daftarida yoki kutubxona katalogida ishlatiladigan tugmachalarning qanchalik murakkabligini tasavvur qiling. Ushbu asoratlarning barchasini o'rganilgan saralash usullarining eng muhim xususiyatlaridan ajratish uchun biz 6-9 boblarda deyarli hamma joyda faqat ikkita kalitni taqqoslash va ikkita yozuvni almashtirish operatsiyalaridan foydalanish bilan cheklandik (tugmalar bilan ishlashning barcha tafsilotlarini yashirish bu funktsiyalar) saralash usullari va ilovalari o'rtasidagi mavhum interfeys sifatida. Ushbu bobda biz tartiblash tugmachalari uchun yana bir abstraktsiyani ko'rib chiqamiz. Masalan, har bir bosqichda tugmachalarni to'liq qayta ishlashga hojat qolmaydi: telefon katalogidan qidirishda abonent raqami bilan sahifani topish uchun uning familiyasining faqat birinchi harflarini tekshirish kifoya. Saralash algoritmlarining bir xil samaradorligiga erishish uchun biz tugmachalarni taqqoslashning abstrakt ishidan mavhumlikka o'tamiz, unda tugmachalar sobit o'lchovli qismlar - baytlar ketma-ketligiga bo'linadi. Ikkilik raqamlar bitlar ketma-ketligi, satrlar belgilar ketma-ketligi, o'nli raqamlar raqamlar ketma-ketligi va boshqa ko'plab (hammasi bo'lmasa ham) turdagi kalitlarni xuddi shunday ko'rib chiqish mumkin.

Tugmachalarni yonma-yon ishlashiga asoslangan tartiblash usullari radix sort deb nomlanadi. Ushbu usullar shunchaki tugmachalarni taqqoslamaydi, balki tugmalar qismlarini qayta ishlaydi va taqqoslaydi.

Radixni saralash algoritmlari kalitlarni R (radix) ning har xil qiymatlari uchun asosiy R raqamlari sifatida izohlaydi va bu raqamlarning alohida raqamlari ustida ishlaydi. Masalan, pochtani saralash mashinasi har biri 5 xonali o'nli raqam bilan belgilangan konvertlar to'plamini qayta ishlaganda, bu to'plamni o'nta alohida stakka tarqatadi:

bittasida 0 bilan boshlangan paketlar, ikkinchisida 1 bilan boshlangan paketlar, uchinchisida 2 bilan boshlangan paketlar va hk.

Har bir to'plamni keyingi raqam uchun xuddi shu usuldan foydalangan holda yoki paketda bir nechta sumka bo'lsa, oddiyroq usulda qayta ishlash mumkin. Agar siz endi paketlardan paketlarni 0 dan 9 gacha tartibda va har bir paket ichida bir xil tartibda yig'sangiz, ular buyurtma qilinadi. Ushbu protsedura R = 10 ga teng bo'lgan radix sortidir va kalitlari 5 dan 10 gacha bo'lgan o'nlik raqamlari bo'lgan dasturlarni saralashda foydalidir, masalan, pochta indekslari, telefon raqamlari yoki identifikatsiya raqamlari. Ushbu usul 10.3-bo'limda batafsil muhokama qilinadi.

Turli xil ilovalar uchun turli xil radiuslar yaxshiroq mos keladi.Bu bobda biz butun sonlar yoki satrlar shaklida ifodalangan tugmachalarga e'tibor qaratamiz, ular uchun radiuslarni saralash texnikasi keng qo'llaniladi. Kompyuterlarda ikkilik raqamlar sifatida ifodalangan tamsayılar uchun biz ko'pincha R = 2 bilan yoki 2 ning bir kuchi bilan ishlaymiz, chunki bu tugmachalarni mustaqil qismlarga bo'lishimizga imkon beradi. Belgilar qatorlarini o'z ichiga olgan kalitlar uchun biz radiusni bayt o'lchamiga moslashtirish uchun R = 128 yoki R = 256 dan foydalanamiz. Aslida, bunday to'g'ridan-to'g'ri dasturlardan tashqari, kompyuterda yozilgan deyarli hamma narsani ikkilik raqamlar shaklida ko'rib chiqish mumkin.

Bu boshqa kalit turlarini ishlatadigan ko'plab saralash dasturlarini ikkilik raqamlar sifatida ko'rsatiladigan tugmachalarni buyurtma qiladigan radix sortidan foydalanishga yo'naltirishga imkon beradi.

Radiksni saralash algoritmlari "kalitning i-raqamini ajratib olish" mavhum operatsiyasiga asoslangan. Yaxshiyamki, C ++ operatsion tizimida past darajadagi operatsiyalar mavjud bo'lib, buni amalga oshirish oddiy va samarali bo'ladi. Bu juda muhimdir, chunki ba'zi bir dasturlash tillari (masalan, Paskal), mashinani mustaqil dasturlashni rag'batlantirish orqali ma'lum bir mashinada raqamlarning tasvirlanish uslubiga bog'liq bo'lgan dasturlarni yozishni qasddan qiyinlashtirmoqda. Bunday tillarda ko'pgina kompyuterlar uchun qulay bo'lgan bitli operatsiyalarning ko'p turlarini amalga oshirish qiyin.

Xususan, radiksni saralash ushbu "progressiv" falsafaning qurboniga aylandi. Biroq, C va C ++ yaratuvchilari to'g'ridan-to'g'ri bit operatsiyalari ko'pincha juda foydali ekanligini angladilar va biz radikal tartiblashni amalga oshirishda past darajadagi til vositalaridan foydalanishimiz mumkin.

Yaxshi apparat yordami ham zarur; buni o'z-o'zidan qabul qilib bo'lmaydi. Ba'zi mashinalarda ma'lumotlarning kichik qismlariga kirishning samarali usullari mavjud, ammo ba'zi boshqa turdagi mashinalar ushbu operatsiyalarni bajarilishini sezilarli darajada sekinlashtirishi mumkin. Radiks tartiblash algoritmlari raqamlarni ajratib olish operatsiyalari bo'yicha ifodalash uchun juda sodda bo'lganligi sababli, radix tartiblash algoritmining ishlashini maksimal darajada oshirish vazifasi apparat va dasturiy ta'minot uchun ajoyib kirish bo'lishi mumkin.

(10.1-rasm) Bit-bit tartibida saralash
Ushbu ro'yxatda 0 dan 1 gacha (chapda) jami 99 ta raqamdan iborat 11 ta raqam mavjud bo'lishiga qaramay, ularga faqat 22 ta raqamni (o'ngda) tahlil qilish orqali (o'rtada) buyurtma berish mumkin.

Radiksni saralashga ikkita tubdan farq qiluvchi asosiy yondashuvlar mavjud. Birinchi sinf usullari algoritmlardan iborat bo'lib, ular chapdan o'ngga tugmachalardagi raqamlarni ajrata oladilar, birinchi navbatda eng muhim raqamlar qayta ishlanadi. Ushbu usullarning barchasi birgalikda MSD turlari deb nomlanadi (eng muhim raqamli radius saralash). MSD turlari jozibali, chunki ular saralashni amalga oshirish uchun zarur bo'lgan minimal ma'lumot miqdorini tahlil qiladilar (10.1-rasm).

MSD-ni saralash usullari bu tezkor kortlarni umumlashtirishdir, chunki ular tartiblangan faylni tugmachalarning eng muhim raqamlariga qarab ajratadi va shu usulni hosil bo'lgan pastki fayllarga rekursiv ravishda qo'llaydi. Darhaqiqat, 2 radiusi bilan MSD sortirovkasini amalga oshirish tezkor kortga o'xshaydi. Radiksni saralash usullarining ikkinchi klassi boshqacha printsipni qo'llaydi: ular tugmachalarning raqamlarini o'ngdan chapga ajratib, birinchi navbatda eng kam ahamiyatli raqamlar bilan ishlaydi.

Ushbu usullarning barchasi LSD navlari deb nomlanadi (kamida muhim raqamli radius saralash). LSD-ni saralash biroz qarama-qarshi, chunki protsessorning ba'zi vaqtlari natijalarga ta'sir qila olmaydigan raqamlarni qayta ishlashga sarflanadi, ammo bu muammo osonlikcha hal qilinadi va ushbu muhtaram usul ko'plab saralash dasturlari uchun javob beradi.