مرتب‌سازی رتبه‌ای

مرتب‌سازی رتبه‌ای
رده	الگوریتم مرتب‌سازی
ساختمان داده	آرایه
کارایی بدترین حالت
کارایی بهترین حالت
کارایی متوسط
پیچیدگی فضایی

مرتب‌سازی رتبه‌ای (به انگلیسی: Rank sort) یا مرتب‌سازی سرشماری (به انگلیسی: Enumeration sort) یک الگوریتم مرتب‌سازی از مرتبه‌ی زمانی $O(n^{2})$ است که در آن برای مشخص کردن جایگاه هر عدد در لیست مرتب شده، تعداد عناصر کوچک‌تر از آن شمرده می‌شود.^[۱]

این الگوریتم با توجّه به این که ورودی در یک داده‌ساختار میانی ذخیره می‌شود، یک نوع مرتّب‌سازی توزیعی است.

تحلیل ویرایش

محاسبه‌ی رتبه‌ی هر عنصر در مرتب‌سازی رتبه‌ای

روش کار ویرایش

برای به دست آوردن رتبه‌ی هر عنصر، کافی است تعداد اعداد کوچک‌تر از آن را بشماریم. شکل مقابل، نمونه‌ای از این کار را نشان می‌دهد.

عملکرد ویرایش

مرتبه‌ی زمانی اجرای مرتب‌سازی رتبه‌ای در تمام حالت‌ها $O(n^{2})$ است؛ زیرا مستقل از مرتب بودن یا نبودن آرایه‌ی ورودی، محاسبه‌ی رتبه‌ی تمام عنصرها لازم است. با این حال، می‌توان با پردازش موازی زمان اجرا را بهبود داد. با استفاده از $n$ پردازنده، می‌توان زمان اجرا را به $O(n)$ رساند؛ در این حالت، هر پردازنده با اجرای یک حلقه، رتبه‌ی یک عنصر را محاسبه می‌کند. با وجود عملیاتی نبودن، می‌توان با استفاده از $n^{2}$ پردازنده زمان اجرای الگوریتم را تا $O(lg(n))$ هم کاهش داد.^[۲]

پیاده‌سازی ویرایش

پیاده‌سازی ترتیبی ویرایش

قطعه کد زیر، پیاده‌سازی ترتیبی مرتب‌سازی رتبه‌ای را به زبان پایتون نشان می‌دهد. در این قطعه، آرایه‌ی نامرتب Input به صورت مرتب شده در آرایه‌ی Output ذخیره می‌شود.

for i in range(n):
    rank = 0 # Number of elements less than Input[i]
    for j in range(n):
        if Input[j] < Input[i]:
            rank += 1
    Output[rank] = Input[i] # Put Input[i] in output array based on its rank

اگر لیست اولیه شامل اعداد تکراری باشد، قطعه کد بالا درست کار نمی‌کند؛ اما می‌توان با اعمال تغییراتی، این مشکل را برطرف کرد. قطعه کد زیر، نسخه‌ی بهبود یافته‌ی مرتب‌سازی رتبه‌ای را به زبان پایتون نشان می‌دهد.

Output = [None] * n

for i in range(n):
    rank = 0 # Number of elements less than Input[i]
    for j in range(n):
        if Input[j] < Input[i]:
            rank += 1
    
    while Output[rank] is not None: # As long as an element has the same rank
        rank += 1
    
    Output[rank] = Input[i] # Put Input[i] in output array based on its rank

پیاده‌سازی موازی ویرایش

روش‌های پیاده‌سازی موازی مرتب‌سازی رتبه‌ای

از آن جا که محاسبه کردن رتبه‌ی هر عنصر مستقل از عناصر دیگر است، می‌توان مرتب‌سازی رتبه‌ای را به صورت موازی پیاده‌سازی کرد. از دیدگاه تئوری، با این کار می‌توان زمان اجرای این الگوریتم را تا $O(1)$ کاهش داد. برای پیاده‌سازی موازی روش‌های مختلفی وجود دارد. دو تا از این روش‌ها عبارت‌اند از:

الف) عناصر آرایه را طوری بین پردازنده‌ها تقسیم کنیم که هر پردازنده، رتبه‌ی تعدادی از عناصر را محاسبه کند.

ب) آرایه به چند بخش تقسیم کنیم و در اختیار هر پردازنده قرار دهیم. هر پردازنده رتبه‌ی تمام عناصر را در لیستی که در اختیار دارد محاسبه می‌کند (رتبه‌ی جزئی). رتبه‌ی نهایی حاصل جمع رتبه‌های جزئی است.

قطعه کد زیر، پیاده‌سازی موازی مرتب‌سازی رتبه‌ای در زبان سی شارپ را نشان می‌دهد.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Ranksort
{
    class Ranksorter
    {
        private int[] unsorted_array,sorted_array;
        private int n;
        public int[] GetSortedList
        {
            get { return sorted_array; }
        }
        public Ranksorter(int[] unsorted,int num)
        {
            n = num;
            unsorted_array = new int[n];
            sorted_array = new int[n];
            Array.Copy(unsorted,unsorted_array,n);
            
        }
        public void Sort(int index)
        {
            int rank = 0;
            int inval = unsorted_array[index];
            //int j = index;
            for(int x=0;x<n;x++)
                if (
                     (unsorted_array[x] < inval) ||
                     ((unsorted_array[x] == inval) && x<index)
                   ) rank++;
                
            /*
            do
            {
                j = (j % (n-1))+1;
                
            } while (j==index);
             * */
            sorted_array[rank] = inval;
        }

        public void Print()
        {
            for (int i = 0; i < n; i++)
            {
                Console.Write(sorted_array[i].ToString() + " ");
            }
        }
        public void WriteTo(string path)
        {
            System.IO.StreamWriter wr = new System.IO.StreamWriter(path);
            for (int i = 0; i < n; i++)
            {
                wr.WriteLine(sorted_array[i].ToString());
            }
            wr.Dispose();
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            var sw = new System.Diagnostics.Stopwatch();
            
            Random rnd = new Random();
            int n = 90000;
            int[] A = new int[n];
            System.IO.StreamReader reader = new System.IO.StreamReader("input.in");
            for (int i = 0; i < n; i++) 
                A[i] = int.Parse(reader.ReadLine());
            reader.Dispose();
            Ranksorter rank_sorter = new Ranksorter(A,n);
            sw.Start();
            Parallel.For(0,n, (int k) => {rank_sorter.Sort(k); });
            sw.Stop();
            rank_sorter.WriteTo("result_sorted.txt");
            Console.WriteLine("\nElaspsed time : {0}" + sw.Elapsed.ToString());
            Console.WriteLine("\nArray size is {0}.",n);
            Console.ReadKey();
            
        }
    }
}

برای آسان‌تر شدن پردازش موازی، از یک آرایه‌ی واسط به نام آرایه‌ی رتبه‌ها (به انگلیسی: Rank array) استفاده می‌شود که در جایگاه iاُم آن، رتبه‌ی iامین عنصر آرایه‌ی ورودی قرار می‌گیرد. اگر این آرایه را با R نشان دهیم

Output[R[i]] = Input[i]

جستارهای وابسته ویرایش

الگوریتم‌های مرتب‌سازی

منابع ویرایش

↑ Donald E. Knuth (1998). The Art of Computer Programming: Volume 3 (2 ed.). Addison-Wesley. ISBN 0-201-89685-0. {{cite book}}: Cite has empty unknown parameter: |1= (help)
↑ Barry Wilkinson, Michael Allen (2005). Parallel Programming (2 ed.). Pearson Prentice Hall. ISBN 0-13-140563-2. {{cite book}}: Cite has empty unknown parameter: |1= (help)

پیوند به بیرون ویرایش

مرتب‌سازی رتبه‌ای به زبان سی
مرتب‌سازی رتبه‌ای و مرتب‌سازی پایه‌ای بایگانی‌شده در ۲۲ آوریل ۲۰۱۷ توسط Wayback Machine

[1] Donald E. Knuth (1998). The Art of Computer Programming: Volume 3 (2 ed.). Addison-Wesley. ISBN 0-201-89685-0. {{cite book}}: Cite has empty unknown parameter: |1= (help)

[2] Barry Wilkinson, Michael Allen (2005). Parallel Programming (2 ed.). Pearson Prentice Hall. ISBN 0-13-140563-2. {{cite book}}: Cite has empty unknown parameter: |1= (help)

[۱]

[۲]