Jenis Keranjang di Jawa

1. Perkenalan

Dalam artikel ini, kita akan mendalami algoritme pengurutan keranjang. Kami akan mulai dengan sedikit teori, sebelum mengerjakan implementasi Java bersamaan dengan pengujian unit solusi kami. Terakhir, kita akan melihat kerumitan waktu dalam pengurutan bucket.

2. Teori Penyortiran Bucket

Pengurutan keranjang, terkadang dikenal sebagai pengurutan bin, adalah algoritme pengurutan khusus. Pengurutan bekerja dengan mendistribusikan elemen yang ingin kita sortir ke dalam beberapa keranjang yang diurutkan secara individual. Dengan melakukan ini, kami dapat mengurangi jumlah perbandingan antara elemen dan membantu mempersingkat waktu penyortiran.

Mari kita lihat sekilas langkah - langkah yang diperlukan untuk melakukan pengurutan ember :

  1. Siapkan sebuah array dari bucket kosong kami yang awalnya
  2. Distribusikan elemen kami ke dalam keranjang yang sesuai
  3. Sortir setiap ember
  4. Gabungkan keranjang yang diurutkan untuk membuat kembali daftar lengkapnya

3. Implementasi Java

Meskipun algoritme ini tidak khusus bahasa, kami akan mengimplementasikan sortir di Java. Mari melalui daftar di atas selangkah demi selangkah dan tulis kode untuk mengurutkan daftar bilangan bulat.

3.1. Penyiapan Bucket

Pertama, kita perlu menentukan algoritme hashing untuk memutuskan elemen mana yang ditempatkan di bucket mana:

private int hash(int i, int max, int numberOfBuckets) { return (int) ((double) i / max * (numberOfBuckets - 1)); }

Dengan mendefinisikan metode hash, sekarang kita dapat menentukan jumlah bin sebagai akar kuadrat dari ukuran daftar input :

final int numberOfBuckets = (int) Math.sqrt(initialList.size()); List
    
      buckets = new ArrayList(numberOfBuckets); for(int i = 0; i < numberOfBuckets; i++) { buckets.add(new ArrayList()); }
    

Akhirnya, kami membutuhkan metode singkat untuk menentukan bilangan bulat maksimum dalam daftar masukan kami:

private int findMax(List input) { int m = Integer.MIN_VALUE; for (int i : input) { m = Math.max(i, m); } return m; }

3.2. Mendistribusikan Elemen

Sekarang setelah bucket kami ditentukan, kami dapat mendistribusikan setiap elemen dari daftar input kami ke bucket yang relevan menggunakan metode hash :

int max = findMax(initialList); for (int i : initialList) { buckets.get(hash(i, max, numberOfBuckets)).add(i); } 

3.3. Menyortir Bucket Individu

Dengan bucket kita ditentukan dan penuh dengan bilangan bulat, mari gunakan Comparator untuk mengurutkannya :

Comparator comparator = Comparator.naturalOrder(); for(List bucket : buckets){ bucket.sort(comparator); }

3.4. Menggabungkan Bucket Kami

Terakhir, kita perlu mengumpulkan semua ember untuk membuat ulang daftar tunggal. Karena keranjang kita diurutkan, kita hanya perlu mengulang setiap keranjang sekali dan menambahkan elemen ke daftar master:

List sortedArray = new LinkedList(); for(List bucket : buckets) { sortedArray.addAll(bucket); } return sortedArray;

4. Menguji Kode Kita

Dengan implementasi kami selesai, mari tulis pengujian unit cepat untuk memastikannya berfungsi seperti yang diharapkan:

BucketSorter sorter = new IntegerBucketSorter(); List unsorted = Arrays.asList(80,50,60,30,20,10,70,0,40,500,600,602,200,15); List expected = Arrays.asList(0,10,15,20,30,40,50,60,70,80,200,500,600,602); List sorted = sorter.sort(unsorted); assertEquals(expected, sorted);

5. Kompleksitas Waktu

Selanjutnya, mari kita lihat sekilas kerumitan waktu melakukan pengurutan keranjang.

5.1. Skenario terburuk

Dalam skenario terburuk kami, kami akan menemukan semua elemen kami dalam keranjang yang sama dan dalam urutan terbalik. Saat kasus ini terjadi, kami mengurangi pengurutan keranjang menjadi pengurutan sederhana di mana setiap elemen dibandingkan dengan setiap elemen lainnya, menghasilkan kompleksitas waktu O (n²) .

5.2. Skenario Kasus Rata-rata

Dalam kasus rata-rata kami, kami menemukan bahwa elemen-elemennya relatif merata di antara keranjang masukan kami. Karena setiap langkah kami hanya memerlukan satu iterasi melalui keranjang masukan, kami menemukan bahwa jenis keranjang kami selesai dalam waktu O (n) .

6. Kesimpulan

Di artikel ini, kami melihat cara mengimplementasikan jenis ember di Java. Kami juga melihat kerumitan waktu dari algoritme pengurutan keranjang.

Seperti biasa, kode yang ditampilkan dalam artikel ini tersedia di GitHub.