Radix Sort Algorithm

Razryadli saralash (Radix Sort) — bu elementlarni to'g'ridan-to'g'ri o'zaro taqqoslamasdan, ularning raqamlarini razryadlari (xonalari: birliklar, o'nliklar, yuzliklar va h.k.) bo'yicha guruhlab saralovchi algoritm hisoblanadi.

Faraz qilaylik, bizda 8 ta elementdan iborat massiv mavjud. Dastlab biz elementlarni birliklar xonasidagi raqamlari bo'yicha saralaymiz. Keyin o'nliklar xonasi bo'yicha, so'ngra yuzliklar xonasi bo'yicha saralash davom ettiriladi. Bu jarayon eng katta sonning eng yuqori razryadigacha davom etadi.

Dastlabki massiv [121, 432, 564, 23, 1, 45, 788] bo'lsin. Radix sort bo'yicha saralash quyidagi rasmda ko'rsatilgan:

Razryadli saralashning (Radix Sort) ishlash tartibi

[!NOTE] Ushbu mavzuni to'liq tushunish uchun avvalo Sanash orqali saralash (Counting Sort) algoritmi bilan tanishib chiqish tavsiya etiladi, chunki Counting Sort har bir razryadni barqaror saralash uchun oraliq bosqich sifatida qo'llaniladi.

Razryadli saralash qanday ishlaydi?

1-qadam: Maksimal element va xonalar sonini topish

Massivdagi eng katta elementni (max) topamiz. Faraz qilaylik, d — max sonidagi raqamlar (razryadlar) soni bo'lsin.

[121, 432, 564, 23, 1, 45, 788] massivimizda eng katta son — 788. U 3 ta raqamdan iborat (d = 3). Demak, sikl 3 marta (birliklar, o'nliklar va yuzliklar xonalari uchun) bajarilishi kerak.

2-qadam: Birliklar xonasi bo'yicha saralash

Har qanday barqaror saralash algoritmidan (odatda Counting Sort) foydalanib, elementlarni birliklar xonasidagi raqamlar bo'yicha tartiblaymiz:

Birliklar xonasi bo'yicha Counting Sort orqali saralash

3-qadam: O'nliklar xonasi bo'yicha saralash

Endi oldingi qadamda hosil bo'lgan massivni o'nliklar xonasidagi raqamlari bo'yicha saralaymiz:

O'nliklar xonasi bo'yicha saralash

4-qadam: Yuzliklar xonasi bo'yicha saralash

Nihoyat, elementlarni yuzliklar xonasidagi raqamlar bo'yicha tartiblaymiz:

Yuzliklar xonasi bo'yicha saralash yakuni

Eng katta sonning barcha razryadlari ko'rib chiqilgach, massiv to'liq tartiblangan holatga keladi.

Razryadli saralash algoritmi

radixSort(array)
  d <- maximum number of digits in the largest element
  for i <- 1 to d
    sort the elements according to ith place digits using countingSort

Dasturiy namunalar

// Go tilida Radix Sort algoritmi
package main

import "fmt"

func getMax(arr []int) int {
	max := arr[0]
	for _, val := range arr {
		if val > max {
			max = val
		}
	}
	return max
}

// Berilgan xona (exp) bo'yicha Counting Sort
func countingSortForRadix(arr []int, exp int) {
	n := len(arr)
	output := make([]int, n)
	count := make([]int, 10)

	// Har bir raqam sonini hisoblash
	for i := 0; i < n; i++ {
		digit := (arr[i] / exp) % 10
		count[digit]++
	}

	// Kumulyativ yig'indi
	for i := 1; i < 10; i++ {
		count[i] += count[i-1]
	}

	// Barqarorlikni ta'minlash uchun orqadan oldinga joylashtirish
	for i := n - 1; i >= 0; i-- {
		digit := (arr[i] / exp) % 10
		output[count[digit]-1] = arr[i]
		count[digit]--
	}

	// Asosiy massivga ko'chirish
	for i := 0; i < n; i++ {
		arr[i] = output[i]
	}
}

func radixSort(arr []int) {
	max := getMax(arr)

	// exp birliklar (1), o'nliklar (10), yuzliklar (100) va h.k. bo'yicha oshiriladi
	for exp := 1; max/exp > 0; exp *= 10 {
		countingSortForRadix(arr, exp)
	}
}

func main() {
	data := []int{121, 432, 564, 23, 1, 45, 788}
	fmt.Println("Dastlabki massiv:", data)

	radixSort(data)

	fmt.Println("Saralangan massiv:", data)
}

Razryadli saralashning murakkabligi

Vaqt murakkabligi

• Barcha holatlarda (Best, Worst, Average): O(d * (n + k))
  • bu yerda d — eng katta elementdagi xonalar (razryadlar) soni,
  • n — massiv elementlari soni,
  • k — asos / sanoq tizimi (o'nli sanoq tizimida k = 10).

Agar d o'zgarmas doimiy deb olinsa, Radix Sort chiziqli vaqtda — O(n) da ishlaydi.

Xotira murakkabligi

• Xotira murakkabligi O(n + k) ga teng (Counting Sort uchun talab qilinadigan yordamchi massivlar).
• Radix Sort barqaror (stable) hisoblanadi.

Razryadli saralashning qo'llanilishi

• DC3 algoritmi orqali matnlarning suffiks massivlarini (suffix array) yaratishda.
• Katta diapazondagi butun sonlarni tezkor saralashda.