โปรแกรม C++ อัลกอริทึม Bucket Sort

Bucket Sort

ในเทคนิคการจัดเรียงแบบ Bucket Sort ข้อมูลจะถูกกระจายไปยังชุดของถัง (buckets) แต่ละถังสามารถเก็บข้อมูลประเภทเดียวกันได้ หลังจากกระจายแล้ว แต่ละถังจะถูกจัดเรียงโดยใช้อัลกอริทึมจัดเรียงอีกตัวหนึ่ง หลังจากนั้น รวบรวมองค์ประกอบทั้งหมดเข้าสู่รายการหลักเพื่อให้ได้รูปแบบที่จัดเรียงแล้ว

ความซับซ้อนของ Bucket Sort

• Time Complexity: O(n + k) สำหรับกรณีดีที่สุดและเฉลี่ย และ O(n²) สำหรับกรณีแย่ที่สุด

• Space Complexity: O(nk) สำหรับกรณีแย่ที่สุด

Input - รายการข้อมูลที่ไม่ได้จัดเรียง: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Output - Array after Sorting: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79

อัลกอริทึม

bucketSort(array, size)

Input: อาร์เรย์ข้อมูล, และจำนวนรวมในอาร์เรย์

Output: อาร์เรย์ที่จัดเรียงแล้ว

เริ่มต้น
  for i := 0 ถึง size-1
    ใส่ array[i] ลงในถังดัชนี (size * array[i])
  for i := 0 ถึง size-1
    จัดเรียง bucket[i]
  for i := 0 ถึง size -1
    รวบรวมไอเท็มของ bucket[i] และใส่ใน array
สิ้นสุด

โค้ดตัวอย่าง

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void display(float *array, int size) {
    for(int i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void bucketSort(float *array, int size) {
    vector<float> bucket[size];
    for(int i = 0; i < size; i++) {
        bucket[int(size*array[i])].push_back(array[i]);
    }
    for(int i = 0; i < size; i++) {
        sort(bucket[i].begin(), bucket[i].end());
    }
    int index = 0;
    for(int i = 0; i < size; i++) {
        while(!bucket[i].empty()) {
            array[index++] = *(bucket[i].begin());
            bucket[i].erase(bucket[i].begin());
        }
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    float arr[n];
    cout << "Enter elements:" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Array before Sorting: ";
    display(arr, n);
    bucketSort(arr, n);
    cout << "Array after Sorting: ";
    display(arr, n);
}

ผลลัพธ์ตัวอย่าง

Enter the number of elements: 10
Enter elements: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Array before Sorting: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01 0.69
Array after Sorting: 0.01 0.22 0.25 0.29 0.36 0.41 0.45 0.58 0.69 0.79