Counting Sort Algorithm

Sanash orqali saralash (Counting Sort) — bu taqqoslashga asoslanmagan saralash algoritmi bo'lib, u massivdagi har bir noyob elementning necha marta uchrashini (takrorlanish sonini) sanash orqali tartiblaydi. Elementlar soni yordamchi hisoblash massivida saqlanadi va ushbu sonlar asosida har bir elementning yakuniy saralangan massivdagi to'g'ri o'rni aniqlanadi.

Sanash orqali saralash qanday ishlaydi?

1-qadam: Maksimal elementni topish

Berilgan massivdan eng katta elementni (max) aniqlaymiz.

Berilgan dastlabki massiv (Given array)

2-qadam: Sanash massivini yaratish

Uzunligi max + 1 ga teng bo'lgan va barcha elementlari 0 bilan to'ldirilgan count massivini hosil qilamiz. Ushbu massiv har bir qiymatning takrorlanishlar sonini saqlaydi.

0 lar bilan to'ldirilgan hisoblash massivi (Count array)

3-qadam: Har bir elementning uchrashlar sonini yozib borish

Massivdagi har bir elementni ko'rib chiqib, count massivining mos indeksidagi qiymatni 1 taga oshiramiz.

Masalan: agar 3 soni 2 marta uchrasa, count[3] = 2 bo'ladi. Agar 5 soni massivda umuman bo'lmasa, count[5] = 0 bo'lib qoladi.

Har bir elementning takrorlanishlar soni qayd etildi

4-qadam: Kumulyativ yig'indini hisoblash

count massivi elementlarining kumulyativ (to'plangan) yig'indisini hisoblaymiz. Bu har bir element yakuniy saralangan massivda qaysi indeksgacha joylashishi kerakligini ko'rsatadi:

Kumulyativ (jamlangan) sanash massivi (Cumulative count)

5-qadam: Elementlarni chiqish massiviga joylashtirish

Dastlabki massivning oxirgi elementidan boshlab chapga qarab yuramiz. Har bir element uchun count massividagi qiymatni ko'ramiz, elementni chiqish massivining count[element] - 1 indeksiga joylashtiramiz va count[element] qiymatini 1 taga kamaytiramiz:

Sanash orqali saralash (Counting sort yakuni)

Sanash orqali saralash algoritmi

countingSort(array, size)
  max <- find largest element in array
  initialize count array with all zeros
  for j <- 0 to size - 1
    find total count of each unique element and store at count[array[j]]
  for i <- 1 to max
    count[i] <- count[i] + count[i - 1] // Kumulyativ yig'indi
  for j <- size - 1 down to 0
    output[count[array[j]] - 1] <- array[j]
    count[array[j]] <- count[array[j]] - 1
  copy output to array

Dasturiy namunalar

// Go tilida Counting Sort algoritmi
package main

import "fmt"

func countingSort(arr []int) {
	size := len(arr)
	if size == 0 {
		return
	}

	// 1-qadam: max elementni topish
	max := arr[0]
	for _, val := range arr {
		if val > max {
			max = val
		}
	}

	// 2-qadam: count va output massivlarini tayyorlash
	count := make([]int, max+1)
	output := make([]int, size)

	// 3-qadam: Har bir element sonini hisoblash
	for _, val := range arr {
		count[val]++
	}

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

	// 5-qadam: Elementlarni joylashtirish (barqarorlik uchun orqadan oldinga)
	for i := size - 1; i >= 0; i-- {
		output[count[arr[i]]-1] = arr[i]
		count[arr[i]]--
	}

	// Natijani asosiy massivga ko'chirish
	for i := 0; i < size; i++ {
		arr[i] = output[i]
	}
}

func main() {
	data := []int{4, 2, 2, 8, 3, 3, 1}
	fmt.Println("Dastlabki massiv:", data)

	countingSort(data)

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

Sanash orqali saralashning murakkabligi

Vaqt murakkabligi

• Barcha holatlarda (Best, Worst, Average): O(n + k), bu yerda n — massivdagi elementlar soni, k — massivdagi maksimal element (max).
  • Agar k qiymati n ga yaqin yoki undan kichik bo'lsa, algoritm chiziqli vaqtda — O(n) da ishlaydi (bu O(n log n) dan ancha tez!).
  • Agar k juda katta bo'lsa (masalan, n = 5, lekin elementlar orasida 1_000_000 bo'lsa), xotira va vaqt sarfi keskin oshib ketadi.

Xotira murakkabligi

• Xotira murakkabligi O(max) = O(k) bo'lib, count massivining o'lchamiga to'g'ri proporsionaldir.
• Counting Sort barqaror (stable) hisoblanadi.

Sanash orqali saralashning qo'llanilishi

Counting sort quyidagi vaziyatlarda qo'llaniladi:

• Elementlar butun sonlar bo'lib, ularning qiymatlar oralig'i (k) unchalik katta bo'lmaganda.
• Radix Sort (Razryadli saralash) algoritmining ichki yordamchi qadami sifatida (har bir xonadagi raqamlar bo'yicha saralashda).