Algoritma Jenis Keranjang

Dalam tutorial ini, Anda akan mempelajari cara kerja pengurutan ember. Selain itu, Anda akan menemukan contoh kerja pengurutan bucket di C, C ++, Java dan Python.

Bucket Sort adalah teknik pengurutan yang mengurutkan elemen dengan terlebih dahulu membagi elemen menjadi beberapa kelompok yang disebut keranjang . Elemen di dalam setiap keranjang diurutkan menggunakan salah satu algoritme pengurutan yang sesuai atau secara rekursif memanggil algoritme yang sama.

Beberapa ember dibuat. Setiap keranjang diisi dengan berbagai elemen tertentu. Elemen di dalam keranjang diurutkan menggunakan algoritme lain. Terakhir, elemen bucket dikumpulkan untuk mendapatkan array yang diurutkan.

Proses sortir ember dapat dipahami sebagai pendekatan pencar-berkumpul . Elemen-elemen tersebut pertama-tama disebarkan ke dalam kotak-kotak kemudian elemen-elemen kotak diurutkan. Akhirnya, elemen dikumpulkan secara berurutan.

Cara Kerja Jenis Bucket

Bagaimana Cara Kerja Bucket Sort?

  1. Misalkan, larik masukan adalah: Larik masukan
    Membuat larik berukuran 10. Setiap slot larik ini digunakan sebagai wadah untuk menyimpan elemen. Larik di mana setiap posisi adalah keranjang
  2. Sisipkan elemen ke dalam keranjang dari larik. Elemen-elemen tersebut dimasukkan sesuai dengan kisaran ember.
    Dalam kode contoh kami, kami memiliki keranjang yang masing-masing berkisar dari 0 hingga 1, 1 hingga 2, 2 hingga 3,… (n-1) hingga n.
    Misalkan, elemen input .23diambil. Ini dikalikan dengan size = 10(mis. .23*10=2.3). Kemudian, itu diubah menjadi integer (mis. 2.3≈2). Akhirnya, .23 dimasukkan ke dalam keranjang-2 . Menyisipkan elemen ke dalam keranjang dari larik
    Demikian pula, .25 juga dimasukkan ke dalam wadah yang sama. Setiap saat, nilai dasar dari angka floating point diambil.
    Jika kita mengambil bilangan bulat sebagai input, kita harus membaginya dengan interval (10 di sini) untuk mendapatkan nilai lantai.
    Demikian pula, elemen lain dimasukkan ke dalam keranjangnya masing-masing. Sisipkan semua elemen ke dalam keranjang dari larik
  3. Elemen setiap keranjang diurutkan menggunakan salah satu algoritme pengurutan yang stabil. Di sini, kami telah menggunakan quicksort (fungsi bawaan). Sortir elemen di setiap keranjang
  4. Elemen-elemen dari setiap ember dikumpulkan.
    Ini dilakukan dengan melakukan iterasi melalui bucket dan memasukkan elemen individu ke dalam array asli di setiap siklus. Elemen dari keranjang dihapus setelah disalin ke dalam larik asli. Kumpulkan elemen dari setiap ember

Algoritma Jenis Keranjang

 bucketSort () membuat N bucket yang masing-masing dapat menampung berbagai nilai untuk semua bucket menginisialisasi setiap bucket dengan nilai 0 untuk semua bucket, masukkan elemen ke dalam bucket yang sesuai dengan rentang untuk semua elemen sortir bucket di setiap bucket mengumpulkan elemen dari setiap bucket end bucketSort

Contoh Python, Java dan C / C ++

Python Java C ++ 
 # Bucket Sort in Python def bucketSort(array): bucket = () # Create empty buckets for i in range(len(array)): bucket.append(()) # Insert elements into their respective buckets for j in array: index_b = int(10 * j) bucket(index_b).append(j) # Sort the elements of each bucket for i in range(len(array)): bucket(i) = sorted(bucket(i)) # Get the sorted elements k = 0 for i in range(len(array)): for j in range(len(bucket(i))): array(k) = bucket(i)(j) k += 1 return array array = (.42, .32, .33, .52, .37, .47, .51) print("Sorted Array in descending order is") print(bucketSort(array)) 
 // Bucket sort in Java import java.util.ArrayList; import java.util.Collections; public class BucketSort ( public void bucketSort(float() arr, int n) ( if (n <= 0) return; @SuppressWarnings("unchecked") ArrayList() bucket = new ArrayList(n); // Create empty buckets for (int i = 0; i < n; i++) bucket(i) = new ArrayList(); // Add elements into the buckets for (int i = 0; i < n; i++) ( int bucketIndex = (int) arr(i) * n; bucket(bucketIndex).add(arr(i)); ) // Sort the elements of each bucket for (int i = 0; i < n; i++) ( Collections.sort((bucket(i))); ) // Get the sorted array int index = 0; for (int i = 0; i < n; i++) ( for (int j = 0, size = bucket(i).size(); j < size; j++) ( arr(index++) = bucket(i).get(j); ) ) ) // Driver code public static void main(String() args) ( BucketSort b = new BucketSort(); float() arr = ( (float) 0.42, (float) 0.32, (float) 0.33, (float) 0.52, (float) 0.37, (float) 0.47, (float) 0.51 ); b.bucketSort(arr, 7); for (float i : arr) System.out.print(i + " "); ) )
 // Bucket sort in C #include #include #define NARRAY 7 // Array size #define NBUCKET 6 // Number of buckets #define INTERVAL 10 // Each bucket capacity struct Node ( int data; struct Node *next; ); void BucketSort(int arr()); struct Node *InsertionSort(struct Node *list); void print(int arr()); void printBuckets(struct Node *list); int getBucketIndex(int value); // Sorting function void BucketSort(int arr()) ( int i, j; struct Node **buckets; // Create buckets and allocate memory size buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET); // Initialize empty buckets for (i = 0; i < NBUCKET; ++i) ( buckets(i) = NULL; ) // Fill the buckets with respective elements for (i = 0; i data = arr(i); current->next = buckets(pos); buckets(pos) = current; ) // Print the buckets along with their elements for (i = 0; i < NBUCKET; i++) ( printf("Bucket(%d): ", i); printBuckets(buckets(i)); printf(""); ) // Sort the elements of each bucket for (i = 0; i < NBUCKET; ++i) ( buckets(i) = InsertionSort(buckets(i)); ) printf("-------------"); printf("Bucktets after sorting"); for (i = 0; i < NBUCKET; i++) ( printf("Bucket(%d): ", i); printBuckets(buckets(i)); printf(""); ) // Put sorted elements on arr for (j = 0, i = 0; i data; node = node->next; ) ) return; ) // Function to sort the elements of each bucket struct Node *InsertionSort(struct Node *list) ( struct Node *k, *nodeList; if (list == 0 || list->next == 0) ( return list; ) nodeList = list; k = list->next; nodeList->next = 0; while (k != 0) ( struct Node *ptr; if (nodeList->data> k->data) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = nodeList; nodeList = tmp; continue; ) for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) ( if (ptr->next->data> k->data) break; ) if (ptr->next != 0) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = ptr->next; ptr->next = tmp; continue; ) else ( ptr->next = k; k = k->next; ptr->next->next = 0; continue; ) ) return nodeList; ) int getBucketIndex(int value) ( return value / INTERVAL; ) void print(int ar()) ( int i; for (i = 0; i data); cur = cur->next; ) ) // Driver code int main(void) ( int array(NARRAY) = (42, 32, 33, 52, 37, 47, 51); printf("Initial array: "); print(array); printf("-------------"); BucketSort(array); printf("-------------"); printf("Sorted array: "); print(array); return 0; )
 // Bucket sort in C++ #include #include using namespace std; #define NARRAY 7 // Array size #define NBUCKET 6 // Number of buckets #define INTERVAL 10 // Each bucket capacity struct Node ( int data; struct Node *next; ); void BucketSort(int arr()); struct Node *InsertionSort(struct Node *list); void print(int arr()); void printBuckets(struct Node *list); int getBucketIndex(int value); // Sorting function void BucketSort(int arr()) ( int i, j; struct Node **buckets; // Create buckets and allocate memory size buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET); // Initialize empty buckets for (i = 0; i < NBUCKET; ++i) ( buckets(i) = NULL; ) // Fill the buckets with respective elements for (i = 0; i data = arr(i); current->next = buckets(pos); buckets(pos) = current; ) // Print the buckets along with their elements for (i = 0; i < NBUCKET; i++) ( cout << "Bucket(" << i << ") : "; printBuckets(buckets(i)); cout << endl; ) // Sort the elements of each bucket for (i = 0; i < NBUCKET; ++i) ( buckets(i) = InsertionSort(buckets(i)); ) cout << "-------------" << endl; cout << "Bucktets after sorted" << endl; for (i = 0; i < NBUCKET; i++) ( cout << "Bucket(" << i << ") : "; printBuckets(buckets(i)); cout << endl; ) // Put sorted elements on arr for (j = 0, i = 0; i data; node = node->next; ) ) for (i = 0; i next; free(tmp); ) ) free(buckets); return; ) // Function to sort the elements of each bucket struct Node *InsertionSort(struct Node *list) ( struct Node *k, *nodeList; if (list == 0 || list->next == 0) ( return list; ) nodeList = list; k = list->next; nodeList->next = 0; while (k != 0) ( struct Node *ptr; if (nodeList->data> k->data) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = nodeList; nodeList = tmp; continue; ) for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) ( if (ptr->next->data> k->data) break; ) if (ptr->next != 0) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = ptr->next; ptr->next = tmp; continue; ) else ( ptr->next = k; k = k->next; ptr->next->next = 0; continue; ) ) return nodeList; ) int getBucketIndex(int value) ( return value / INTERVAL; ) // Print buckets void print(int ar()) ( int i; for (i = 0; i < NARRAY; ++i) ( cout << setw(3) << ar(i); ) cout << endl; ) void printBuckets(struct Node *list) ( struct Node *cur = list; while (cur) ( cout << setw(3)  next; ) ) // Driver code int main(void) ( int array(NARRAY) = (42, 32, 33, 52, 37, 47, 51); cout << "Initial array: " << endl; print(array); cout << "-------------" << endl; BucketSort(array); cout << "-------------" << endl; cout << "Sorted array: " << endl; print(array); )

Kompleksitas

  • Kompleksitas Kasus Terburuk: Jika ada elemen dengan jarak dekat dalam larik, mereka kemungkinan besar akan ditempatkan di keranjang yang sama. Hal ini dapat mengakibatkan beberapa keranjang memiliki lebih banyak elemen daripada yang lain. Itu membuat kerumitan bergantung pada algoritme pengurutan yang digunakan untuk mengurutkan elemen bucket. Kompleksitas menjadi lebih buruk ketika elemen berada dalam urutan terbalik. Jika penyisipan semacam digunakan untuk mengurutkan elemen keranjang, kompleksitas waktu menjadi .O(n2)

    O(n2)
  • Kompleksitas Kasus Terbaik: O(n+k)
    Ini terjadi ketika elemen didistribusikan secara seragam dalam bucket dengan jumlah elemen yang hampir sama di setiap bucket.
    Kompleksitas menjadi lebih baik jika elemen di dalam bucket sudah diurutkan.
    Jika penyisipan semacam digunakan untuk mengurutkan elemen ember maka keseluruhan kompleksitas dalam kasus terbaik akan linier yaitu. O(n+k). O(n)adalah kerumitan untuk membuat bucket dan O(k)merupakan kerumitan untuk menyortir elemen bucket menggunakan algoritme yang memiliki kerumitan waktu linier pada kasus terbaik.
  • Average Case Complexity: O(n)
    Ini terjadi ketika elemen didistribusikan secara acak dalam array. Meskipun elemen tidak didistribusikan secara seragam, pengurutan keranjang berjalan dalam waktu linier. Ini berlaku sampai jumlah kuadrat ukuran bucket linier dalam jumlah total elemen.

Aplikasi Jenis Bucket

Jenis ember digunakan jika:

  • masukan didistribusikan secara seragam pada suatu rentang.
  • ada nilai floating point

Artikel yang menarik...