الگوریتم مرتب سازی شمارشی (Counting Sort)

یکشنبه ۱۹ آبان ۱۳۹۸
بازدید ۴,۴۸۵ نفر
آرتین
(14 امتیاز از 3 رای)
Loading...

تصویر counting-sort-algorithm_7343 الگوریتم مرتب سازی شمارشی (Counting Sort)

الگوریتم مرتب‌سازی شمارشی (Counting Sort)

الگوریتم مرتب سازی شمارشی (Counting Sort)، یک تکنیک مرتب سازی مبتنی بر کلیدهای بین یک رنج خاص است. در این الگوریتم برخلاف الگوریتم هایی مثل Merge Sort که مبتنی بر مقایسه هستند، برای مرتب سازی از تکنیک شمارش عناصر آرایه استفاده می کند.

برای درک بهتر به مثال زیر توجه کنید:

For simplicity, consider the data in the range 0 to 9.
Input data: 1, 4, 1, 2, 7, 5, 2
  1) Take a count array to store the count of each unique object.
  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     0  2  2  0   1  1  0  1  0  0

  2) Modify the count array such that each element at each index
  stores the sum of previous counts.
  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     0  2  4  4  5  6  6  7  7  7

The modified count array indicates the position of each object in
the output sequence.

  3) Output each object from the input sequence followed by
  decreasing its count by 1.
  Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2.
  Put data 1 at index 2 in output. Decrease count by 1 to place
  next data 1 at an index 1 smaller than this index.

For simplicity, consider the data in the range 0 to 9.

Input data: 1, 4, 1, 2, 7, 5, 2

1) Take a count array to store the count of each unique object.

Index: 0 1 2 3 4 5 6 7 8 9

Count: 0 2 2 0 1 1 0 1 0 0

2) Modify the count array such that each element at each index

stores the sum of previous counts.

Index: 0 1 2 3 4 5 6 7 8 9

Count: 0 2 4 4 5 6 6 7 7 7

The modified count array indicates the position of each object in

the output sequence.

3) Output each object from the input sequence followed by

decreasing its count by 1.

Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2.

Put data 1 at index 2 in output. Decrease count by 1 to place

next data 1 at an index 1 smaller than this index.

پیاده سازی الگوریتم Counting Sort

در زیر می توانید نحوه پیاده سازی الگوریتم مرتب سازی شمارشی در زبان برنامه نویسی سی پلاس پلاس را مشاهده کنید:

// C++ Program for counting sort 
#include<bits/stdc++.h> 
#include<string.h>
using namespace std; 
#define RANGE 255 
// The main function that sort 
// the given string arr[] in 
// alphabatical order 
void countSort(char arr[]) 
{ 
    // The output character array 
    // that will have sorted arr 
    char output[strlen(arr)]; 
    // Create a count array to store count of inidividul 
    // characters and initialize count array as 0 
    int count[RANGE + 1], i; 
    memset(count, 0, sizeof(count)); 
    // Store count of each character 
    for(i = 0; arr[i]; ++i) 
        ++count[arr[i]]; 
    // Change count[i] so that count[i] now contains actual 
    // position of this character in output array 
    for (i = 1; i <= RANGE; ++i) 
        count[i] += count[i-1]; 
    // Build the output character array 
    for (i = 0; arr[i]; ++i) 
    { 
        output[count[arr[i]]-1] = arr[i]; 
        --count[arr[i]]; 
    } 
    /* 
    For Stable algorithm 
    for (i = sizeof(arr)-1; i>=0; --i) 
    { 
        output[count[arr[i]]-1] = arr[i]; 
        --count[arr[i]]; 
    } 
    For Logic : See implementation 
    */
    // Copy the output array to arr, so that arr now 
    // contains sorted characters 
    for (i = 0; arr[i]; ++i) 
        arr[i] = output[i]; 
} 
// Driver  code
int main() 
{ 
    char arr[] = "CFGBCAFygbG";
    countSort(arr); 
    cout<< "Sorted character array is " << arr; 
    return 0; 
}

// C++ Program for counting sort

#include<bits/stdc++.h>

#include<string.h>

using namespace std;

#define RANGE 255

// The main function that sort

// the given string arr[] in

// alphabatical order

void countSort(char arr[])

{

// The output character array

// that will have sorted arr

char output[strlen(arr)];

// Create a count array to store count of inidividul

// characters and initialize count array as 0

int count[RANGE + 1], i;

memset(count, 0, sizeof(count));

// Store count of each character

for(i = 0; arr[i]; ++i)

++count[arr[i]];

// Change count[i] so that count[i] now contains actual

// position of this character in output array

for (i = 1; i <= RANGE; ++i)

count[i] += count[i-1];

// Build the output character array

for (i = 0; arr[i]; ++i)

{

output[count[arr[i]]-1] = arr[i];

--count[arr[i]];

}

For Stable algorithm

for (i = sizeof(arr)-1; i>=0; --i)

{

output[count[arr[i]]-1] = arr[i];

--count[arr[i]];

}

For Logic : See implementation

// Copy the output array to arr, so that arr now

// contains sorted characters

for (i = 0; arr[i]; ++i)

arr[i] = output[i];

}

// Driver code

int main()

{

char arr[] = "CFGBCAFygbG";

countSort(arr);

cout<< "Sorted character array is " << arr;

return 0;

}

امتحان کنید

خروجی کد فوق:

Sorted character array is ABCCFFGGbgy

1	Sorted character array is ABCCFFGGbgy

نکات

پیچیدگی زمانی الگوریتم برابر است با O(n+k) که در آن n تعداد عناصر آرایه ورودی و k رنج ورودی است.
پیچیدگی فضایی برابر است با O(n+k).

مشکلی که پیاده سازی بالا دارد این است که اگر آرایه ورودی شامل مقادیر منفی باشد، نمی توانیم آن را مرتب کنیم. چون هیچ اندیسی برای اعداد منفی وجود ندارد. برای حل این مشکل می توانید آن را به شکل زیر پیاده سازی کنید.

//Counting sort which takes negative numbers as well
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void countSort(vector <int>& arr)
{
    int max = *max_element(arr.begin(), arr.end());
    int min = *min_element(arr.begin(), arr.end());
    int range = max - min + 1;
    vector<int> count(range), output(arr.size());
    for(int i = 0; i < arr.size(); i++)
        count[arr[i]-min]++;
    for(int i = 1; i < count.size(); i++)
           count[i] += count[i-1];
    for(int i = arr.size()-1; i >= 0; i--)
    {
         output[ count[arr[i]-min] -1 ] = arr[i];
              count[arr[i]-min]--;
    }
    for(int i=0; i < arr.size(); i++)
            arr[i] = output[i];
}
void printArray(vector <int> & arr)
{
    for (int i=0; i < arr.size(); i++)
        cout << arr[i] << " ";
    cout << "\n";
}
int main()
{
    vector<int> arr = {-5, -10, 0, -3, 8, 5, -1, 10};
    countSort (arr);
    printArray (arr);
    return 0;
}