Counting sort veri kümesinde (sayılardan oluşuyor) yer alan elemanların aralığını kullanarak sıralama yapan vir sıralama algoritmasıdır. 1954 yılında Harold H. Seward tarafından yarılmıştır. Counting sort çalışması sırasında giren dizi haricinde 2 tane boş dizi yaratır. A: Sıralanacak elemanların bulunduğu dizi B: Sıralanmış dizi C: A dizisindeki tekrarlanan eleman sayısını tutan dizi   Algoritmanın uygulanışı şu şekildedir: A dizisindeki elemanlar tek tek dolaşılarak B dizisi doldurulur. Mesela; A dizinde 1 elemanında 2 tane bulunmaktadır, 2 elamanından hiç yoktur. C dizisi, en soldaki birimden başlayarak n = n + (n-1) şeklinde artırılacak şekilde yeniden oluşturulur. Bu adımda A dizisinin elemanları sondan başlayarak taranmaya başlanır. Her elemanın içeriği kontrol edilerek C dizisindeki karşılığı bulunur. Bu karşılık A dizinden aldığımız elemanı B dizisinin hangi gözüne yazmamız gerektiğini gösteriyor.   İşlem sonucunda B dizimiz şu şekilde oluşmuştur:     Örnek C kodu: void counting_sort(int *array, int size) { int i, min, max; min = max = array[0]; for(i = 1; i < size; i++) { if (array[i] < min) min = array[i]; else if (array[i] > max) max = array[i]; } int range = max - min + 1; int *count = (int *) malloc(range * sizeof(int)); for(i = 0; i < range; i++) count[i] = 0; for(i = 0; i < size; i++) count[ array[i] - min ]++; int j, z = 0; for(i = min; i <= max; i++) for(j = 0; j < count[ i - min ]; j++) array[z++] = i; free(count); } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Örnek C++ kodu: #include <iostream> #include <vector> using namespace std; void countingSort(vector<int>& Array) { int Min, Max; Min = Max = Array[0]; for(int i = 1; i < Array.size(); i ++) { if(Array[i] < Min) Min = Array[i]; if(Array[i] > Max) Max = Array[i]; } int Range = Max - Min + 1; vector<int> Count; Count.resize(Range); for(int i = 0; i < Range; i ++) Count[i] = 0; for(int i = 0; i < Array.size(); i ++) Count[Array[i] - Min] ++; int Index = 0; for(int i = Min; i <= Max; i ++) for(int j = 0; j < Count[i - Min]; j ++) Array[Index ++] = i; } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Kaynak: en.wikipedia.org net.pku.edu.cn Tags: , | Categories: C | C++ | Algoritma