Bit-bit tartibida saralash

Ikkilik tezkor saralash

Faraz qilaylik, biz fayldagi yozuvlarni tartibini o'zgartirib, bit 0 dan boshlanadigan barcha tugmachalar bit 1 dan boshlanadigan tugmachalardan oldin joylashtiriladi. Keyin biz tezkor tortish variantlaridan biri bo'lgan rekursiv tartiblash usulidan foydalanishimiz mumkin ("Tez saralash" ga qarang). : faylni shu tarzda bo'linib, so'ngra ikkala subfaylni mustaqil ravishda saralash. Faylni tartibini o'zgartirish uchun biz uni chapdan, bit 1dan boshlanadigan tugmachani topgunimizcha ko'rib chiqamiz, keyin 0 bitdan boshlanadigan tugmani topgunimizcha o'ng tomonga qarab, ularni almashtiramiz va bu jarayonni ko'rsatkichlarga qadar davom etamiz kesib o'tish.

10.1-dastur ushbu usulning to'liq bajarilishini ko'rsatadi. Unda ishlatiladigan bo'linish jarayoni, asosan, 7.2-dastur bilan bir xil, faqat markaziy element sifatida faqat 2b raqami ishlatiladi, fayldan ba'zi kalitlar emas. Faylda 2b raqami bo'lmasligi mumkinligi sababli, bo'linish jarayonida kamida bitta element yakuniy holatiga tushishiga kafolat yo'q. Ushbu algoritm odatdagi tezkor kontseptsiyadan farq qiladi, chunki 1 bit kichikroq tugmachalar uchun rekursiv qo'ng'iroqlar amalga oshiriladi.

Ushbu farq algoritm samaradorligiga sezilarli ta'sir qiladi. Masalan, N elementli faylning degenerativ bo'linishi topilsa, N hajmdagi subfayl uchun rekursiv chaqiruv qilinadi, lekin uzunligi 1 bit kam bo'lgan tugmalar uchun. Shuning uchun bunday qo'ng'iroqlar soni kalitdagi raqamlar soni bilan cheklanadi. Va faylda bo'lmagan markaziy elementlardan ketma-ket foydalanish odatdagi tezkorlikni cheksiz rekursiv tsiklga kiritishi mumkin.

Dastur 10.1. Ikkilik tezkor

Ushbu dastur faylni tugmachalarning etakchi bitlari bilan ajratadi va natijada olingan pastki fayllarni rekursiv ravishda saralaydi. D o'zgaruvchisi tahlil qilingan bitning pozitsiyasini o'z ichiga oladi, 0 dan boshlab (chapda). J ga tenglashganda bo'linish tugaydi, shundan so'ng a [i] ning o'ng tomonidagi barcha elementlar d-chi pozitsiyada 1 ga, a [i] ning chap tomonidagi barcha elementlar d-chi pozitsiyada 0 ga ega. A [i] elementi d-chi pozitsiyada 1 ni o'z ichiga oladi, faqat faylning barcha tugmachalari d-chi pozitsiyada nollardan iborat. Bunday holda, qo'shimcha tekshiruv bo'linish davridan so'ng darhol kiritiladi.

template

void quicksortB(Item a[], int l, int r, int d)

{ int i = l, j = r;

if (r <= l || d > bitsword) return;

while (j != i)

{ while (digit(a[i], d) == 0 && (i < j)) i++;

while (digit(a[j], d) == 1 && (j > i)) j--;

exch(a[i], a[j]);

}

if (digit(a[r], d) == 0) j++;

quicksortB(a, l, j-1, d+1);

quicksortB(a, j, r, d+1);

}

template

void sort(Item a[], int l, int r)

{ quicksortB(a, l, r, 0); }

Standart tezkor kortda bo'lgani kabi, ichki tsiklni amalga oshirishning turli usullari mavjud. 10.1 dasturida indeks qiymatlari kesib o'tganligini tekshirish ikkala ichki tsiklga kiritilgan. Bunday tekshirish i = j bo'lganda qo'shimcha almashinuvga olib keladi; 7.2-dasturda bo'lgani kabi, bu tanaffus bayonoti bilan oldini olish mumkin, ammo u erda a [i] elementining o'zi bilan almashishi juda zararsizdir. Yana bir usul - signalizatsiya kalitidan foydalanish.

Shakl. 10.2-rasmda rasm bilan taqqoslanishi mumkin bo'lgan kichik faylda 10.1 dasturining bajarilishi ko'rsatilgan. 7.1 tez saralash uchun. Ushbu rasm ma'lumotlarning qanday ko'chirilishini ko'rsatadi, ammo nima uchun ba'zi harakatlar amalga oshirilishini tushuntirmaydi - bu tugmachalarning ikkilik ko'rinishiga bog'liq. Ushbu misolning batafsil tasviri shakl. 10.3. Bu erda harflar oddiy 5-bitli kod bilan kodlangan deb hisoblanadi, unda alfavitning i-harfi i sonining ikkilik tasviri bilan ifodalanadi. Ushbu kodlash ko'proq belgilarni (katta va kichik harflar, raqamlar va maxsus belgilar) ko'rsatish uchun ko'proq bitlardan (7, 8 yoki hatto 16) foydalanadigan haqiqiy belgilar kodlashlarining soddalashtirilgan versiyasidir.

10.2. Ikkilik quicksort misoli

Eng muhim buyurtmani buzish hali hech bo'lmaganda bitta qiymat o'z o'rnini egallashiga kafolat bermaydi; faqat eng muhim bitdagi 0 ga ega bo'lgan barcha tugmachalar, eng muhim bitdagi 1-lardan oldin bo'lishini ta'minlaydi. Siz ushbu diagrammani shakl bilan taqqoslashingiz mumkin. 7.1 quicksort uchun, garchi tugmalar ikkilikda ifodalanmasa, bo'limlarning printsipi umuman tushunarsizdir. Shakl. 10.3-rasm 10.3 qaysi pozitsiyalar bo'linishini aniqlaydigan barcha ma'lumotlarni beradi.

Tasodifiy bitlarning to'liq so'zli tugmachalari uchun 10.1 so'zning chap qismidan boshlanishi kerak, ya'ni. nol. Umuman olganda, boshlang'ich bit to'g'ridan-to'g'ri dasturga, mashina so'zidagi bitlar soniga va butun sonlarning (shu jumladan, manfiy) ichki ko'rinishiga bog'liq. Shakldan bitta harfli 5-bitli tugmalar uchun. 10.2 va rasm. 10.3 32-bitli mashinada boshlanish 27-bit bo'lishi kerak.

Ushbu misol, ikkilik tezkor kortni real hayot sharoitida ishlatishda yuzaga kelishi mumkin bo'lgan muammoni ko'rsatadi: degenerativ bo'limlarga duch kelish odatiy holdir (barcha tugmalar bo'lim uchun bit qiymatiga teng bo'lganda). Biz ko'rib chiqqan misollarda bo'lgani kabi kichik raqamlarni (etakchi nolga ega) saralash g'ayrioddiy emas.

Belgilar tugmachalari uchun ham xuddi shunday muammo yuzaga keladi: aytaylik, har biri standart 8-bitli kodlashda ko'rsatilgan to'rtta belgini birlashtirib 32-bitli kalitlarni yaratamiz. Keyin har bir belgining boshlang'ich pozitsiyasida nasli bo'linishlar paydo bo'lishi ehtimoldan yiroq emas, chunki, masalan, barcha kichik harflar bir xil bitlardan boshlanadi. Ushbu muammo ko'pincha kodlangan ma'lumotlarni saralashda uchraydi; shunga o'xshash muammolar radiks sortining boshqa turlari bilan bog'liq.

10.3. Ikkilik tezkor korpusning misoli (tugmachalarni bitikli ko'rsatish bilan)

Ushbu diagramma rasmga asoslangan. 10.2, faqat shu erda kalit qiymatlar ikki martalik tasvirda va sata jadvali mustaqil subfayllarni saralashni parallel ravishda bajarilgandek ko'rsatish uchun va qulaylik uchun berilgan. Birinchi bosqichda fayl subfaylga bo'linadi, uning barcha tugmachalari 0 bilan boshlanadi va pastki fayllar, ularning hammasi 1 dan boshlanadi. Keyin birinchi pastki fayl barcha kalitlari 00 dan boshlanadigan va barcha tugmachalari 01 dan boshlanadigan pastki faylga bo'linadi; bundan qat'i nazar, o'zboshimchalik bilan bir vaqtning o'zida ikkinchi pastki fayl subfaylga bo'linadi, uning barcha tugmachalari 10 dan boshlanadi va barcha tugmachalari 11 dan boshlanadi. ushbu misoldagi takroriy kalitlar) yoki pastki fayllar hajmi teng bo'lganda.

Bir marta tugmachani boshqalar tomonidan chap tomondagi bitlar bilan farqlash mumkin bo'lsa, endi boshqa bitlar tahlil qilinmaydi. Ushbu xususiyat ba'zi holatlarda afzallik, boshqalarda bu kamchilikdir. Agar kalitlar chindan ham tasodifiy bitlar to'plami bo'lsa, unda har bir tugmachada faqat lg N bitlar tahlil qilinadi, bu odatda tugmachalar sonidan ancha kam.

Ushbu fakt 10.6-bo'limda, shuningdek 10.5-mashqda va shakl. 10.1. Masalan, 1000 ta yozuvdan iborat faylni tasodifiy tugmachalar bilan saralash uchun har bir tugmachaning 10 yoki 11 bitini ajratish kerak bo'lishi mumkin (hatto tugmalar, masalan, 64 bitli bo'lsa ham). Ammo bir xil kalitlar uchun barcha bitlar tekshiriladi.

Bitsorting ko'plab uzun takrorlanadigan kalitlarga ega fayllarda yaxshi ishlamaydi. Ikkilik quicksort va standart usul etarli darajada tez ishlaydi, agar tartiblash uchun kalitlar to'liq tasodifiy bitlardan iborat bo'lsa (ular orasidagi farq asosan bit ajratib olish va taqqoslash operatsiyalari narxidagi farqdan iborat), ammo standart tezkor algoritmga moslashish osonroq tasodifiy bo'lmagan kalit ketma-ketliklarini qayta ishlash va uch tomonlama tezkor kontsorts takrorlanadigan kalitlar ustun bo'lgan holatlar uchun juda mos keladi.

Quicksort holatida bo'lgani kabi, bo'limning tuzilishini ikkilik daraxt shaklida tasvirlash qulay (10.4-rasmda bo'lgani kabi): daraxtning ildizi saralanayotgan faylga, uning ikkita kichik daraxtlari subfayllarga to'g'ri keladi. bo'linishdan keyin. Standart quicksort holatida, yozuvlarning hech bo'lmaganda bittasi oxirgi holatiga bo'linishi ma'lum, shuning uchun bu tugma ildiz tuguniga joylashtirilgan.