Əsas məzmuna keçin

Bucket Sort

Bucket Sort, elementləri müxtəlif "bucket" (vedrə) lərə paylaşdıraraq sıralayan bir alqoritmdir. Hər bir bucket daxilində elementlər ayrı-ayrılıqda sıralanır və sonra bütün bucket-lər birləşdirilir.

Bucket Sort-un Əsas Xüsusiyyətləri​

  • Paylaşdırma əsaslı: Elementləri müxtəlif bucket-lərə paylaşdırır
  • Hybrid yanaşma: Hər bucket daxilində başqa sıralama alqoritmi istifadə edir
  • Məhdud məlumat: Uniform paylanmış məlumatlar üçün ən effektivdir
  • Parallelləşmə: Bucket-lər paralel şəkildə sıralana bilər

Bucket Sort-un İşləmə Prinsipi​

  1. Bucket-ləri yarad: n sayda boş bucket yarad
  2. Elementləri paylaş: Hər elementi uyğun bucket-ə yerləşdir
  3. Hər bucket-i sırala: Ayrı-ayrılıqda hər bucket-i sırala
  4. Birləşdir: Bütün bucket-ləri ardıcıl birləşdir
  5. Nəticəni qaytar: Sıralanmış massivi qaytar

Bucket Sort-un Java-da İmplementasiyası​

Koda bax
import java.util.*;

public class BucketSort {
    
    // Float massivi üçün bucket sort
    public static void bucketSort(float[] arr) {
        if (arr.length <= 1) return;
        
        int n = arr.length;
        
        // Bucket-ləri yarad
        List<List<Float>> buckets = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            buckets.add(new ArrayList<>());
        }
        
        // Elementləri bucket-lərə paylaş
        for (int i = 0; i < n; i++) {
            int bucketIndex = (int) (n * arr[i]);
            // Boundary check
            if (bucketIndex >= n) bucketIndex = n - 1;
            buckets.get(bucketIndex).add(arr[i]);
        }
        
        // Hər bucket-i ayrı-ayrılıqda sırala
        for (int i = 0; i < n; i++) {
            Collections.sort(buckets.get(i));
        }
        
        // Bucket-ləri birləşdir
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (float value : buckets.get(i)) {
                arr[index++] = value;
            }
        }
    }
    
    // Integer massivi üçün bucket sort
    public static void bucketSortInteger(int[] arr) {
        if (arr.length <= 1) return;
        
        // Min və max dəyərləri tap
        int min = arr[0], max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min) min = arr[i];
            if (arr[i] > max) max = arr[i];
        }
        
        // Bucket sayını hesabla
        int bucketCount = arr.length;
        int range = max - min + 1;
        
        // Bucket-ləri yarad
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        
        // Elementləri bucket-lərə paylaş
        for (int i = 0; i < arr.length; i++) {
            int bucketIndex = (arr[i] - min) * bucketCount / range;
            if (bucketIndex >= bucketCount) bucketIndex = bucketCount - 1;
            buckets.get(bucketIndex).add(arr[i]);
        }
        
        // Hər bucket-i sırala
        for (int i = 0; i < bucketCount; i++) {
            Collections.sort(buckets.get(i));
        }
        
        // Bucket-ləri birləşdir
        int index = 0;
        for (int i = 0; i < bucketCount; i++) {
            for (int value : buckets.get(i)) {
                arr[index++] = value;
            }
        }
    }
    
    // String massivi üçün bucket sort (uzunluq əsasında)
    public static void bucketSortStrings(String[] arr) {
        if (arr.length <= 1) return;
        
        // Ən uzun string-in uzunluğunu tap
        int maxLength = 0;
        for (String str : arr) {
            if (str.length() > maxLength) {
                maxLength = str.length();
            }
        }
        
        // Bucket-ləri yarad (uzunluq əsasında)
        List<List<String>> buckets = new ArrayList<>();
        for (int i = 0; i <= maxLength; i++) {
            buckets.add(new ArrayList<>());
        }
        
        // String-ləri uzunluq əsasında bucket-lərə paylaş
        for (String str : arr) {
            buckets.get(str.length()).add(str);
        }
        
        // Hər bucket-i sırala
        for (List<String> bucket : buckets) {
            Collections.sort(bucket);
        }
        
        // Bucket-ləri birləşdir
        int index = 0;
        for (List<String> bucket : buckets) {
            for (String str : bucket) {
                arr[index++] = str;
            }
        }
    }
    
    // Generic bucket sort implementasiyası
    public static <T extends Comparable<T>> void genericBucketSort(
            T[] arr, BucketIndexCalculator<T> calculator) {
        if (arr.length <= 1) return;
        
        int bucketCount = arr.length;
        
        // Bucket-ləri yarad
        List<List<T>> buckets = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        
        // Elementləri bucket-lərə paylaş
        for (T element : arr) {
            int bucketIndex = calculator.getBucketIndex(element, bucketCount);
            if (bucketIndex >= bucketCount) bucketIndex = bucketCount - 1;
            if (bucketIndex < 0) bucketIndex = 0;
            buckets.get(bucketIndex).add(element);
        }
        
        // Hər bucket-i sırala
        for (List<T> bucket : buckets) {
            Collections.sort(bucket);
        }
        
        // Bucket-ləri birləşdir
        int index = 0;
        for (List<T> bucket : buckets) {
            for (T element : bucket) {
                arr[index++] = element;
            }
        }
    }
    
    // Bucket indeks hesablamaq üçün interfeys
    public interface BucketIndexCalculator<T> {
        int getBucketIndex(T element, int bucketCount);
    }
    
    // Test
    public static void main(String[] args) {
        // Float massivi üçün test
        float[] floatArr = {0.78f, 0.17f, 0.39f, 0.26f, 0.72f, 0.94f, 0.21f, 0.12f, 0.23f, 0.68f};
        
        System.out.println("Original float array:");
        printFloatArray(floatArr);
        
        bucketSort(floatArr);
        
        System.out.println("\nSorted float array:");
        printFloatArray(floatArr);
        
        // Integer massivi üçün test
        int[] intArr = {42, 32, 33, 52, 37, 47, 51};
        
        System.out.println("\nOriginal integer array:");
        printIntArray(intArr);
        
        bucketSortInteger(intArr);
        
        System.out.println("\nSorted integer array:");
        printIntArray(intArr);
        
        // String massivi üçün test
        String[] strArr = {"apple", "pie", "washington", "book", "java", "a", "to"};
        
        System.out.println("\nOriginal string array:");
        printStringArray(strArr);
        
        bucketSortStrings(strArr);
        
        System.out.println("\nSorted string array (by length):");
        printStringArray(strArr);
    }
    
    // Float massivini çap etmək üçün köməkçi metod
    private static void printFloatArray(float[] arr) {
        for (float f : arr) {
            System.out.printf("%.2f ", f);
        }
        System.out.println();
    }
    
    // Integer massivini çap etmək üçün köməkçi metod
    private static void printIntArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    
    // String massivini çap etmək üçün köməkçi metod
    private static void printStringArray(String[] arr) {
        for (String str : arr) {
            System.out.print(str + " ");
        }
        System.out.println();
    }
}

Zaman və Yaddaş Mürəkkəbliyi​

  • Zaman Mürəkkəbliyi:
    • Ən yaxşı hal: O(n + k) - uniform paylanma
    • Orta hal: O(n + n²/k + k) - k: bucket sayı
    • Ən pis hal: O(n²) - bütün elementlər eyni bucket-də
  • Yaddaş Mürəkkəbliyi: O(n + k), bucket-lər üçün əlavə yaddaş

Bucket Sort-un Üstünlükləri və Çatışmazlıqları​

Üstünlüklər​

  • Uniform paylanmış məlumatlar üçün çox effektivdir
  • Parallelləşdirmə imkanı var
  • Stabil implementasiya mümkündür
  • Müxtəlif məlumat növləri üçün adaptasiya oluna bilər
  • Average case-də O(n) performans əldə etmək mümkündür

Çatışmazlıqları​

  • Məlumatın paylanması haqqında əvvəlcədən məlumat tələb edir
  • Pis paylanmış məlumatlar üçün effektiv deyil
  • Əlavə yaddaş tələb edir
  • Bucket sayının düzgün seçilməsi mühümdür
  • Floating point ədədlər üçün precision məsələləri ola bilər