Radix sort. Key indeksli sanoq bilan tartiblash

Graph protsessing o’zining eng yuqori cho’qqisi – maxflow/mincut masalasidan keyin tugadi (hozircha). Biz graph’ga Leetcode masalalarini yechish jarayonida yana qaytamiz. Keyingi maqolalarda osonroq mavzular – string va string sort haqida so’z boradi.

Javascriptda har bir string belgi UTF-16 belgilarining qo’llab quvvatlanishi sababli xotiradan 4 baytgacha joy oladi (ammo hamma UTF-16 belgilar ham qo’llab-quvvatlanmaydi, chunki hamma UTF-16 belgilar ham 4 bayt emas). Misol uchun, Blob yordamida biz string’ning hajmini bila olamiz.

console.info(
  new Blob(['😂']).size,               // 4
  new Blob(['👍']).size,               // 4
  new Blob(['😂👍']).size,             // 8
  new Blob(['I\'m a string']).size,   // 12, har bir belgi uchun 1 bayt
);

Amaliyotda UTF-16 belgilari ko’p ham ishlatilmasligi bois, misollarda biz oddiy ASCII belgilar bilan cheklanamiz.

Radix

Radix (radiks) – biror alifbodagi (yoki tizimdagi) unikal belgilar soniga teng. Masalan, ikkilik sanoq tizimi uchun R = 2 (0 1); 16lik sanoq tizimida R = 16 (0123456789ABCDEF); ASCII uchun R = 128; va hokazo.

Biz masala yechish jarayonida radix sonini stringdagi unikal qiymatlarga ko’ra aniqlab olishimiz ham mumkin, biz uchun radix soni dunyo standartlari bo’yicha bo’lishi shartmas.

Key indeksli sanoq

Key indeksli sanoq (bundan keyin Key indexed counting, KIC) bizga unikal bo’lmagan key’ga ega ro’yhatlarni tartiblash uchun asqotishi bois, dastlab biz tartiblash algoritmlari haqida eslab olamiz.

Samarador tartiblash algoritmlari – Mergesort, Quicksort va Heapsort da time complexity O(N lg N) dan katta edi, ya’ni tartiblash uchun N elementlarni N lg N marta taqqoslash talab etilardi.

Amaliyotda kichik integer key’li, ko’pincha key’lari unikal bo’lmagan ro’yhatlar uchraydi. Masalan, ro’yhatdagi so’zlarni bosh harfi bo’yicha tartiblash yoki telefon raqamlarini joy kodi bo’yicha tartiblash. Javascriptda odatiy Array.sort() funksiyasi bilan tartiblashdan qutilish mumkin, bu oson yo’l, to’g’ri. Ammo .sort() funksiyasi ham Quicksort/Mergesort algoritmi asosida ishlaydi.

Bizga qo’yiladigan savol – string key’li ro’yhatni tartiblash uchun biz yaxshiroq natijaga erishishimiz mumkinmi?

Bizda quyidagi ro’yhat bor:

Name	Section
Anderson	2
Brown	3
Davis	3
Garcia	4
Harris	1
Jackson	3
Johnson	4
Jones	3
Martin	1
Martines	2
Miller	2
Moore	1
Robinson	2
Smith	4
Taylor	3
Thomas	4
Thompson	4
White	2
Williams	3
Wilson	4

Uni section bo’yicha tartiblash kerak. Bunda section’ga bog’langan ismlar joylashuvi ham o’zgaradi. Key’lar unikalmas, va ular kichik integer sonlardan tashkil topgan. Shu faktga ko’ra, key’larni array indeksi deb olib, tezkor tartiblashni amalga oshirish mumkin.

Key’lar ro’yhatini olamiz:

const sections = [ 
  2, 3, 3, 4, 1, 3, 4, 
  3, 1, 2, 2, 1, 2, 4, 
  3, 4, 4, 2, 3, 4 
]

Key’larning sections[] da necha marta qaytarilayotganini aniqlab olamiz.

const count = []
const count = Array(R + 1).fill(0) // R - radix, unikal belgilar soni

for (let i = 0; i < sections.length; i++) {
  count[sections[i]]++
}

Shunda bizda count[]

[ 0, 3, 5, 6, 6 ]

1 key 3 marta qaytarilayotgan ekan, 2 5 marta, 3 6 marta, 4 ham 6 marta. Endi qaytarilishlarni ketma-ketlikka almashtiramiz.

for (let i = 0; i < R; i++) {
  count[i + 1] += count[i]
}

count[] endi

[ 0, 3, 8, 14, 20 ]

bu ro’yhat sections’dagi key’larning umumiy ro’yhatda qaysi qatordan boshlanishini bildiradi. Faqat endi section 1 count[0] dan boshlab hisoblanadi. sections’ni tartiblab yangi aux[] array’ga yig’amiz.

for (let i = 0; i < sections.length; i++) { 
  aux[count[sections[i] - 1]++] = sections[i] 
}

aux[] qiymati:

[
  1, 1, 1, 2, 2, 2, 2,
  2, 3, 3, 3, 3, 3, 3,
  4, 4, 4, 4, 4, 4
]

Yuqoridagi siklni kengaytirib, ro’yhatni tartiblaymiz.

for (let i = 0; i < sections.length; i++) { 
  const newPosition = count[sections[i] - 1]++ 
  auxNames[newPosition] = names[i] 
  aux[newPosition] = sections[i]
}

Bizdagi ro’yhat tartiblandi:

Name	Section
Anderson	1
Brown	1
Davis	1
Garcia	2
Harris	2
Jackson	2
Johnson	2
Jones	2
Martin	3
Martines	3
Miller	3
Moore	3
Robinson	3
Smith	3
Taylor	4
Thomas	4
Thompson	4
White	4
Williams	4
Wilson	4

To’liq kod bilan tanishib chiqishingiz mumkin:

P.s. Key string bo’lsa, hisoblashlardan oldin str.charCodeAt() funksiyasi bilan string belgini indeksga o’zgartirish kerak bo’ladi.