ประเภทถัง

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

ความซับซ้อนของเทคนิคการจัดเรียงถัง

• ความซับซ้อนของเวลา:O(n + k) สำหรับกรณีที่ดีที่สุดและกรณีเฉลี่ย และ O(n^2) สำหรับกรณีที่เลวร้ายที่สุด

• Space Complexity:O(nk) สำหรับกรณีที่เลวร้ายที่สุด

อินพุตและเอาต์พุต

Input:
A list of unsorted data: 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
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)

ป้อนข้อมูล - อาร์เรย์ของข้อมูลและจำนวนทั้งหมดในอาร์เรย์

ผลลัพธ์ − อาร์เรย์ที่เรียงลำดับ

Begin
   for i := 0 to size-1 do
      insert array[i] into the bucket index (size * array[i])
   done

   for i := 0 to size-1 do
      sort bucket[i]
   done

   for i := 0 to size -1 do
      gather items of bucket[i] and put in array
   done
End

ตัวอย่าง

#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++) { //put elements into different buckets
      bucket[int(size*array[i])].push_back(array[i]);
   }

   for(int i = 0; i<size; i++) {
      sort(bucket[i].begin(), bucket[i].end()); //sort individual vectors
   }

   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]; //create an array with given number of elements
   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