Bu eğitimde, sıralamanın nasıl çalıştığını öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da sayma sıralaması için çalışma örnekleri bulacaksınız.
Sayma sıralaması, dizideki her benzersiz öğenin oluşum sayısını sayarak bir dizinin öğelerini sıralayan bir sıralama algoritmasıdır. Sayım, bir yardımcı dizide depolanır ve sıralama, sayıyı yardımcı dizinin bir indeksi olarak eşleyerek yapılır.
Sayma Sıralaması Nasıl Çalışır?
maxVerilen diziden maksimum elemanı (öyle olmasına izin verin ) bulun .
Verilen dizimax+1Tüm öğeler 0 ile bir uzunluk dizisi başlatın. Bu dizi, dizideki öğelerin sayısını saklamak için kullanılır.
Dizi say- Her öğenin sayısını
countdizideki ilgili dizininde saklayın
Örneğin: öğe 3'ün sayısı 2 ise, 2, count dizisinin 3. konumunda saklanır. Dizide "5" öğesi yoksa, 0, 5. konumda saklanır.
Depolanan her bir öğenin sayısı - Count dizisinin öğelerinin kümülatif toplamını depolar. Öğelerin sıralanan dizinin doğru dizinine yerleştirilmesine yardımcı olur.
Kümülatif sayım - Count dizisindeki orijinal dizinin her bir öğesinin dizinini bulun. Bu, kümülatif sayımı verir. Öğeyi aşağıdaki şekilde gösterildiği gibi hesaplanan dizine yerleştirin.
Sıralama sayma - Her öğeyi doğru konumuna yerleştirdikten sonra, sayısını bir azaltın.
Sıralama Algoritmasını Sayma
countingSort (dizi, boyut) max <- dizideki en büyük öğeyi bul, her benzersiz öğenin toplam sayısını bulmak için j <- 0 için tümü sıfır olan count dizisini başlat ve i <- 1 için count dizisindeki jth dizindeki sayımı sakla maks. kümülatif toplamı bulmak ve onu count dizisinde saklamak için j <- boyut 1'e kadar öğeleri diziye geri yükleyin, geri yüklenen her öğenin sayısını 1 azaltın
Python, Java ve C / C ++ Örnekleri
Python Java C C ++ # Counting sort in Python programming def countingSort(array): size = len(array) output = (0) * size # Initialize count array count = (0) * 10 # Store the count of each elements in count array for i in range(0, size): count(array(i)) += 1 # Store the cummulative count for i in range(1, 10): count(i) += count(i - 1) # Find the index of each element of the original array in count array # place the elements in output array i = size - 1 while i>= 0: output(count(array(i)) - 1) = array(i) count(array(i)) -= 1 i -= 1 # Copy the sorted elements into original array for i in range(0, size): array(i) = output(i) data = (4, 2, 2, 8, 3, 3, 1) countingSort(data) print("Sorted Array in Ascending Order: ") print(data)
// Counting sort in Java programming import java.util.Arrays; class CountingSort ( void countSort(int array(), int size) ( int() output = new int(size + 1); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); // Initialize count array with all zeros. for (int i = 0; i < max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Driver code public static void main(String args()) ( int() data = ( 4, 2, 2, 8, 3, 3, 1 ); int size = data.length; CountingSort cs = new CountingSort(); cs.countSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Counting sort in C programming #include void countingSort(int array(), int size) ( int output(10); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) // The size of count must be at least (max+1) but // we cannot declare it as int count(max+1) in C as // it does not support dynamic memory allocation. // So, its size is provided statically. int count(10); // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countingSort(array, n); printArray(array, n); )
// Counting sort in C++ programming #include using namespace std; void countSort(int array(), int size) ( // The size of count must be at least the (max+1) but // we cannot assign declare it as int count(max+1) in C++ as // it does not support dynamic memory allocation. // So, its size is provided statically. int output(10); int count(10); int max = array(0); // Find the largest element of the array for (int i = 1; i max) max = array(i); ) // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countSort(array, n); printArray(array, n); )
Karmaşıklık
Zaman Karmaşıklıkları:
Esas olarak dört ana döngü vardır. (En büyük değeri bulmak, işlevin dışında yapılabilir.)
| döngü için | sayma zamanı |
|---|---|
| 1 inci | O (maks.) |
| 2. | O (boyut) |
| 3 üncü | O (maks.) |
| 4. | O (boyut) |
Genel karmaşıklık = O(max)+O(size)+O(max)+O(size)=O(max+size)
- En Kötü Durum Karmaşıklığı:
O(n+k) - En İyi Durum Karmaşıklığı:
O(n+k) - Ortalama Durum Karmaşıklığı:
O(n+k)
Yukarıdaki tüm durumlarda, karmaşıklık aynıdır çünkü öğeler diziye nasıl yerleştirilirse yerleştirilsin, algoritma n+kzamanlardan geçer .
Herhangi bir öğe arasında karşılaştırma yoktur, bu nedenle karşılaştırmaya dayalı sıralama tekniklerinden daha iyidir. Ancak, tam sayıların çok büyük olması kötüdür çünkü bu büyüklükte dizi yapılmalıdır.
Uzay Karmaşıklığı:
Sayma Sıralamasının uzay karmaşıklığı O(max). Öğe aralığı ne kadar büyükse, alan karmaşıklığı da o kadar büyük olur.
Sıralama Uygulamalarını Sayma
Sayma sıralaması şu durumlarda kullanılır:
- birden çok sayıya sahip daha küçük tam sayılar vardır.
- doğrusal karmaşıklık ihtiyaçtır.
