8 mavzu: Murakkab saralash algoritmlari. Amaliy dasturlash Reja

Bitli saralash(Radix sort). Shuningdek, raqamli saralash sifatida tanilgan algoritmdir. Bu saralashning ikki versiyasi mavjud bo‘lib, ular, qandaydir sonlar sistemasida (masalan, binar – ikkilik) sonni ifodalashdan foydalanish fikridan boshqa umumiylikka ega emas.
Birinchi usuli. LSD (least significant digit, kichik muhim son). Har bir sonni binar shaklda ifodalaylik. Algoritmning har bir qadamida sonlarni shunday tartiblaymizki, ular k doimiy bo‘lgan birinchi k * i bitlar bo‘yicha tartiblansin. Bu taʻrifdan shunday xulosa kelib chiqadiki, har bir qadamda elementlarni yangi k bitlar bo‘yicha uzluksiz tartiblash kifoyadir. Shu maqsadda, sanash orqali saralash ideldir (agar muvaffaqiyatlisini doimiy tanlasangiz 2k xotira va vaqt ko‘p kerak emas). Murakkabligi O(n), agar sonlar fiksirlangan kattalikda deb faraz qilsak va aks holda ikki sonni taqqoslash vaqt birligi bo‘yicha bajariladi deb hisoblash mumkin bo‘lmaydi. Amalga oshirish juda oddiy.
8.13-dastur. Saralashni amalga oshirish.
int digit(int n, int k, int N, int M) { return (n >> (N * k) & (M - 1));
}
void _radixsort(int* l, int* r, int N) { int k = (32 + N - 1) / N;
int M = 1 << N; int sz = r - l;
int* b = new int[sz]; int* c = new int[M];
for (int i = 0; i < k; i++) {
for (int j = 0; j < M; j++) c[j] = 0;
for (int* j = l; j < r; j++) c[digit(*j, i, N, M)]++;
for (int j = 1; j < M; j++) c[j] += c[j - 1];
for (int* j = r - 1; j >= l; j--)
b[--c[digit(*j, i, N, M)]] = *j; int cur = 0;
for (int* j = l; j < r; j++)
*j = b[cur++];
}
delete b; delete c;
}
void radixsort(int* l, int* r) {
_radixsort(l, r, 8);
}
Ikkinchi usuli. MSD (most significant digit, eng muhim raqam). Aslida qandaydir blokni saralash algoritmiga o‘xshaydi. Shu blokda teng k bitli sonlar bo‘ladi. Murakkabligi LSD versiyasidagidek. Amalga oshirish blok saralash juda o‘xshaydi, lekin oddiy. Bu LSD versiyasini amalga oshirishdagi belgilangan raqamli vazifasidan foydalanadi.