Kova Sıralama Algoritması

Bu eğiticide, kova sıralamanın nasıl çalıştığını öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da kova sıralamanın çalışma örneklerini bulacaksınız.

Kova Sıralama, öğeleri önce kova adı verilen birkaç gruba bölerek sıralayan bir sıralama tekniğidir . Her bir bölümün içindeki öğeler , uygun sıralama algoritmalarından herhangi biri kullanılarak veya aynı algoritmayı yinelemeli olarak çağırarak sıralanır.

Birkaç kova oluşturulur. Her kova belirli bir dizi elemanla doldurulur. Paketin içindeki öğeler, başka bir algoritma kullanılarak sıralanır. Son olarak, sıralı diziyi elde etmek için kepçenin öğeleri toplanır.

Kovalı sıralama süreci, dağıtarak toplama yaklaşımı olarak anlaşılabilir . Öğeler önce kovalara dağıtılır, ardından paketlerin öğeleri sıralanır. Son olarak, öğeler sırayla toplanır.

Kova Sıralamanın Çalışması

Kova Sıralama Nasıl Çalışır?

  1. Diyelim ki, girdi dizisi: Girdi dizisi
    10 boyutunda bir dizi yaratın. Bu dizinin her yuvası, öğeleri depolamak için bir kova olarak kullanılır. Her konumun bir kova olduğu dizi
  2. Dizideki paketlere öğeler ekleyin. Elemanlar, kepçe aralığına göre yerleştirilir.
    Örnek kodumuzda, her biri 0 - 1, 1 - 2, 2 - 3,… (n-1) - n arasında değişen kovalarımız var.
    Bir girdi elemanının .23alındığını varsayalım . size = 10(Yani .23*10=2.3) ile çarpılır . Daha sonra bir tam sayıya (yani 2.3≈2) dönüştürülür. Son olarak, .23 kova-2'ye yerleştirilir . Diziden bölümlere öğeler ekleme
    Benzer şekilde, .25 de aynı bölüme eklenir. Her seferinde kayan nokta numarasının taban değeri alınır.
    Tam sayıları girdi olarak alırsak, kat değerini elde etmek için onu aralığa (burada 10) bölmemiz gerekir.
    Benzer şekilde, diğer öğeler de ilgili kovalarına yerleştirilir. Dizideki tüm öğeleri kümelere ekle
  3. Her bir grubun öğeleri, kararlı sıralama algoritmalarından herhangi biri kullanılarak sıralanır. Burada, hızlı sıralama (dahili işlev) kullandık. Her bir paketteki öğeleri sıralayın
  4. Her bir kovadaki öğeler toplanır.
    Bu, kovada yineleyerek ve her döngüde orijinal diziye ayrı bir öğe ekleyerek yapılır. Paket içindeki öğe, orijinal diziye kopyalandığında silinir. Her kovadan öğeler toplayın

Kova Sıralama Algoritması

 packSort (), her biri tüm kepçeler için bir dizi değer tutabilen N kova oluşturur, her kepçeyi tüm kepçeler için 0 değeriyle başlatır, her kepçedeki tüm kepçeler için aralığa uyan kepçelere öğe yerleştirir, her bir kepçedeki öğeleri toplar kova sonu

Python, Java ve C / C ++ Örnekleri

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); )

Karmaşıklık

  • En Kötü Durum Karmaşıklığı: Dizide yakın aralıktaki öğeler olduğunda, bunlar büyük olasılıkla aynı kovaya yerleştirilir. Bu, bazı paketlerin diğerlerinden daha fazla öğeye sahip olmasına neden olabilir. Karmaşıklığın, paketin öğelerini sıralamak için kullanılan sıralama algoritmasına bağlı olmasını sağlar. Öğeler ters sırada olduğunda karmaşıklık daha da kötüleşir. Paketin öğelerini sıralamak için ekleme sıralaması kullanılırsa, zaman karmaşıklığı olur .O(n2)

    O(n2)
  • En İyi Durum Karmaşıklığı: O(n+k)
    Öğeler, her bir kovada neredeyse eşit sayıda öğeyle kovalara eşit olarak dağıtıldığında ortaya çıkar.
    Paketlerin içindeki öğeler önceden sıralanmışsa karmaşıklık daha da iyi hale gelir.
    Bir grubun öğelerini sıralamak için ekleme sıralaması kullanılırsa, en iyi durumda genel karmaşıklık doğrusal olacaktır, yani. O(n+k). O(n)kepçe yapmak için karmaşıklığı ve O(k)en iyi durumda doğrusal zaman karmaşıklığı olan algoritmalar kullanılarak kovanın elemanları sıralamak için karmaşıklığıdır.
  • Ortalama Durum Karmaşıklığı: O(n)
    Elemanlar dizide rastgele dağıtıldığında ortaya çıkar. Öğeler eşit olarak dağıtılmasa bile, kova sıralama doğrusal zamanda çalışır. Kova boyutlarının karelerinin toplamı, toplam eleman sayısında doğrusal olana kadar geçerlidir.

Kova Sıralama Uygulamaları

Kova sıralaması şu durumlarda kullanılır:

  • giriş, bir aralıkta eşit olarak dağıtılır.
  • kayan nokta değerleri var

Ilginç makaleler...