Algoritma Pengurutan Keranjang (Java, Python, C/C++ Code Contoh)

Apa itu Penyortiran Keranjang?

Bucket Sort, yang sering disebut bin sort, adalah metode pengurutan distribusi berbasis perbandingan yang menerima array yang belum diurutkan sebagai input dan menghasilkan array yang sudah diurutkan sebagai output. Teknik ini mendistribusikan elemen ke dalam beberapa bucket dan mengurutkan setiap bucket secara individual menggunakan algoritma pengurutan lain seperti insertion sort. Kemudian, semua bucket digabungkan untuk membentuk array akhir yang sudah diurutkan.

Pengurutan Ember (Bucket Sort) umumnya digunakan ketika elemen-elemennya:

1. Nilai titik mengambang
2. Terdistribusi secara merata dalam rentang yang diketahui.

Kompleksitas waktu dari Bucket Sort bergantung pada jumlah bucket yang digunakan dan keseragaman distribusi input. Sementara algoritma pengurutan lainnya seperti semacam cangkang, menggabungkan pengurutan, heapsort, dan sortir cepat Dengan mencapai kompleksitas waktu kasus terbaik O(n*logn), algoritma Bucket Sort dapat mencapai kompleksitas waktu linier O(n) dalam kondisi yang menguntungkan.

Algoritma Bucket Sort mengikuti pendekatan scatter-gather. Elemen-elemen disebar ke dalam bucket yang sesuai, diurutkan di dalam setiap bucket, dan dikumpulkan untuk membentuk array yang sudah diurutkan sebagai langkah terakhir. Pendekatan scatter-gather ini akan dibahas di bagian selanjutnya.

Pendekatan Sebar-Kumpul

Masalah berskala besar dan kompleks terkadang sulit dipecahkan secara langsung. Pendekatan scatter-gather mengatasi masalah tersebut dengan membagi seluruh dataset menjadi beberapa klaster. Setiap klaster diproses secara terpisah, dan hasilnya digabungkan kembali untuk menghasilkan jawaban akhir.

Berikut cara algoritma Bucket Sort mengimplementasikan metode scatter-gather:

Cara Kerja Penyortiran Keranjang

Prinsip kerja dasar dari Bucket Sort adalah sebagai berikut:

1. Sejumlah wadah kosong dibuat. Berdasarkan kebijakan yang dipilih, jumlah wadah dapat bervariasi.
2. Dari larik masukan, setiap elemen ditempatkan ke dalam wadah yang sesuai.
3. Setiap bucket diurutkan secara individual menggunakan algoritma pengurutan sekunder.
4. Bucket yang telah diurutkan digabungkan untuk menghasilkan satu array keluaran tunggal.

Pseudo Code

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

Algoritma Bucket Sort untuk bilangan floating-point dalam rentang [0.0, 1.0]:

Langkah 1) Buatlah sepuluh (10) ember kosong. Ember pertama berisi angka dalam rentang [0.0, 0.1). Ember kedua berisi [0.1, 0.2), dan seterusnya.

Langkah 2) Untuk setiap elemen array:

• a. Hitung indeks bucket menggunakan rumus:
  indeks_bucket = jumlah_bucket * elemen_array
• b. Masukkan elemen ke dalam bucket[bucket_index]

Langkah 3) Urutkan setiap keranjang satu per satu menggunakan jenis penyisipan.

Langkah 4) Gabungkan semua bucket menjadi satu array yang sudah diurutkan.

Mari kita bahas contoh Bucket Sort. Untuk contoh ini, kita akan mengurutkan array berikut:

Langkah 1) Pertama, kita membuat 10 wadah kosong. Wadah pertama berisi angka dalam rentang [0.0, 0.1). Wadah kedua berisi angka dalam rentang [0.1, 0.2), dan seterusnya.

Langkah 2) Untuk setiap elemen array, hitung indeks bucket dan tempatkan elemen tersebut ke dalam bucket tersebut.

Indeks bucket dihitung menggunakan rumus:
        indeks_bucket = jumlah_bucket * elemen_array

Perhitungan Indeks Bucket:
a) 0.78
      indeks_bucket = jumlah_bucket * elemen_array
              = 10 * 0.78
              = 7.8
Oleh karena itu, elemen 0.78 disimpan di bucket[floor(7.8)] atau bucket[7].

b) 0.17
      indeks_bucket = jumlah_bucket * elemen_array
              = 10 * 0.17
              = 1.7

Elemen array 0.17 disimpan di bucket[floor(1.7)] atau bucket[1].

c) 0.39
      indeks_bucket = jumlah_bucket * elemen_array
              = 10 * 0.39
              = 3.9
0.39 disimpan di bucket[floor(3.9)] atau bucket[3].

Setelah mengulangi proses pada semua elemen array, bucket akan terlihat seperti berikut:

Langkah 3) Setiap bucket kemudian diurutkan menggunakan insertion sort. Setelah operasi pengurutan, hasilnya adalah:

Langkah 4) Pada langkah terakhir, bucket-bucket tersebut digabungkan menjadi satu array tunggal. Array tersebut merupakan hasil akhir yang telah diurutkan dari input.

Setiap bucket digabungkan ke dalam array output. Misalnya, penggabungan elemen bucket kedua:

Penggabungan elemen-elemen bucket terakhir ditunjukkan di bawah ini:

Setelah penggabungan, array yang dihasilkan adalah array terurut yang diinginkan.

Program Sortir Bucket di C/C++

Memasukkan:

//Bucket Sort Program in C/C++
//For values without 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: 
";
  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 values without 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

Algoritma Bucket Sort untuk input yang berisi angka di luar rentang [0.0, 1.0] sedikit berbeda dari algoritma sebelumnya. algoritmaLangkah-langkah yang diperlukan untuk kasus ini adalah sebagai berikut:

Langkah 1) Temukan elemen maksimum dan minimum dalam array tersebut.

Langkah 2) Pilih jumlah wadah, n, dan inisialisasikan 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 bucket:
          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 bahas contoh algoritma Bucket Sort ini. Untuk contoh ini, kita akan mengurutkan array berikut:

Langkah 1) Pada langkah pertama, kita mencari elemen maksimum dan minimum dari array yang diberikan. Untuk contoh ini, nilai maksimumnya adalah 24 dan nilai minimumnya adalah 1.

Langkah 2) Selanjutnya, kita memilih jumlah wadah kosong, n. Dalam contoh ini, kita menggunakan 5 wadah dan menginisialisasinya sebagai wadah kosong.

Langkah 3) Rentang setiap bucket dihitung menggunakan rumus:
        span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Oleh karena itu, bucket pertama berisi angka dalam rentang [0, 5). Bucket kedua berisi angka dalam rentang [5, 10), dan seterusnya.

Langkah 4) Untuk setiap elemen array, hitung indeks bucket dan tempatkan elemen tersebut ke dalam bucket tersebut. Indeks bucket dihitung menggunakan rumus:
        bucket_index = (element - minimum) / span

Perhitungan Indeks Bucket:

a) 11
indeks_bucket = (elemen – minimum) / rentang
        = (11 – 1) / 4
        = 2

Dengan demikian, elemen 11 disimpan di dalam bucket[2].

b) 9
indeks_bucket = (elemen – minimum) / rentang
        = (9 – 1) / 4
        = 2

Catatan: Karena 9 adalah elemen batas untuk bucket[1], maka ia ditambahkan ke bucket[1] alih-alih ditempatkan di bucket yang sama dengan elemen sebelumnya.

Setelah melakukan operasi untuk setiap elemen, bucket akan terlihat seperti berikut:

Langkah 5) Sekarang, setiap bucket diurutkan menggunakan insertion sort. Berikut adalah hasil pengurutan untuk setiap bucket:

Langkah 6) Pada langkah terakhir, bucket-bucket tersebut digabungkan menjadi satu array tunggal. Itu susunan adalah hasil pengurutan dari input.

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=0; 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:
", 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

Kelebihan & Kekurangan Metode Pengurutan Ember

Analisis Kompleksitas Sortiran Bucket

Kompleksitas Waktu Pengurutan Bucket

• Kompleksitas Kasus Terbaik: Jika semua elemen array terdistribusi secara seragam dan telah diurutkan sebelumnya di dalam setiap bucket, maka dibutuhkan waktu O(n) untuk menyebarkan elemen-elemen tersebut ke dalam bucket yang sesuai. Kemudian mengurutkan setiap bucket menggunakan jenis penyisipan Biayanya O(k). Dengan demikian, kompleksitas keseluruhannya adalah O(n+k).
• Kompleksitas Kasus Rata-rata: Untuk kasus rata-rata, kita mengasumsikan input terdistribusi secara seragam. Dengan demikian, algoritma Bucket Sort mencapai kompleksitas waktu linier O(n+k). Di sini, waktu O(n) diperlukan untuk menyebarkan elemen dan waktu O(k) diperlukan untuk mengurutkannya menggunakan insertion sort.
• Kompleksitas Kasus Terburuk: Dalam kasus terburuk, elemen-elemen tidak terdistribusi secara merata dan terkonsentrasi dalam satu atau dua bucket. Dalam kasus tersebut, Bucket Sort akan berperilaku mirip dengan algoritma pengurutan lainnya. algoritma pengurutan gelembungOleh karena itu, dalam kasus terburuk, kompleksitas waktu Bucket Sort adalah O(n²).

Kompleksitas Ruang dari Bucket Sort

Kompleksitas ruang dari Bucket Sort adalah O(n*k). Di sini, n adalah jumlah elemen dan k adalah jumlah bucket yang dibutuhkan untuk menampung elemen-elemen tersebut selama proses pengurutan.

Pertanyaan Umum Demo Slot