Bucket Sort Algorithm

Savatli saralash (Bucket Sort) — bu saralanmagan massiv elementlarini savatlar (buckets) deb ataluvchi bir nechta oraliq guruhlarga ajratib saralovchi algoritm hisoblanadi. Har bir savatdagi elementlar alohida boshqa mos saralash algoritmi (masalan, Insertion sort yoki Quicksort) yordamida yoki ushbu chelak algoritmini rekursiv qo'llash orqali tartiblanadi.

Yakunda esa barcha saralangan savatlar ketma-ket birlashtirilib, umumiy saralangan massiv hosil qilinadi.

Scatter-Gather Approach

Tarqatish va yig'ish yondashuvi:

Bucket Sort jarayonini tarqatish va yig'ish (scatter-gather) tamoyili sifatida tushunish mumkin:

1. Tarqatish (Scatter): Elementlar dastlab o'z qiymatiga mos savatlarga taqsimlanadi.
2. Saralash (Sort): Har bir savat ichidagi elementlar alohida saralanadi.
3. Yig'ish (Gather): Barcha savatlardagi tartiblangan elementlar tartib bilan birlashtiriladi.

Savatli saralashning (Bucket Sort) umumiy sxemasi

Savatli saralash qanday ishlaydi?

1-qadam: Savatlarni tayyorlash

Faraz qilaylik, bizga haqiqiy sonlardan iborat quyidagi massiv berilgan:

Kiruvchi massiv (Input array)

O'lchami 10 ga teng bo'lgan massiv yaratamiz. Ushbu massivning har bir o'rni elementlarni saqlash uchun alohida savat vazifasini o'taydi:

Har bir pozitsiyasi bitta savat bo'lgan massiv

2-qadam: Elementlarni savatlarga taqsimlash

Elementlar savatning tegishli diapazoniga qarab joylashtiriladi. Masalan, bizda har bir savat 0 dan 1, 1 dan 2 gacha bo'lgan intervallarga ega bo'lsin.

Aytaylik, 0.23 soni olindi. U massiv o'lchamiga (size = 10) ko'paytiriladi: 0.23 * 10 = 2.3. So'ngra pastki butun qismi olinadi (floor(2.3) = 2). Shunday qilib, 0.23 soni 2-savatga joylashtiriladi:

Elementlarni savatlarga joylashtirish

Xuddi shunday, 0.25 ham 2-savatga tushadi. Barcha elementlar o'z savatlariga taqsimlanadi:

Barcha elementlar savatlarga joylashtirildi

3-qadam: Har bir savatni saralash

Har bir savatdagi elementlar alohida saralash algoritmi (odatda Insertion sort yoki tezkor ichki saralash) orqali tartiblanadi:

Har bir savat ichidagi elementlarni saralash

4-qadam: Savatlardan elementlarni yig'ib olish

Har bir savat bo'ylab ketma-ket yurib, tartiblangan elementlar asl massivga birma-bir ko'chiriladi:

Har bir savatdan elementlarni ketma-ket yig'ib olish va yakuniy saralangan massiv

Savatli saralash algoritmi

bucketSort(array)
  create N buckets
  for each element in array
    index <- floor(element * N)
    insert element into bucket[index]
  for each bucket
    sort(bucket)
  concatenate all sorted buckets into array

Dasturiy namunalar

// Go tilida Bucket Sort algoritmi
package main

import (
	"fmt"
	"sort"
)

func bucketSort(arr []float64) {
	n := len(arr)
	if n <= 0 {
		return
	}

	// 1-qadam: n ta bo'sh savat yaratish
	buckets := make([][]float64, n)

	// 2-qadam: Elementlarni savatlarga taqsimlash
	for _, val := range arr {
		bucketIndex := int(val * float64(n))
		if bucketIndex >= n {
			bucketIndex = n - 1
		}
		buckets[bucketIndex] = append(buckets[bucketIndex], val)
	}

	// 3-qadam: Har bir savatni alohida saralash
	for i := 0; i < n; i++ {
		sort.Float64s(buckets[i])
	}

	// 4-qadam: Barcha savatlarni birlashtirish
	index := 0
	for i := 0; i < n; i++ {
		for _, val := range buckets[i] {
			arr[index] = val
			index++
		}
	}
}

func main() {
	data := []float64{0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51}
	fmt.Println("Dastlabki massiv:", data)

	bucketSort(data)

	fmt.Println("Saralangan massiv:")
	for _, val := range data {
		fmt.Printf("%.2f ", val)
	}
	fmt.Println()
}

Savatli saralashning murakkabligi

Vaqt murakkabligi

• Eng yaxshi holat (Best Case): O(n + k) — agar elementlar savatlar bo'yicha bir tekis taqsimlangan bo'lsa.
• O'rtacha holat (Average Case): O(n) — elementlar bir maromda tasodifiy taqsimlanganda.
• Eng yomon holat (Worst Case): O(n^2) — agar barcha elementlar bitta umumiy savatga tushib qolsa va ular ustida Insertion Sort ishlatilsa.

Xotira murakkabligi

• Xotira murakkabligi O(n + k) ga teng bo'lib, n ta element va k ta savat uchun qo'shimcha xotira talab etiladi.

Savatli saralashning qo'llanilishi

Bucket sort quyidagi holatlarda ishlatiladi:

• Elementlar suzuvchi nuqtali (kasrli) sonlar bo'lib, ma'lum bir oraliqda (masalan, 0 dan 1 gacha) bir tekis taqsimlanganda.
• Ma'lumotlar oqimini parallel ravishda bir nechta protsessor yoki oqimlarda taqsimlab saralashda.