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.
    counting-1
    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.
    counting-2
  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.
    counting-3

    counting-4


      counting-5

    İşlem sonucunda B dizimiz şu şekilde oluşmuştur:
     counting-6

 

Ö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

Tags: , | Categories: C | C++ | Algoritma