Algoritma Susun Baldi

Dalam tutorial ini, anda akan belajar bagaimana cara kerja baldi berfungsi. Anda juga akan dapati contoh contoh baldi yang berfungsi di C, C ++, Java dan Python.

Bucket Sort adalah teknik menyusun yang menyusun unsur-unsur dengan terlebih dahulu membahagikan elemen ke dalam beberapa kumpulan yang disebut baldi . Unsur-unsur di dalam setiap baldi disusun menggunakan algoritma penyortiran yang sesuai atau memanggil algoritma yang sama.

Beberapa baldi dibuat. Setiap baldi diisi dengan pelbagai elemen tertentu. Unsur-unsur di dalam baldi disusun menggunakan algoritma lain. Akhirnya, elemen baldi dikumpulkan untuk mendapatkan susunan yang disusun.

Proses penyusun baldi dapat difahami sebagai pendekatan mengumpulkan- sebar. Unsur-unsur pertama disebarkan ke dalam baldi kemudian unsur-unsur baldi disusun. Akhirnya, unsur-unsur dikumpulkan mengikut urutan.

Kerja Susun Baldi

Bagaimana Penyusun Baldi Berfungsi?

Misalkan, array input adalah: Input array
Buat susunan ukuran 10. Setiap slot array ini digunakan sebagai baldi untuk menyimpan elemen. Array di mana setiap kedudukan adalah baldi
Masukkan elemen ke dalam baldi dari larik. Unsur dimasukkan mengikut julat baldi.
Dalam kod contoh kami, kami mempunyai baldi yang masing-masing berkisar antara 0 hingga 1, 1 hingga 2, 2 hingga 3,… (n-1) hingga n.
Katakan, elemen input .23diambil. Ia didarabkan dengan size = 10(iaitu. .23*10=2.3). Kemudian, ia ditukar menjadi bilangan bulat (iaitu. 2.3≈2). Akhirnya, .23 dimasukkan ke dalam baldi-2 . Masukkan elemen ke dalam baldi dari array
Begitu juga, .25 juga dimasukkan ke dalam baldi yang sama. Setiap kali, nilai minimum nombor titik terapung diambil.
Sekiranya kita mengambil nombor bulat sebagai input, kita harus membaginya dengan selang (10 di sini) untuk mendapatkan nilai minimum.
Begitu juga elemen lain yang dimasukkan ke dalam baldi masing-masing. Masukkan semua elemen ke dalam baldi dari larik
Unsur-unsur setiap baldi disusun menggunakan salah satu algoritma penyusun stabil. Di sini, kami telah menggunakan quicksort (fungsi inbuilt). Susun elemen dalam setiap baldi
Unsur-unsur dari setiap baldi dikumpulkan.
Ia dilakukan dengan melakukan iterasi melalui baldi dan memasukkan elemen individu ke dalam array asal dalam setiap kitaran. Elemen dari baldi akan dipadamkan setelah disalin ke susunan asal. Kumpulkan elemen dari setiap baldi

Algoritma Susun Baldi

 bucketSort () create N bucket yang masing-masing dapat menampung julat nilai untuk semua baldi menginisialisasi setiap baldi dengan 0 nilai untuk semua baldi memasukkan elemen ke dalam baldi yang sesuai dengan julat untuk semua elemen urutan baldi di setiap baldi mengumpulkan elemen dari setiap baldi baldi akhirSusun

Contoh Python, Java dan C / C ++

Python Java C 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); )

Kerumitan

Kerumitan Kes Terburuk: Apabila terdapat unsur jarak dekat dalam larik, mereka kemungkinan diletakkan di dalam baldi yang sama. Ini boleh menyebabkan beberapa baldi mempunyai lebih banyak unsur daripada yang lain. Ini menjadikan kerumitan bergantung pada algoritma penyortiran yang digunakan untuk menyusun elemen baldi. Kerumitan menjadi lebih teruk apabila elemen berada dalam urutan terbalik. Sekiranya jenis penyisipan digunakan untuk menyusun elemen baldi, maka kerumitan masa menjadi .O(n²)

O(n²)
Kerumitan Kes Terbaik: O(n+k)
Ia berlaku apabila unsur-unsur diedarkan secara seragam di dalam baldi dengan bilangan elemen yang hampir sama di setiap baldi.
Kerumitan menjadi lebih baik sekiranya elemen di dalam baldi sudah disusun.
Sekiranya jenis penyisipan digunakan untuk menyusun unsur baldi maka kerumitan keseluruhan dalam kes terbaik akan menjadi linear iaitu. O(n+k). O(n)adalah kerumitan untuk membuat baldi dan O(k)kerumitan untuk menyusun unsur-unsur baldi menggunakan algoritma yang mempunyai kerumitan masa linear pada kes terbaik.
Kerumitan Kes Purata: O(n)
Ia berlaku apabila elemen diedarkan secara rawak dalam larik. Walaupun elemen tidak diedarkan secara seragam, jenis baldi berjalan dalam masa linear. Ini berlaku sehingga jumlah kotak ukuran baldi adalah linear dalam jumlah elemen.