Bu yazımızda sayma sıralama algoritmasını ele alacağız. Sayma sıralaması, belirli aralıklar arasındaki anahtarlara dayalı bir sıralama tekniğidir. Yazılım mühendislerine yönelik kodlama veya teknik görüşmelerde sıralama algoritmaları yaygın olarak sorulmaktadır. Bu nedenle konuyu tartışmak önemlidir.
piton veya
Bu sıralama tekniği, öğeleri karşılaştırarak sıralama yapmaz. Hashing gibi farklı anahtar değerleri olan nesneleri sayarak sıralama yapar. Bundan sonra, çıktı dizisindeki her nesnenin indeks konumunu hesaplamak için bazı aritmetik işlemler gerçekleştirir. Sayma sıralaması genel amaçlı bir sıralama algoritması olarak kullanılmaz.
Sayma sıralaması, aralık sıralanacak nesnelerin sayısından büyük olmadığında etkilidir. Negatif giriş değerlerini sıralamak için kullanılabilir.
Şimdi sayma sıralamasının algoritmasını görelim.
Algoritma
countingSort(array, n) // 'n' is the size of array max = find maximum element in the given array create count array with size maximum + 1 Initialize count array with all 0's for i = 0 to n find the count of every unique element and store that count at ith position in the count array for j = 1 to max Now, find the cumulative sum and store it in count array for i = n to 1 Restore the array elements Decrease the count of every restored element by 1 end countingSort
Sayma sıralama algoritmasının çalışması
Şimdi sayma sıralama algoritmasının çalışmasına bakalım.
Sayma sıralama algoritmasının çalışmasını anlamak için sıralanmamış bir diziyi ele alalım. Bir örnek üzerinden sayma sıralamasını anlamak daha kolay olacaktır.
Dizinin elemanları şöyle olsun:
1. Verilen dizideki maksimum elemanı bulun. İzin vermek maksimum maksimum eleman olsun.
2. Şimdi uzunluk dizisini başlatın maksimum + 1 0 elementin tamamına sahip. Bu dizi, verilen dizideki öğelerin sayısını depolamak için kullanılacaktır.
3. Şimdi her dizi elemanının sayısını count dizisindeki karşılık gelen indekste saklamamız gerekiyor.
Bir elemanın sayısı şu şekilde depolanacaktır - Dizi elemanı '4'ün iki kez göründüğünü, dolayısıyla eleman 4'ün sayısının 2 olduğunu varsayalım. Bu nedenle, 2, 4'te depolanır.busayım dizisinin konumu. Dizide herhangi bir öğe yoksa, 0'ı yerleştirin, yani dizide '3' öğesinin bulunmadığını varsayalım, bu nedenle 0, 3'te saklanacaktır.üçüncükonum.
java'da dizi.sort
Şimdi kümülatif toplamı saklayın saymak dizi elemanları. Öğeleri sıralanan dizinin doğru dizinine yerleştirmeye yardımcı olacaktır.
Benzer şekilde, count dizisinin kümülatif sayısı -
4. Şimdi orijinal dizinin her bir elemanının indeksini bulun
Elemanı yerine yerleştirdikten sonra sayısını bir azaltın. 2. öğeyi yerleştirmeden önce sayısı 2'ydi, ancak doğru konuma yerleştirdikten sonra 2. öğenin yeni sayısı 1'dir.
Benzer şekilde, sıralamadan sonra dizi elemanları -
git durumu -s
Artık dizi tamamen sıralanmıştır.
Sıralama karmaşıklığını sayma
Şimdi en iyi durum, ortalama durum ve en kötü durum sıralamasında sayma işleminin zaman karmaşıklığını görelim. Ayrıca sayma sıralamasının uzay karmaşıklığını da göreceğiz.
1. Zaman Karmaşıklığı
| Dava | Zaman | Karmaşıklık |
|---|---|---|
| En iyi senaryo | O(n + k) | |
| Ortalama Durum | O(n + k) | |
| En kötü durumda | O(n + k) |
Yukarıdaki tüm durumlarda, sayma sıralamasının zaman karmaşıklığı aynıdır. Bunun nedeni algoritmanın n+k öğelerin diziye nasıl yerleştirildiğine bakılmaksızın.
Sayma sıralaması karşılaştırmaya dayalı sıralama tekniklerinden daha iyidir çünkü sayma sıralamasında öğeler arasında karşılaştırma yoktur. Ancak tamsayılar çok büyük olduğunda sayma sıralaması kötü olur çünkü bu boyutta dizilerin oluşturulması gerekir.
2. Uzayın Karmaşıklığı
| Uzay Karmaşıklığı | Ç(maks) |
| Stabil | EVET |
- Sayma sıralamasının uzay karmaşıklığı O(max)'tır. Öğelerin aralığı ne kadar geniş olursa, alan karmaşıklığı da o kadar büyük olur.
Sayma sıralamasının uygulanması
Şimdi farklı programlama dillerinde sayma sıralama programlarını görelim.
Program: C dilinde sayma sıralamasını uygulayan bir program yazın.
#include int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 16 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; printf('%d ', a[i]); main() a[]="{" 11, 30, 24, 7, 31, }; n="sizeof(a)/sizeof(a[0]);" printf('before sorting are -
'); printarr(a, n); countsort(a, printf('
after return 0; pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-12.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 11 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; cout< <a[i]<<' '; main() a[]="{" 31, 11, 42, 7, 30, }; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting are -
'; printarr(a, n); countsort(a, cout<<'
after return 0; pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-13.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in C#.</p> <pre> using System; class CountingSort { static int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } static void countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 3 i++) { a[i]="output[i];" store the sorted elements into main array } static void printarr(int[] a, int n) * function to print i; for (i="0;" i < n; console.write(a[i] + ' '); main() int[] a="{" 43, 31, 2, 7, 10, 1, 5, 6, }; n="a.Length;" console.write('before sorting are -
'); printarr(a,n); countsort(a,n); console.write('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-14.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in Java.</p> <pre> class CountingSort { int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); //int max = 42; int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 41 i++) { a[i]="output[i];" store the sorted elements into main array } * function to print void printarray(int a[], int n) i; for (i="0;" i < n; system.out.print(a[i] + ' '); public static main(string args[]) a[]="{" 11, 30, 24, 7, 31, 16, 39, }; n="a.length;" countingsort c1="new" countingsort(); system.out.println('
before sorting are - c1.printarray(a, n); c1.countsort(a,n); system.out.println('
after system.out.println(); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-15.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in PHP.</p> <pre> <?php function getMax($a, $n) { $max = $a[0]; for($i = 1; $i $max) $max = $a[$i]; } return $max; //maximum element from the array } function countSort(&$a, $n) // function to perform counting sort { $LeftArray = array($n + 1); $max = getMax($a, $n); $count = array($max + 1); //create count array with size [max+1] for ($i = 0; $i <= $max; ++$i) { $count[$i] = 0; // Initialize count array with all zeros } for ($i = 0; $i < $n; $i++) // Store the count of each element { $count[$a[$i]]++; } for($i = 1; $i= 0; $i--) { $output[$count[$a[$i]] - 1] = $a[$i]; $count[$a[$i]]--; // decrease count for same numbers } for($i = 0; $i<$n; $i++) { $a[$i] = $output[$i]; //store the sorted elements into main array } } /* Function to print the array elements */ function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 9, 28, 22, 5, 29, 14, 37, 28, 9 ); $n = count($a); echo 'Before sorting array elements are - <br>'; printArray($a, $n); countSort($a,$n); echo ' <br> After sorting array elements are - <br>'; printArray($a, $n); ?> </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-16.webp" alt="Counting Sort"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed counting sort complexity, working, and implementation in different programming languages.</p> <hr></n;></=></pre></n;></=></pre></n;></=></pre></n;></=> Çıktı
ücretsiz ipconfig
Yani bu makaleyle ilgili. Umarım makale sizin için yararlı ve bilgilendirici olacaktır.
Bu makale sadece algoritma ile sınırlı değildi. Ayrıca sayma sıralama karmaşıklığını, çalışmasını ve farklı programlama dillerinde uygulanmasını da tartıştık.