Algoritma Pengurutan Keranjang (Java, Python, C/C++ Contoh Kode)
Sarah Chen
Apa itu Penyortiran Keranjang?
Pengurutan keranjang, sering disebut pengurutan bin, adalah metode pengurutan perbandingan yang menerima array yang tidak diurutkan sebagai masukan dan menghasilkan array yang diurutkan sebagai hasilnya. Metode ini bekerja dengan mendistribusikan elemen ke dalam beberapa keranjang dan mengurutkan setiap keranjang tersebut satu per satu menggunakan algoritma pengurutan apa pun seperti penyisipan. Kemudian semua ember digabungkan untuk membentuk larik yang terurut.
Pengurutan keranjang biasanya digunakan ketika elemen-
- Nilai titik mengambang
- Didistribusikan secara merata pada suatu rentang
Kompleksitas waktu sortir bucket bergantung pada jumlah bucket yang digunakan dan keseragaman distribusi input. Sementara algoritma sortir yang berbeda seperti semacam cangkang, menggabungkan pengurutan, heapsort, dan sortir cepat dapat mencapai kompleksitas waktu kasus terbaik O(n*logn), algoritma penyortiran bucket dapat mencapai hal yang sama dalam kompleksitas waktu linier atau O(n).
Bucket sort mengikuti pendekatan scatter-gather. Dengan menerapkan pendekatan ini, elemen-elemen disebar ke dalam bucket yang sesuai, diurutkan dalam bucket, dan dikumpulkan untuk membentuk array yang diurutkan sebagai langkah terakhir. Pendekatan scatter-gather ini dibahas di bagian berikut
Pendekatan Sebar-Kumpulkan
Masalah yang kompleks dan berskala besar terkadang sulit dipecahkan. Pendekatan scatter-gather mencoba memecahkan masalah tersebut dengan membagi seluruh kumpulan data ke dalam kelompok. Kemudian, setiap kelompok ditangani secara terpisah dan semuanya disatukan kembali untuk mendapatkan jawaban akhir.
Beginilah cara algoritma pengurutan keranjang mengimplementasikan metode scatter-gather:
Cara Kerja Penyortiran Keranjang
Prinsip kerja dasar dari bucket sort adalah sebagai berikut:
- Satu set keranjang kosong dibuat. Berdasarkan kebijakan yang berbeda, jumlah keranjang dapat berbeda.
- Dari array masukan, masukkan setiap elemen ke dalam keranjangnya yang sesuai.
- Sortir ember tersebut satu per satu.
- Gabungkan keranjang yang telah diurutkan untuk membuat larik keluaran tunggal.
Langkah-langkah kerja yang terperinci disediakan pada bagian berikut.
Kode Pseudo
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
Metode 1: Algoritma Pengurutan Bucket untuk Floating-Point Numbers
Algoritme pengurutan keranjang untuk bilangan floating point dalam rentang 0.0 hingga 1.0:
Langkah 1) Buat sepuluh (10) keranjang kosong sehingga keranjang pertama berisi angka dalam rentang [0.0, 0.1). Kemudian ember kedua akan berisi [0.1, 0.2), dan seterusnya.
Langkah 2) Untuk setiap elemen array:
-
A. Hitung indeks keranjang menggunakan rumus:
indeks ember= no_of_buckets *array_element
-
B. Masukkan elemen ke dalam keranjang[bucket_index]
Langkah 3) Urutkan setiap keranjang satu per satu menggunakan jenis penyisipan.
Langkah 4) Gabungkan semua keranjang menjadi satu larik.
Mari kita lihat contoh bucket sort. Untuk contoh ini, kita akan mengurutkan array berikut menggunakan algoritma bucket sort-
Langkah 1) Pertama, kita akan membuat 10 ember kosong. Keranjang pertama akan berisi angka antara [0.0, 0.1). Kemudian bucket kedua akan berisi angka antara [0.1, 0.2) dan seterusnya.
Langkah 2) Untuk setiap elemen array, kami akan menghitung indeks keranjang dan menempatkan elemen tersebut ke dalam keranjang tersebut.
Indeks bucket dapat dihitung menggunakan rumus:
indeks_ember= no_of_buckets*array_element
Perhitungan Indeks Bucket:
a) 0.78
bucket_index = no_of_buckets*array_element
= 10 * 0.78
= 7.8
Oleh karena itu, elemen 0.78 akan disimpan di bucket[floor(7.8)] atau bucket[7].
b) 0.17
bucket_index = no_of_buckets * elemen larik
= 10 * 0.17
= 1.7
Elemen array 0.17 akan disimpan di bucket[floor(1.7)] atau bucket[1].
c) 0.39
bucket_index = no_of_buckets * elemen larik
= 10 * 0.39
= 3.9
0.39 akan disimpan di bucket[floor(3.9)] atau bucket[3].
Setelah mengulangi semua elemen array, bucket-nya akan menjadi sebagai berikut:
Langkah 3) Kemudian setiap bucket akan diurutkan menggunakan insertion sort. Setelah operasi penyortiran, hasilnya adalah:
Langkah 4) Pada langkah terakhir, bucket akan digabungkan menjadi satu array. Array itu akan menjadi hasil input yang diurutkan.
Setiap keranjang akan digabungkan ke larik keluaran. Misalnya-penggabungan elemen keranjang kedua:
Penggabungan elemen bucket terakhir akan menjadi sebagai berikut:
Setelah penggabungan, array yang dihasilkan akan menjadi array terurut yang diinginkan.
Program Sortir Bucket di C/C++
Memasukkan:
//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;
}
Keluaran:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Program Penyortiran Ember di Python
Memasukkan:
# 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))
Keluaran:
Sorted Output: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]
Sortir Ember Java
Memasukkan:
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]+" ");
}
}
}
Keluaran:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Metode 2: Algoritma Pengurutan Bucket untuk Elemen Integer
Algoritme pengurutan bucket untuk input yang berisi angka di luar rentang [0.0, 1.0] sedikit berbeda dari sebelumnya algoritma. Langkah-langkah yang diperlukan untuk kasus ini adalah sebagai berikut-
Langkah 1) Temukan elemen maksimum dan minimum.
Langkah 2) Pilih jumlah keranjang, n, dan inisialisasi keranjang tersebut sebagai kosong.
Langkah 3) Hitung rentang atau rentang setiap keranjang menggunakan rumus:
span = (maximum - minimum)/n
Langkah 4) Untuk setiap elemen array:
-
1.Hitung indeks keranjang:
bucket_index = (element - minimum)/span-
2.Masukkan elemen ke dalam bucket[bucket_index]
Langkah 5) Urutkan setiap keranjang menggunakan jenis penyisipan.
Langkah 6) Gabungkan semua keranjang menjadi satu larik.
Mari kita lihat contoh algoritma bucket sort ini. Untuk contoh ini, kita akan mengurutkan array berikut menggunakan algoritma bucket sort-
Langkah 1) Pada langkah pertama, elemen maksimum dan minimum dari array yang diberikan perlu ditemukan. Untuk contoh ini, maksimumnya adalah 24 dan minimumnya adalah 1.
Langkah 2) Sekarang, kita harus memilih sejumlah ember kosong, n. Dalam contoh ini, kita akan mengambil 5 ember. Kemudian kita akan menginisialisasinya sebagai kosong.
Langkah 3) Rentang setiap bucket perlu dihitung dengan rumus berikut:
span = (maximum-minimum)/n = (24-1)/5 = 4;
Oleh karena itu, keranjang pertama akan berisi angka-angka dalam rentang [0, 5). Keranjang kedua akan berisi angka dalam [5, 10) dan seterusnya.
Langkah 4) Untuk setiap elemen array, kami akan menghitung indeks keranjang dan menempatkan elemen tersebut ke dalam keranjang tersebut. Indeks bucket dapat dihitung menggunakan rumus:
bucket_index = (element - minimum)/span
Perhitungan Indeks Bucket:
-
a) 11bucket_index = (elemen – minimum)/span
=(11-1)/4
=2
Dengan demikian, elemen 11 akan disimpan dalam bucket[2].
-
b) 9
bucket_index = (elemen – minimum)/span
=(9-1)/4
=2
Catatan: Karena 9 adalah elemen batas untuk keranjang[1], ia perlu ditambahkan dalam keranjang[1] alih-alih menambahkan dalam keranjang yang sama dengan elemen sebelumnya.
Setelah melakukan operasi untuk setiap elemen, bucketnya akan menjadi seperti berikut:
Langkah 5) Sekarang, setiap bucket akan diurutkan menggunakan insertion sort. Ember setelah disortir-
Langkah 6) Pada langkah terakhir, bucket akan digabungkan menjadi satu array. Itu susunan akan menjadi hasil input yang diurutkan.
Program Sortir Bucket di C/C++
Memasukkan:
#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;
}
Keluaran:
Sorted Output:1 8 9 11 12 13 17 19 21 24
Program Penyortiran Ember di Python
Memasukkan:
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)
Keluaran:
Sorted Output: [1, 8, 9, 11, 12, 13, 17, 19, 21, 24]
Sortir Ember Java
Memasukkan:
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 + " ");
}
}
}
Keluaran:
Sorted Output: 1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0
Pro kontra
| Pro | Kekurangan |
|---|---|
| Lakukan komputasi lebih cepat | Mengonsumsi lebih banyak ruang dibandingkan dengan algoritma lainnya |
| Ini dapat digunakan sebagai metode penyortiran eksternal | Berkinerja buruk ketika data tidak terdistribusi secara merata |
| Ember dapat diproses secara mandiri |
Analisis Kompleksitas Sortiran Bucket
Kompleksitas Waktu Bucket Sort
- Kompleksitas Kasus Terbaik:Jika semua elemen array terdistribusi secara merata dan diurutkan terlebih dahulu, maka diperlukan waktu O(n) untuk menyebarkan elemen ke dalam keranjang yang sesuai. Kemudian menyortir setiap ember menggunakan jenis penyisipan akan menghabiskan biaya O(k). Jadi, kompleksitas keseluruhannya akan menjadi O(n+k).
- Kompleksitas Kasus Rata-rata:Untuk kasus rata-rata, kami berasumsi bahwa input didistribusikan secara seragam. Dengan demikian, algoritma penyortiran bucket mencapai kompleksitas waktu linier sebesar O(n+k). Di sini, waktu O(n) diperlukan untuk menyebarkan elemen dan waktu O(k) diperlukan untuk mengurutkan elemen tersebut menggunakan penyisipan.
- Kompleksitas Kasus Terburuk:Dalam kasus terburuk, elemen-elemen tersebut tidak akan terdistribusi secara merata dan terkonsentrasi pada satu atau dua wadah tertentu. Dalam hal ini, pengurutan keranjang akan berfungsi sebagai a algoritma pengurutan gelembung. Oleh karena itu, dalam kasus terburuk, kompleksitas waktu dari pengurutan bucket akan menjadi O(n^2).
Kompleksitas Ruang dari Bucket Sort
Kompleksitas ruang bucket sort adalah O(n*k). Di sini n adalah jumlah elemen dan k adalah jumlah bucket yang dibutuhkan.
