Paylaşım Noktası

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:

1. 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.
   
2. C dizisi, en soldaki birimden başlayarak n = n + (n-1) şeklinde artırılacak şekilde yeniden oluşturulur.
   
3. 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);
}

Ö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;
}

Kaynak:
en.wikipedia.org
net.pku.edu.cn

C, C++, Algoritma sıralama algoritmalaları, counting