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

counting sort algorithm 7343 تصویر

الگوریتم مرتب‌سازی شمارشی (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.

پیاده سازی الگوریتم 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; 
}

امتحان کنید

خروجی کد فوق:

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

امتحان کنید

خروجی:

-10 -5 -3 -1 0 5 8 10

نوشته الگوریتم مرتب سازی شمارشی (Counting Sort) اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.

درباره نویسنده: administrator

ممکن است دوست داشته باشید

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *