อัลกอริธึมการเรียงลำดับที่เก็บข้อมูล (Java, Python, ค/C++ ตัวอย่างโค้ด)

Bucket Sort คืออะไร?

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

การเรียงลำดับถังมักใช้เมื่อองค์ประกอบคือ-

1. ค่าจุดลอยตัว
2. กระจายอย่างเท่าเทียมกันในช่วง

ความซับซ้อนของเวลาในการเรียงลำดับแบบ Bucket ขึ้นอยู่กับจำนวน Bucket ที่ใช้และความสม่ำเสมอของการกระจายอินพุต ในขณะที่อัลกอริทึมการเรียงลำดับที่แตกต่างกัน เช่น การเรียงลำดับเปลือก, การเรียงลำดับแบบผสาน, ฮีปเรียงลำดับ และ Quicksort สามารถบรรลุความซับซ้อนของเวลาในกรณีที่ดีที่สุดของ O(n*logn) ได้ อัลกอริธึมการเรียงลำดับบัคเก็ตสามารถบรรลุผลเช่นเดียวกันได้ในความซับซ้อนของเวลาเชิงเส้นหรือ O(n)

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

กระจาย-รวบรวม-แนวทาง

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

นี่คือวิธีที่อัลกอริธึมการเรียงลำดับบัคเก็ตใช้เมธอด Scatter-gather:

การเรียงลำดับถังทำงานอย่างไร

หลักการทำงานพื้นฐานของการเรียงลำดับถังมีดังนี้:

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

ขั้นตอนการทำงานโดยละเอียดมีอยู่ในหัวข้อต่อไปนี้

รหัสหลอก

Start
Create N empty buckets
For each array element:
Calculate bucket index
Put that element into the corresponding bucket
For each bucket:
Sort elements within each bucket
Merge all the elements from each bucket
Output the sorted array
End

วิธีที่ 1: อัลกอริทึมการเรียงลำดับบัคเก็ตสำหรับจุดลอยตัว Numbers

อัลกอริทึมการเรียงลำดับบัคเก็ตสำหรับตัวเลขจุดลอยตัวในช่วงตั้งแต่ 0.0 ถึง 1.0:

ขั้นตอน 1) สร้างบัคเก็ตว่างสิบ (10) อัน โดยที่บัคเก็ตแรกจะบรรจุตัวเลขที่อยู่ในช่วง [0.0, 0.1) จากนั้นบัคเก็ตที่สองจะบรรจุตัวเลขที่อยู่ในช่วง [0.1, 0.2) และเป็นเช่นนี้ต่อไป

ขั้นตอน 2) สำหรับแต่ละองค์ประกอบอาร์เรย์:

ก. คำนวณดัชนีถังโดยใช้สูตร:
ดัชนีที่เก็บข้อมูล = no_of_buckets *array_element

ข. แทรกองค์ประกอบลงในที่เก็บข้อมูล [bucket_index]

ขั้นตอน 3) จัดเรียงแต่ละที่เก็บข้อมูลแยกกันโดยใช้การเรียงลำดับการแทรก

ขั้นตอน 4) เชื่อมต่อที่เก็บข้อมูลทั้งหมดไว้ในอาร์เรย์เดียว

มาดูตัวอย่างการเรียงลำดับแบบ Bucket กัน สำหรับตัวอย่างนี้ เราจะเรียงลำดับอาร์เรย์ต่อไปนี้โดยใช้อัลกอริทึมการเรียงลำดับแบบ Bucket

ขั้นตอน 1) ขั้นแรก เราจะสร้างบัคเก็ตเปล่า 10 อัน บัคเก็ตแรกจะมีตัวเลขระหว่าง [0.0, 0.1) จากนั้นบัคเก็ตที่สองจะมีตัวเลขระหว่าง [0.1, 0.2) เป็นต้นไป

ขั้นตอน 2) สำหรับแต่ละองค์ประกอบอาร์เรย์ เราจะคำนวณดัชนีบัคเก็ตและวางองค์ประกอบลงในบัคเก็ตนั้น

ดัชนีถังสามารถคำนวณได้โดยใช้สูตร:
              bucket_index= no_of_buckets*array_element

การคำนวณดัชนีถัง:
a) 0.78
      bucket_index = no_of_buckets*array_element
                   = 10 * 0.78
                   = 7.8
ดังนั้น องค์ประกอบ 0.78 จะถูกจัดเก็บไว้ในบัคเก็ต[พื้น(7.8)] หรือบัคเก็ต[7]

b) 0.17
      bucket_index = no_of_buckets * องค์ประกอบอาร์เรย์
                   = 10 * 0.17
                   = 1.7

องค์ประกอบอาร์เรย์ 0.17 จะถูกเก็บไว้ใน bucket[floor(1.7)] หรือ bucket[1]

c) 0.39
      bucket_index = no_of_buckets * องค์ประกอบอาร์เรย์
                   = 10*0.39
                   = 3.9
   0.39 จะถูกเก็บไว้ในบัคเก็ต[ชั้น(3.9)] หรือบัคเก็ต[3]

หลังจากทำการวนซ้ำผ่านองค์ประกอบอาร์เรย์ทั้งหมดแล้ว บัคเก็ตจะเป็นดังต่อไปนี้:

ขั้นตอน 3) จากนั้นถังแต่ละถังจะถูกเรียงลำดับโดยใช้การเรียงลำดับแบบแทรก หลังจากดำเนินการเรียงลำดับแล้ว ผลลัพธ์จะเป็นดังนี้:

ขั้นตอน 4) ในขั้นตอนสุดท้าย ที่เก็บข้อมูลจะต่อกันเป็นอาร์เรย์เดียว อาร์เรย์นั้นจะเป็นผลลัพธ์ที่เรียงลำดับของอินพุต

แต่ละที่เก็บข้อมูลจะถูกต่อเข้ากับอาร์เรย์เอาต์พุต ตัวอย่างเช่น การต่อข้อมูลขององค์ประกอบที่เก็บข้อมูลที่สอง:

การเชื่อมโยงขององค์ประกอบถังสุดท้ายจะเป็นดังต่อไปนี้:

หลังจากต่อข้อมูลแล้ว อาเรย์ที่ได้จะเป็นอาเรย์ที่เรียงลำดับที่ต้องการ

โปรแกรม Bucket Sort ด้วยภาษา C/C++

Input:

//Bucket Sort Program in C/C++
//For not having integer parts
#include <bits/stdc++.h>
#define BUCKET_SIZE 10
using namespace std;
void bucketSort(float input[], int array_size)
{
  vector <float>bucket[BUCKET_SIZE];
for (int i = 0; i < array_size; i++) {
    int index = BUCKET_SIZE*input[i];
 bucket[index].push_back(input[i]);
  }
for (int i = 0; i < BUCKET_SIZE; i++)
    sort(bucket[i].begin(), bucket[i].end());
  int out_index = 0;
  for (int i = 0; i < BUCKET_SIZE; i++)
    for (int j = 0; j < bucket[i].size(); j++)
      input[out_index++] = bucket[i][j];
}
int main()
{
float input[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.69};
 int array_size = sizeof(input)/sizeof(input[0]);
 
 bucketSort(input, array_size);
 cout <<"Sorted Output: \n";
 for (int i = 0; i< array_size; i++)
 cout<<input[i]<<" ";
return 0;
}

Output:

Sorted Output:
0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94

โปรแกรม Bucket Sort ใน Python

Input:

# Bucket Sort Program in Python
# For not having integer parts
def bucketSort(input):
    output = []
    bucket_size = 10
    for bucket in range(bucket_size):
        output.append([])
    for element in input:
        index = int(bucket_size * element)
        output[index].append(element)
    for bucket in range(bucket_size):
        output[bucket] = sorted(output[bucket])
    out_index = 0
    for bucket in range(bucket_size):
        for element in range(len(output[bucket])):
            input[out_index] = output[bucket][element]
            out_index += 1
    return input

input = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.69]
print("Sorted Output:")
print(bucketSort(input))

Output:

Sorted Output:
[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]

ถังเรียงลำดับใน Java

Input:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    private static final int BUCKET_SIZE = 10;
    public static void bucketSort(float[] input, int arraySize) {
        List <
        Float >
        [] bucket = new ArrayList[BUCKET_SIZE];
        for (int i = 0; i < arraySize; i++) {
            int index = (int)(BUCKET_SIZE * input[i]);
            if (bucket[index] == null) {
                bucket[index] = new ArrayList < >
                ();
            }
            bucket[index].add(input[i]);
        }
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (bucket[i] != null) {
                Collections.sort(bucket[i]);
            }
        }
        int outIndex = 0;
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (bucket[i] != null) {
                for (float value: bucket[i]) {
                    input[outIndex++] = value;
               }
            }
        }
    }
    public static void main(String[] args) {
    float[] input = {0.78f,0.17f,0.39f,0.26f,0.72f,0.94f,0.21f,0.12f,0.23f,0.69f};
        int arraySize = input.length;
        bucketSort(input, arraySize);
        System.out.println("Sorted Output:");
        for (int i = 0; i < arraySize; i++) {
            System.out.print(input[i]+" ");
        }
    }
}

Output:

Sorted Output:
0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94

วิธีที่ 2: อัลกอริธึมการเรียงลำดับ Bucket สำหรับองค์ประกอบจำนวนเต็ม

อัลกอริทึมการเรียงลำดับแบบบัคเก็ตสำหรับอินพุตที่มีตัวเลขเกินช่วง [0.0, 1.0] แตกต่างจากอัลกอริทึมก่อนหน้าเล็กน้อย ขั้นตอนวิธี- ขั้นตอนที่จำเป็นสำหรับกรณีนี้มีดังนี้-

ขั้นตอน 1) ค้นหาองค์ประกอบสูงสุดและต่ำสุด

ขั้นตอน 2) เลือกจำนวนที่เก็บข้อมูล n และเริ่มต้นที่เก็บข้อมูลเหล่านั้นเป็นค่าว่าง

ขั้นตอน 3) คำนวณช่วงหรือช่วงของแต่ละที่เก็บข้อมูลโดยใช้สูตร:
               span = (maximum - minimum)/n

ขั้นตอน 4) สำหรับแต่ละองค์ประกอบอาร์เรย์:

1. คำนวณดัชนีถัง:
               bucket_index = (element - minimum)/span

2.ใส่องค์ประกอบลงในที่ฝากข้อมูล[bucket_index]

ขั้นตอน 5) จัดเรียงแต่ละที่เก็บข้อมูลโดยใช้การเรียงลำดับการแทรก

ขั้นตอน 6) เชื่อมต่อที่เก็บข้อมูลทั้งหมดไว้ในอาร์เรย์เดียว

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

ขั้นตอน 1) ในขั้นตอนแรก จำเป็นต้องค้นหาองค์ประกอบสูงสุดและต่ำสุดของอาร์เรย์ที่กำหนด สำหรับตัวอย่างนี้ ค่าสูงสุดคือ 24 และค่าต่ำสุดคือ 1

ขั้นตอน 2) ตอนนี้เราต้องเลือกถังเปล่าจำนวนหนึ่ง n ในตัวอย่างนี้ เราจะใช้ 5 ที่เก็บข้อมูล จากนั้นเราจะกำหนดค่าเริ่มต้นให้ว่างเปล่า

ขั้นตอน 3) ระยะขยายของถังแต่ละถังต้องคำนวณโดยใช้สูตรต่อไปนี้:
               span = (maximum-minimum)/n = (24-1)/5 = 4;

ดังนั้นถังแรกจะประกอบด้วยตัวเลขที่อยู่ในช่วง [0, 5) ถังที่สองจะประกอบด้วยตัวเลขที่อยู่ในช่วง [5, 10) และอื่นๆ

ขั้นตอน 4) สำหรับแต่ละองค์ประกอบอาร์เรย์ เราจะคำนวณดัชนีบัคเก็ตและวางองค์ประกอบลงในบัคเก็ตนั้น ดัชนีถังสามารถคำนวณได้โดยใช้สูตร:
               bucket_index = (element - minimum)/span

การคำนวณดัชนีถัง:

ก) 11bucket_index = (องค์ประกอบ – ขั้นต่ำ)/span
                   =(11-1)/4
                   =2

ดังนั้นองค์ประกอบที่ 11 จะถูกจัดเก็บไว้ในที่เก็บข้อมูล [2]

b) 9
bucket_index = (องค์ประกอบ – ขั้นต่ำ)/span
                   =(9-1)/4
                   =2

หมายเหตุ เนื่องจาก 9 เป็นองค์ประกอบขอบเขตสำหรับที่เก็บข้อมูล [1] จึงจำเป็นต้องต่อท้ายในที่เก็บข้อมูล [1] แทนที่จะต่อท้ายในที่เก็บข้อมูลเดียวกันขององค์ประกอบก่อนหน้า

หลังจากดำเนินการกับแต่ละองค์ประกอบแล้ว ถังจะเป็นดังต่อไปนี้:

ขั้นตอน 5) ตอนนี้ แต่ละที่เก็บข้อมูลจะถูกจัดเรียงโดยใช้การเรียงลำดับการแทรก ถังหลังจากการเรียงลำดับ-

ขั้นตอน 6) ในขั้นตอนสุดท้าย ที่เก็บข้อมูลจะต่อกันเป็นอาร์เรย์เดียว ที่ แถว จะเป็นผลลัพธ์ที่เรียงลำดับของอินพุต

โปรแกรม Bucket Sort ด้วยภาษา C/C++

Input:

#include<bits/stdc++.h>
using namespace std;
void bucketSort(vector < double > & input, int No_Of_Buckets)
{
  double max_value = * max_element(input.begin(), input.end());
  double min_value = * min_element(input.begin(), input.end());
  double span = (max_value - min_value) / No_Of_Buckets;
  vector<vector <double>>
  output;
  for (int i = 0; i < No_Of_Buckets; i++)
    output.push_back(vector <double>
      ());
  for (int i = 0; i < input.size(); i++)
  {
    double difference = (input[i] - min_value) / span
     -
      int((input[i] - min_value) / span);
    if (difference == 0 && input[i] != min_value)
      output[int((input[i] - min_value) / span) - 1]
      .push_back(input[i]);
    else
      output[int((input[i] - min_value) / span)].push_back(
        input[i]);
  }
  for (int i = 0; i < output.size(); i++)
  {
    if (!output[i].empty())
      sort(output[i].begin(), output[i].end());
  }
  int index = 0;
  for (vector <double> & bucket: output)
  {
    if (!bucket.empty())
    {
      for (double i: bucket)
      {
        input[index] = i;
        index++;
      }
    }
  }
}
int main()
{
  vector <double>
  input ={11,9,21,8,17,19,13,1,24,12
  };
  int No_Of_Buckets = 5;
  bucketSort(input, No_Of_Buckets);
  cout<<
  "Sorted Output:";
  for (int i; i < input.size(); i++)
    cout <<input[i]<<" ";
  return 0;
}

Output:

Sorted Output:1 8 9 11 12 13 17 19 21 24

โปรแกรม Bucket Sort ใน Python

Input:

def bucketSort(input, No_Of_Buckets):
    max_element = max(input)
    min_element = min(input)
    span = (max_element - min_element) / No_Of_Buckets
    output = []
    for bucket in range(No_Of_Buckets):
        output.append([])
    for element in range(len(input)):
        diff = (input[element] - min_element) / span - int(
            (input[element] - min_element) / span
        )
        if diff == 0 and input[element] != min_element:
            output[int((input[element] - min_element) / span) - 1].append(
                input[element]
            )
        else:
            output[int((input[element] - min_element) / span)].append(input[element])
    for bucket in range(len(output)):
        if len(output[bucket]) != 0:
            output[bucket].sort()
    index = 0
    for bucket in output:
        if bucket:
            for element in bucket:
                input[index] = element
                index = index + 1
input = [11, 9, 21, 8, 17, 19, 13, 1, 24, 12]
No_Of_Buckets = 5
bucketSort(input, No_Of_Buckets)
print("Sorted Output:\n", input)

Output:

Sorted Output:
[1, 8, 9, 11, 12, 13, 17, 19, 21, 24]

ถังเรียงลำดับใน Java

Input:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    public static void bucketSort(List < Double > input, int No_Of_Buckets) {
        double max_value = Collections.max(input);
        double min_value = Collections.min(input);
        double span =(max_value - min_value) / No_Of_Buckets;
        List <
        List <
        Double > >
        output = new ArrayList < >
        ();
        for (int i = 0; i < No_Of_Buckets; i++) {
            output.add(new ArrayList < >
                ());
        }
        for (Double value: input) {
            double difference = (value - min_value) / span - ((value - min_value) / span);
            if (difference == 0 && value != min_value) {
                output.get((int)((value - min_value) / span) - 1).add(value);
            } else {
                output.get((int)((value - min_value) / span)).add(value);
				}
			}
        for (List <Double> bucket: output) {
            if (!bucket.isEmpty()) {
			Collections.sort(bucket);
            }
        }
        int index = 0;
        for (List <Double> bucket: output) {
            if (!bucket.isEmpty()) {
                for (Double value: bucket) {
                    input.set(index,value);
                    index++;
                }
            }
        }
    }
    public static void main(String[] args) {
        List <Double>
        input = new ArrayList <>
        ();
        input.add(11.0);
		input.add(9.0);
        input.add(21.0);
        input.add(8.0);
        input.add(17.0);
        input.add(19.0);
        input.add(13.0);
        input.add(1.0);
        input.add(24.0);
        input.add(12.0);
        int No_Of_Buckets = 5;
        bucketSort(input, No_Of_Buckets);
        System.out.println("Sorted Output:");
        for (Double value: input) {
		System.out.print(value + " ");
        }
    }
}

Output:

Sorted Output:
1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0

ข้อเสียข้อดี

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

การวิเคราะห์ความซับซ้อนของการเรียงลำดับแบบ Bucket

ความซับซ้อนของเวลาในการเรียงลำดับแบบ Bucket Sort

• ความซับซ้อนของเคสที่ดีที่สุด:หากองค์ประกอบอาร์เรย์ทั้งหมดมีการกระจายและจัดเรียงอย่างสม่ำเสมอ จะต้องใช้เวลา O(n) เพื่อกระจายองค์ประกอบลงในที่เก็บข้อมูลที่เกี่ยวข้อง แล้วคัดแยกแต่ละถังโดยใช้ การเรียงลำดับการแทรก จะมีราคา O(k) ดังนั้นความซับซ้อนโดยรวมจะเท่ากับ O(n+k)

• ความซับซ้อนของเคสโดยเฉลี่ย:สำหรับกรณีทั่วไป เราถือว่าอินพุตกระจายสม่ำเสมอ ดังนั้นอัลกอริทึมการเรียงลำดับบัคเก็ตจึงมีความซับซ้อนของเวลาเชิงเส้นเท่ากับ O(n+k) โดยที่ต้องใช้เวลา O(n) เพื่อกระจายองค์ประกอบ และต้องใช้เวลา O(k) เพื่อเรียงลำดับองค์ประกอบเหล่านั้นโดยใช้การเรียงลำดับแบบแทรก

• ความซับซ้อนของกรณีที่เลวร้ายที่สุด:ในกรณีที่เลวร้ายที่สุด องค์ประกอบต่างๆ จะไม่กระจายสม่ำเสมอและกระจุกตัวอยู่ในที่เก็บข้อมูลเฉพาะหนึ่งหรือสองชุด ในกรณีนั้น การเรียงลำดับบัคเก็ตจะทำงานเป็น อัลกอริธึมการเรียงลำดับฟอง ดังนั้น ในกรณีที่เลวร้ายที่สุด ความซับซ้อนของเวลาของการเรียงลำดับแบบถังจะอยู่ที่ O(n^2)

ความซับซ้อนของพื้นที่ในการเรียงลำดับแบบ Bucket

ความซับซ้อนของพื้นที่ในการเรียงลำดับแบบ Bucket คือ O(n*k) โดยที่ n คือจำนวนองค์ประกอบ และ k คือจำนวน Bucket ที่ต้องการ