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

همچنین ببینید: مقایسه الگوریتم‌های مرتب‌سازی

الگوریتم مرتب‌سازی، در دانش رایانه و ریاضی، الگوریتمی است که فهرستی از داده‌ها را به ترتیبی مشخص می‌چیند.

پرکاربردترین ترتیب‌ها، ترتیب‌های عددی و واژه‌نامه‌ای هستند. مرتب‌سازی کارا در بهینه سازی الگوریتم‌هایی که به فهرست‌های مرتب شده نیاز دارند (مثل جستجو و ترکیب) اهمیت زیادی دارد.

از آغاز علم رایانه مسائل مرتب‌سازی بررسی‌های فراوانی را متوجه خود ساختند، شاید به این علت که در عین ساده بودن، حل آن به صورت کارا پیچیده است. برای نمونه مرتب‌سازی حبابی در سال ۱۹۵۶ به وجود آمد. در حالی که بسیاری این را یک مسئلهٔ حل شده می‌پندارند، الگوریتم کارآمد جدیدی همچنان ابداع می‌شوند (مثلاً مرتب‌سازی کتاب خانه‌ای در سال ۲۰۰۴ مطرح شد).

مبحث مرتب‌سازی در کلاس‌های معرفی علم رایانه بسیار پرکاربرد است، مبحثی که در آن وجود الگوریتم‌های فراوان به آشنایی با ایده‌های کلی و مراحل طراحی الگوریتم‌های گوناگون کمک می‌کند؛ مانند تحلیل الگوریتم، داده‌ساختارها، الگوریتم‌های تصادفی، تحلیل بدترین و بهترین حالت و حالت میانگین، هزینهٔ زمان و حافظه، و حد پایین.

محتویات

۱ طبقه‌بندی
۲ مرتب‌سازی حبابی
۳ مرتب سازی انتخابی
۴ مرتب سازی درجی
۵ مرتب سازی پایه‌ای (مبنایی)
۶ مرتب‌سازی سطلی
۷ مرتب سازی هرمی
۸ مرتب سازی شل
۹ مرتب سازی سریع
۱۰ مرتب سازی ادغامی
۱۱ مرتب سازی درجی
۱۲ مرتب سازی بوگو
۱۳ فهرست الگوریتم‌های مرتب‌سازی
۱۴ پانویس
۱۵ جستارهای وابسته
۱۶ منابع

طبقه‌بندی [ویرایش]

در علم کامپیوتر معمولاً الگوریتم‌های مرتب‌سازی بر اساس این معیارها طبقه‌بندی می‌شوند:

پیچیدگی (بدترین و بهترین عملکرد و عملکرد میانگین)

با توجه به اندازهٔ فهرست (n). در مرتب‌سازی‌های معمولی عملکرد خوب (O(n log n و عملکرد بد (O(n^۲ است. بهترین عملکرد برای مرتب‌سازی (O(n است. الگوریتم‌هایی که فقط از مقایسهٔ کلیدها استفاده می‌کنند در حالت میانگین حداقل (O(n log n مقایسه نیاز دارند.

حافظه (و سایر منابع کامپیوتر)

بعضی از الگوریتم‌های مرتب‌سازی «در جا^[۱]» هستند. یعنی به جز داده‌هایی که باید مرتب شوند، حافظهٔ کمی ((O(۱) مورد نیاز است؛ در حالی که سایر الگوریتم‌ها به ایجاد مکان‌های کمکی در حافظه برای نگه‌داری اطلاعات موقت نیاز دارند.

پایداری^[۲]

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

مقایسه‌ای بودن یا نبودن

در یک مرتب‌سازی مقایسه‌ای داده‌ها فقط با مقایسه به وسیلهٔ یک عملگر مقایسه مرتب می‌شوند.

روش کلی

درجی، جابجایی، گزینشی، ترکیبی و غیره. جابجایی مانند مرتب‌سازی حبابی و مرتب‌سازی سریع و گزینشی مانند مرتب‌سازی پشته‌ای.

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

مرتب‌سازی حبابی [ویرایش]

نوشتار اصلی: مرتب‌سازی حبابی

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

این مرتب‌سازی از آن رو که برای کار با عناصر آن‌ها را با یکدیگر می‌سنجد، یک مرتب‌سازی بر مبنای مقایسه‌است.

با فرض داشتن n عضو در لیست، در بدترین حالت $n (n - 1) / 2$ عمل لازم خواهد بود.

یک آرایه با مقادیر “5, 1, 4, 2, 8” را در نظر بگیرید. آن را به ترتیب صعودی با استفاده از مرتب سازی حبابی مرتب می‌کنیم.

گذر اول:

(1, 5, 4, 2, 8) <= (5, 1, 4, 2, 8)

در اینجا الگوریتم دو عنصر اول را مقایسه، و جابجا می‌کند.


(1, 4, 5, 2, 8) <= (1, 5, 4, 2, 8)
(1, 4, 2, 5, 8) <= (1, 4, 5, 2, 8)
(1, 2, 4, 5, 8) <= (1, 4, 2, 5, 8)

حالا آرایه مرتب شده‌است، ولی الگوریتم هنوز نمی‌داند که این کار کامل انجام شده‌است یا نه، که برای فهمیدن احتیاج به یک گذر کامل بدون هیچ جابجایی (swap) داریم:
گذردوم

(1, 2, 4, 5, 8) <= (1, 2, 4, 5, 8)
(1, 2, 4, 5, 8) <= (1, 2, 4, 5, 8)
(1, 2, 4, 5, 8) <= (1, 2, 4, 5, 8)
(1, 2, 4, 5, 8) <= (1, 2, 4, 5, 8)

در نهایت آرایه مرتب شده‌است و الگوریتم می‌تواند پایان پذیرد. بیان سادهٔ شبه کد مرتب‌سازی حبابی:

procedure bubbleSort(A: list of sortable items) defined as:
do
swapped:= false
for each i in 0 to length(A) - 2 inclusive do:
if A[ i ]> A[ i + 1 ] then
swap(A[ i ], A[ i + 1 ])
swapped:= true
end if
end for
while swapped
end procedure

مرتب سازی انتخابی [ویرایش]

نوشتار اصلی: الگوریتم مرتب‌سازی انتخابی

(به انگلیسی: Selection Sort)‏

معمولاً اطلاعات و داده‌های خامی که در اختیار برنامه نویس قرار دارد بصورت نامرتب هستند. مواقعی پیش می‌آید که لازم است این داده‌ها بر حسب فیلد خاصی مرتب بشوند؛ مانند لیست دانش آموزان بر حسب معدل، لیست کارمندان بر حسب شماره پرسنلی، لیست دفترچه تلفن بر حسب نام خانوادگی و... روشهای متعددی برای مرتب سازی وجود دارد. برای شروع روش مرتب سازی انتخابی (Selection Sort):

روش انتخابی اولین روشی است که به ذهن می‌رسد: بزرگ‌ترین رکورد بین رکوردهای لیست را پیدا می‌کنیم و به انتهای لیست انتقال می‌دهیم. از بقیه رکوردها بزرگ‌ترین را انتخاب می‌کنیم و انتهای لیست - کنار رکورد قبلی - قرار می‌دهیم و... مثلا:

۰:  ۹ ۱ ۶ ۴ ۷ ۳ ۵

۱:  ۵ ۱ ۶ ۴ ۷ ۳ ۹

۲:  ۵ ۱ ۶ ۴ ۳ ۷ ۹

۳:  ۵ ۱ ۳ ۴ ۶ ۷ ۹

۴:  ۴ ۱ ۳ ۵ ۶ ۷ ۹

۵:  ۳ ۱ ۴ ۵ ۶ ۷ ۹

۶:  ۱ ۳ ۴ ۵ ۶ ۷ ۹

پیاده سازی (مرتب سازی انتخابی) در ++C

void selection_sort (int arr[] , int n)
{
  register int i , j;
  int max , temp;
  for (i = n-1 ; i > 0 ; i--)
  {
    max = 0;
    for (j = 1 ; j <= i ; j++)
      if (arr[max] < arr[j])
        max = j;
    temp = arr[i];
    arr[i] = arr[max];
    arr[max] = temp;
  }
}

کد مرتب سازی انتخابی همراه با جستجوی باینری به زبان ++C

#include <iostream.h>
 
using namespace std;
/*** functions definition ***/
int selectionSort(int __array[], int arrayLength);
int binerySearch(int __array[], int arrayLength, int __target);
 
int main()
{
   // declear arrays
   int numArray[] = {0, 9, 8, 10 , 2, 1};
   // sort arrays
   selectionSort(numArray, 6);
   // print arrays
   cout<<"Selection sort:"<<endl;
   for (int i = 0; i < 6; i++) cout<<numArray[i]<<endl;
   if (binerySearch(numArray, 6, 2) != -1)
      cout<<"Your target index is: "<<binerySearch(numArray, 6, 2)<<endl;
   else
      cout<<"Not found !"<<endl;
   return 0;
}
 
int selectionSort(int __array[], int arrayLength) // unstable
{
   for (int i = 0; i < arrayLength; i++)
      for (int j = 0; j < arrayLength - 1; j++)
          if (__array[j] < __array[j + 1])
          {
             // swap the parameters
             int __tmp = __array[j + 1];
             __array[j + 1] = __array[j];
             __array[j] = __tmp;
          }
    return 0;
}
 
int binerySearch(int __array[], int arrayLength, int __target) // you must sort the array first
{
    int currentIndex = 0, arrayBegin = 0, arrayEnd = arrayLength;
    do
    {
        currentIndex = (arrayBegin + arrayEnd) / 2;
        if (__array[currentIndex] == __target)
           return currentIndex;
        else if (__array[currentIndex] > __target)
           arrayEnd = arrayBegin + 1;
        else if (__array[currentIndex] < __target)
           arrayBegin = arrayEnd + 1;
    } while (arrayEnd > arrayBegin);
    return -1;
}

مرتب سازی درجی [ویرایش]

نوشتار اصلی: الگوریتم مرتب‌سازی درجی

(به انگلیسی: Insertion Sort)‏

در مرتب سازی درجی، ابتدا عنصر دوم با عنصر اول لیست مقایسه می‌شود و در صورت لزوم با عنصر اول جابجا می‌شود به طوری که عناصر اول و دوم تشکیل یک لیست مرتب دوتایی را بدهند. سپس عنصر سوم به ترتیب با دو عنصر قبلی خود یعنی عناصر دوم و اول مقایسه و درجای مناسبی قرار می‌گیرد به طوری که عناصر اول و دوم و سوم تشکیل یک لیست مرتب سه تایی را بدهند.سپس عنصر چهارم به ترتیب با سه عنصر قبلی خود یعنی عنصرسوم و دوم و اول مقایسه و درجای مناسب قرار می‌گیرد به طوری که عناصر اول و دوم و سوم و چهارم تشکیل یک لسیت مرتب چهارتایی را بدهند و در حالت کلی عنصر امم با ام منهای یک عنصر قبلی خود مقایسه می‌گردد تا در مکان مناسب قرار گیرد به طوری که ام عنصر تشکیل یک لیست مرتب ام تایی را بدهند و این روند تا مرتب شدن کامل لیست ادامه می‌یابد. یا به صورت دقیق تر
مرحله 1:[1]A خودش به طور بدیهی مرتب است.
مرحله 2:[2]A را یا قبل از یا بعد از [1]A درج می‌کنیم طوری که [1]A و [2]A مرتب شوند.
مرحله 3:[3]A را در مکان صحیح در [1]A و [2]A درج می‌کنیم به گونه‌ای که [1]Aو [2]A و[3]A مرتب شده باشند.
مرحله A[n]:n را در مکان صحیح خود در [1]Aو [2]A و... و[A[n-1 به گونه‌ای درج می‌کنیم که کل آرایه مرتب باشد.
زمان اجرای الگوریتم مرتب سازی درجی از(O(n^2 است.
این الگوریتم از الگوریتم‌های پایدار می‌باشد و در یک آرایهٔ کاملا مرتب بهترین حالت را دارد و برای یک آرایهٔ مرتب شده معکوس بدترین حالت را دارد.
ثابت شده‌است که برای ام های کوچکتر از بیست مرتب سازی درجی سریع ترین روش مرتب سازی است.
پیاده سازی (مرتب سازی درجی) در ++C

void Insertion_sort (int A[] , int n)
{
  int i , j ,temp;
  for (i =1 ; i <n ; i++)
  {
    temp = A[i];
    for (j = i ; j>0 && A[j-1]>temp ; j--)
      A[j]=A[j-1];
    A[j]=temp;
  }
}

مرتب سازی پایه‌ای (مبنایی) [ویرایش]

(به انگلیسی: radix sort)‏

نوشتار اصلی: الگوریتم مرتب‌سازی پایه‌ای

مرتب سازی مبنایی الگوریتمی است که لیستی با اندازهٔ ثابت و اعضایی با طول k را در زمان (O(kn اتجام می‌دهد. ورودی‌ها را به بخش‌های کوچکی تقسیم می‌کنیم(اگر یک کلمه‌است آن را به حرف‌هایش می‌شکنیم و اگر عدد است آن را به ارقامش) سپس ابتدا لیست را بر اساس کم ارزش ترین بیت(حرف یا رقم) مرتب می‌کنیم، سپس بر اساس دومین بیت، تا در نهایت بر اساس پرارزش ترین بیت. به این ترتیب پس از k مرحله لیست مرتب می‌شود.
این روش مرتب سازی پایدار است و در تهیهٔ واژه نامه‌ها و مرتب سازی اعداد استفاده می‌شود.
مرتبهٔ اجرایی این الگوریتم در بهترین حالت از(O(nlgn و در بدترین حالت از(O(n^2 است.
پیاده سازی radix sort


{

  int i , j , k ;

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

  {

    for (j = ۰ ; j <n ; j++)
{

       k=ith digit of x[j];

    place x[j] at rear of q[k];

 }
for (j=0;j<10;j++)
place element of q[j] in next sequential position of x;

}

مرتب‌سازی سطلی [ویرایش]

ایدهٔ مرتب‌سازی سطلی (bucket sort) این است که بازهٔ (1و0] را به زیربازه‌هایی با سایز یکسان تقسیم می‌کند و سپس ورودیها را در این زیربازه‌ها توزیع می‌کنیم(در واقع این ورودی‌ها با توجه به مقدارشان در این زیربازه‌ها قرار می‌گیرند). اگر ورودی‌ها توزیعی یکنواخت داشته باشند، انتظار داریم که هر عدد در یک زیربازه قرار گرفته باشد. برای تولید خروجی، اعداد داخل هر زیربازه را به یک روش مرتب سازی (معمولا مرتب سازی درجی به دلیل کارایی خوب در مرتب سازی تعداد کم ورودی)مرتب می‌کنیم. سپس داده‌های مرتب شدهٔ هر زیربازه در کنار هم قرار می‌دهیم.
شبه کد bucket sort


1.n<-length [A]

2.for i=1 to n do

3.  insert A[i] into list B[nA[i]]

4.for i=0 to n-1 do

5.  sort list B with Insertion sort

6.concatenate the list B[0],B[1],...B[n-1] together in order.

مرتب سازی هرمی [ویرایش]

نوشتار اصلی: الگوریتم مرتب‌سازی هرمی

(به انگلیسی: Heap Sort)‏

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

پیچیدگی آن همواره از(O(nlgn است. و بر خلاف مرتب سازی سریع به صورت بازگشتی نیست.
در این روش درخت heap روی آرایه ساخته می‌شود.
این الگوریتم پایدار نمی‌باشد.

مرتب سازی شل [ویرایش]

نوشتار اصلی: الگوریتم مرتب‌سازی شل

(به انگلیسی: Shell Sort)‏

نام این الگوریتم از نام مخترع آن گرفته شده‌است. در این الگوریتم از روش درج استفاده می‌شود.

به عنوان مثال رشته f d a c b e را تحت این الگوریتم مرتب می‌کنیم.


           F     d   a    c    b    e            : شروع

           C     b   a    f    d    e            : مرحله اول

           A     b   c    d    e    f            : مرحله دوم

           A     b   c    d    e    f            : نتیجه

در مرحله اول: داده‌های با فاصله ۳ از یکدیگر، مقایسه و مرتب شده، در مرحله دوم
داده‌های با فاصله ۲ از یکدیگر، مقایسه و مرتب می‌شوند  و در مرحله دوم داده‌ها با
فاصله یک از یکدیگر مقایسه و مرتب می‌شوند.

منظور از فاصله سه این است که عنصر اول با عنصر چهارم(۳+۱)، عنصر دوم با عنصر پنجم(۵=۳+۲) و عنصر سوم با عنصر ششم(۶=۳+۳) مقایسه شده در جای مناسب خود قرار می‌گیرد.

برای انتخاب فاصله در اولین مرحله، تعداد عناصر لیست بر ۲ تقسیم می‌شود(n/۲) وفاصله بعدی نیز با تقسیم فاصله فعلی بر ۲ حاصل می‌گردد و الگریتم تا زمانی ادامه پیدا می‌کند که این فاصله به صفر برسد.

برای نمونه اگر تعداد عناصر برابر با ۱۰ باشد، فاصله در مرحله اول برابر با ۵، در مرحله دوم برابر با ۲ ور در مرحله سوم برابر با ۱ و در نهایت برابر با صفر خواهد بود.

زمان مرتب سازی shell  از رابطه n       پیروی می‌کند که نسبت به    n^۲  بهبود
خوبی پیدا کرده‌است لذا  سرعت عمل روش مرتب سازی شل از روشهای  انتخابی، در جی

و حبابی بیشتر است.

پیاده سازی مرتب سازی شل)) در c++:

# include<stdio.h>
# include<conio.h>

<include<string.h#

Void shell(int *, char*, int)
Int main()

{

            Char s[80];

            Int gap[80];

           (); Clrscr

           ;(«: Printf(» Enter a string

       ); Gets(s

       )); Shell(gap,s,strlen(s

       ); Printf(«\n the sorted string is: %s»,s

            Getch();

            Return ۰;

}
**************************** //

Void shell(int gap [], char * item, int count)
{

                Register int I, j, step, k, p;

               ; Char x

                Gap[۰] =count /2;

                While(gap[k]> 1)

{

 ++; K

Gap[k]=gap[k-1]/2;

}//end of while

For (i= 0; i<=k; i++)

{

Step=gap[i];

For(j=step; j<count; j++)

{

X=item[j];

P=j-step;

             While(p>=0 &&  x<item[p])

{

Item[p+step]=item[p];

P=p-step;

}

Item[p+step]=x;

      }

}

}

مرتب سازی سریع [ویرایش]

نوشتار اصلی: الگوریتم مرتب‌سازی سریع

(به انگلیسی: Quick Sort)‏

مرتب سازی سریع (Quick Sort) از جمله روشهای محبوب و با سرعت بالا برای مرتب کردن داده‌ها محسوب می‌شه. این روش هم مثل روش ادغام از تقسیم و حل (Divide and Conqure) برای مرتب کردن داده‌ها استفاده می‌کنه. به این ترتیب که داده‌ها رو به دو قسمت مجزا تقسیم، و با مرتب کردن اونها کل داده‌ها رو مرتب می‌کنه. برای اینکار یکی از داده‌ها (مثلاً داده اول) به عنوان محور انتخاب می‌شه. داده‌ها بر اساس محور طوری چینش می‌شن که همه داده‌های کوچک‌تر از محور سمت چپ و داده‌های بزرگ‌تر یا مساوی اون سمت راستش قرار می‌گیرن. با مرتب کردن دو قسمت به دست اومده کل داده‌ها مرتب می‌شن. در این حالت مثل روش ادغام نیازی به ادغام کردن داده‌ها نیست. چرا که قسمت سمت راست همگی از قسمت سمت چپ کوچک‌تر هستن و بالعکس. مثلاً اعداد صحیح زیر رو در نظر بگیرید:


۵  ۶  ۱  ۹  -۲  ۴  ۵  ۱۵  ۳  ۱  ۴  ۱۰

عدد ۵ رو به عنوان محور در نظر می‌گیریم. داده‌ها به این صورت بازچینی می‌شن:


۱  -۲  ۴  ۳  ۱  ۴  ۵  ۶  ۹  ۵  ۱۵  ۱۰

همانطور که مشاهده می‌کنید اعداد سمت چپ عدد ۵ زیر خط دار همگی از ۵ کوچیکتر و اعداد سمت راست بزرگ‌تر یا مساوی اون هستند.

پیاده سازی مرتب سازی Quick sort)) در c++

تابع partition با دریافت آرایه و حد بالا و پایین تکه‌ای که باید تقسیم بشه عملیات لازم رو انجام می‌ده، و اندیس محل تفکیک رو (محل عدد ۵ در مثال بالا) به عنوان نتیجه بر می‌گردونه.

int partition (int arr[ ] , int low , int high)

{

 int lb = low + 1 , rb = high , temp , pivot = arr[ low ] , p;

 while (lb <= rb)

 {

  while (arr[ lb ] <= pivot && lb <= rb)

   lb++;

  while (arr[ rb ]> pivot && lb <= rb)

   rb--;

  if (lb <rb)

  {

   temp = arr[ lb];

   arr[ lb ] = arr[ rb];

   arr[ rb ] = temp;

 }

}

 (if (rb == high

  p = high;

else if(rb == low)

  p = low;

 else

  p = lb – 1;

 arr[ low ] = arr[ p];

 arr[ p ] = pivot;

 return p;

}

اگه این تابع رو برای مثال بالا استفاده کنیم مقدار ۶ (اندیس ۵ زیرخط دار) برگشت داده می‌شه. با تکرار کردن این عملیات برای دو قسمت به دست اومده (در مثال بالا از اندیس صفر تا ۵ و از اندیس ۷ تا ۱۱) داده‌ها به صورت کامل مرتب می‌شن.

بر اساس گفته‌های بالا تابع مرتب سازی به این صورت خواهد بود:

void quick_sort (int arr[ ] , int low , int high)

{
if (low <high)

 {

  int p = partition(arr , low , high);

  quick_sort(arr , low , p – 1);

  quick_sort(arr , p + 1 , high);

}

}

همونطور که مشاهده می‌کنید این تابع بصورت بازگشتی نوشته شده. در صورتی که بخواید به صورت غیر بازگشتی بنویسید باید از پشته به صورت زیر استفاده کنید:

void quick_sort (int arr[ ] ,int n)

{

 stack st;

 st.push(0);

 st.push(n – 1);

 int low , p , high;

 while(! st.isempty())

 {

  high = st.pop();

  low = st.pop();

  p = partition(arr , low , high);

  if (p> low)

  {

   st.push(low);

   st.push(p – 1);

 }

  if (p <high)

 {

   st.push(p + 1);

   st.push(high);

 }

}

}

مرتب سازی ادغامی [ویرایش]

نوشتار اصلی: الگوریتم مرتب‌سازی ادغامی

(به انگلیسی: Merge Sort)‏

روش مرتب سازی ادغامی از الگوریتم تقسیم و حل (divide-and-conquer) و همچنین ادغام برای مرتب کردن داده‌ها استفاده می‌کند. در این الگوریتم مساله به چند جزء کوچک‌تر تقسیم می‌شود. هر کدوم از این قسمت‌ها رو به طور مجزا حل کرده، و با ترکیب اونها به مساله اصلی می‌رسیم. و اما طرح کلی مرتب سازی ادغام:

در این روش داده‌ها به دو قسمت مساوی تقسیم می‌شوند. و هر کدوم از این قسمت‌ها - به صورت بازگشتی - مرتب، و با ادغام آنها دادها بصورت کامل مرتب می‌شوند.اما توجه به این نکته ضروری است که اگر پس از یک بار تقسیم باز هم لیستهای ایجاد شده بزرگ باشند ، می توانیم برای هر زیر لیست مراحل بالا را دوباره انجام دهیم تا به زیر لیستهایی با تنها 1 عضو برسیم و واضح است که لیست تک عنصری خود مرتب است.

کلاس merge sort در #C که وظیفه ی آن مرتب سازی n کلید به ترتیب غیر نزولی است:

   class margesort
    {
        public void marge_sort(ref int[] arr, int low, int high)
        {
            if (low <high)
            {
                int mid = (low + high) / 2;
                marge_sort(ref arr, low, mid);
                marge_sort(ref arr, mid + 1 , high);
                merge(ref arr, low, mid, high);
           }
       }
        void merge(ref int[] arr, int low, int mid, int high)
        {
            int i, j, a, b;
            j = low;
            for (i = mid + 1; i <= high; i++)
            {
                for (; arr[j] <= arr[i] && j <i; j++) ;
                if (j!= i)
                {
                    b = arr[i];
                    for (a = i; a> j; a--)
                        arr[a] = arr[a - 1];
                    arr[j] = b;
               }
                else
                    break;
           }

       }
   }

پیاده سازی مرتب سازی Merge sort در ++C :


void merge_sort (int arr[ ] , int low , int high)

{

 if (low>= high)
  return;

 int mid = (low + high) / 2;

 merge_sort (arr , low , mid);

 merge_sort (arr , mid + 1 , high);

 merge_array (arr , low , mid , high);

}
procedure merge_sort (var arr: array of integer ; l: integer ; h: integer);
var

 m: integer;

begin

 if l>= h then

  exit;

 m:= (l + h) div 2;

 merge_sort (arr , l , m);

 merge_sort (arr , m + 1 , h);

 merge_array (arr , l , m , h);

end;

این توابع اونقدر ساده هستن که نیاز به هیچ توضیحی ندارن. فقط می‌مونه تابع merge_array که دو زیر آرایه رو با هم ادغام می‌کنه.


void merge (int arr[ ] , int low , int mid , int high)
{

 register int i , j , k , t;

 j = low;

 for (i = mid + 1 ; i <= high ; i++)

 {

  while (arr[ j ] <= arr[ i ] && j <i)

   j++;

  if (j == i)

   break;

  t = arr[ i];

  for (k = i ; k> j ; k--)

   arr[ k ] = arr[ k – 1];

  arr[ j ] = t;

}

}

procedure merge_array (var arr: array of integer ; l: integer ; m: integer ; h: integer);

var

 i , j , k , t: integer;

begin

 j:= l;

 for i:= m + 1 to h do

 begin

  while (arr[ j ] <= arr[ i ]) and (j <i) do

   inc (j);

  if j = i then

   break;

  t:= arr[ i];

  for k:= i downto j + 1 do

   arr[ k ]:= arr[ k – 1];

  arr[ j ]:= t;

 end;

End;

تابع merge_array خود آرایه و اندیسهای بالا، پایین و جداکننده زیر آرایه‌ای رو که باید ادغام بشه دریافت می‌کنه، و به صورت درجا (بدون استفاده از آرایه کمکی) دو قمست مرتب شده زیر آرایه رو ادغام می‌کنه.

مثالی در این مورد را مشاهده می کنید :

مرتب سازی درجی [ویرایش]

نوشتار اصلی: الگوریتم مرتب‌سازی درجی

(به انگلیسی: Insertion Sort)‏

مرتب سازی درجی یکی از روشهای مرتب سازی رایج و البته نه چندان کارا محسوب می‌شه. این روش در مقایسه با مرتب سازی حبابی و انتخابی سرعت بهتری داره و برای مرتب کردن تعداد کمی از عناصر مناسبه. به همین خاطر مراخل انتهایی روش مرتب سازی سریع با کمک گرفتن از این روش انجام می‌گیره.

الگوریتم مرتب سازی درجی بر اساس مرتب سازیهایی که معمولاً خود ما بصورت دستی انجام می‌دیم طراحی شده. فرض کنید دسته کارتی با شماره‌های ۱ تا ۱۰ بصورت نامرتب و کنار هم روی زمین چیده شدن:

۵ ۲ ۹ ۳ ۱ ۱۰ ۴ ۶ ۸ ۷

کارت دوم رو نسبت به کارت اول در جای مناسب خودش قرار می‌دیم:

۲ ۵ ۹ ۳ ۱ ۱۰ ۴ ۶ ۸ ۷

حالا نوبت به کارت سوم می‌رسه. این کارت رو نسبت به دو کارت قبلی در جای مناسب قرار می‌دیم. چون ۹ در مقایسه با ۲ و ۵ جای درستی داره بدون هیچ جابجایی به کارت چهارم می‌رسیم. جای این کارت رو نسبت به سه کارت قبلی مشخص می‌کنیم:

۲ ۳ ۵ ۹ ۱ ۱۰ ۴ ۶ ۸ ۷

و به همین ترتیب تا آخر ادامه می‌دیم.

اگه n تعداد عناصر رو مشخص کنه، این روش n - ۱ مرحله رو برای مرتب کردن طی می‌کنه. بعد از اتمام مرحله i ام مطمئنا i + ۱ عنصر اول به صورت مرتب شده هستن (قسمتی که زیرشون خط کشیده شده). این مساله یکی از حسنهای مرتب سازی درجی محسوب می‌شه: در هر مرحله حتما قطعه‌ای از عناصر مرتب شذه هستن. مرتب سازی حبابی این ویژگی رو نداره.

پیاده سازی(مرتب سازی درجی) در c++


void insertion_sort (int arr[ ] , int n)

{

  register int i , j , t;

 (++ for (i = 1 ; i <n ; i

 }

  ]; t = arr[ i

   (-- for (j = i ; j> 0 && arr[ j - 1 ]>= t ; j

     ; arr[ j ] = arr[ j - 1 ]

    arr[ j ] = t;

 }

}

۷ - مرتب سازی Heep Sort))

یک الگوریتم مرتب سازی در حافظه (RAM) می‌باشد. Heap یک درخت دودویی کامل است با ارتفاع Height = ëlog nû هر گره (node) یک کلید بیشتر ندارد که بزرگ‌تر یا برابر کلید گره پدر (parent) می‌باشد. بصورت یک آرایه (Array) ذخیره می‌شود. برای هر گره (i) فرزندان آن در گره‌های (۲i) و (۲i+۱) ذخیره شده‌اند. پدر هر گره (j) در گره (j/۲) می‌باشد.

الگوریتم Insert در Heap Sort چگونه‌است؟

۱) رکورد جدید در آخر Heap اضافه می‌شود.

۱) کلید آن با کلید گره پدر مقایسه می‌شود و اگر مقدار آن کوچک‌تر بود محل آن با محل گره پدر تعویض می‌شود.

۱) در صورت لزوم عمل (۲) تا ریشه درخت (Root) ادامه می‌یابد.

الگوریتم Remove در Heap Sort چگونه‌است؟ ۱) کوچک‌ترین کلید که در گره Root می‌باشد خارج می‌شود. ۲) بزرگ‌ترین کلید (آخرین گره) به گره Root منتقل می‌گردد. ۳) کلید آن با کوچک‌ترین کلید فرزند مقایسه می‌شود و اگر بیشتر بود جای آن دو تعویض می‌شود. ۴) در صورت لزوم عمل (۳) تا آخر Heap تکرار می‌گردد.

مرتب سازی بوگو [ویرایش]

نوشتار اصلی: مرتب‌سازی بوگو

(به انگلیسی: Bugo Sort)‏ در علوم کامپیوتر، مرتب سازی بوگو (که به آن مرتب سازی تصادفی، مرتب سازی میمونی هم میگویند) یک روش غیر موثر در الگوریتم‌های مرتب سازی محسوب می‌شود. از این مرتب سازی برای اهداف آموزشی در تقابل با دیگر روش‌های واقع گرایانه در مرتب سازی به کار می‌رود. اگر در مرتب سازی دسته‌ای از کارت‌ها از مرتب سازی بوگو استفاده شود، بدین صورت خواهد بود که ابتدا بررسی می‌شود که آیا لیست مرتب است یا خیر. اگر نبود، دوباره ترتیب کارت‌ها را تغییر می‌دهیم، و پردازه قبلی را دوباره اجرا می‌کنیم تا زمانی که به یک لیست مرتب از کارت‌ها برسیم. نام این مرتب سازی از واژه bogus به معنای جعلی و ساختگی آمده‌است.

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


while not InOrder(deck)
  do Shuffle(deck);

زمان اجرای این مرتب سازی با فاکتوریل و توابع فرانمایی super-exponential می‌توان بیان کرد. نکته مهم در این است که بدترین حالت ممکن آن می‌تواند زمان اجرای بی نهایت داشته باشد.
زمان اجرا در بدترین حالت در بی نهایت، در حالت میانگین در (O(n!.n و در حالت کمینه در (O(n خواهد بود.

فهرست الگوریتم‌های مرتب‌سازی [ویرایش]

در این جدول، n تعداد داده‌ها و k تعداد داده‌ها با کلیدهای متفاوت است. ستون‌های بهترین، میانگین و بدترین، پیچیدگی در هر حالت را نشان می‌دهد و حافظه بیانگر مقدار حافظهٔ کمکی (علاوه بر خود داده‌ها) است.

نام	بهترین	میانگین	بدترین	حافظه	پایدار	مقایسه‌ای	روش	توضیحات
مرتب سازی حبابی (Bubble sort)	(O(n	—	(O(n^۲	(O(۱	بله	بله	جابجایی	Times are for best variant
Cocktail sort	(O(n	—	(O(n^۲	(O(۱	بله	بله	جابجایی
Comb sort	(O(n log n	—	(O(n log n	(O(۱	خیر	بله	جابجایی
Gnome sort	(O(n	—	(O(n^۲	(O(۱	بله	بله	جابجایی
Selection sort	(O(n^۲	(O(n^۲	(O(n^۲	(O(۱	خیر	بله	گزینشی
Insertion sort	(O(n	—	(O(n^۲	(O(۱	بله	بله	درجی
Shell sort	(O(n log n	—	(O(n log^۲n	(O(۱	خیر	بله	درجی	Times are for best variant
Binary tree sort	(O(n log n	—	(O(n log n	(O(۱	بله	بله	درجی
Library sort	(O(n	(O(n log n	(O(n^۲	ε+۱)n)	بله	بله	درجی
Merge sort	(O(n log n	—	(O(n log n	(O(n	بله	بله	Merging
In-place merge sort	(O(n log n	—	(O(n log n	(O(۱	بله	بله	Merging	Times are for best variant
Heapsort	(O(n log n	—	(O(n log n	(O(۱	خیر	بله	گزینشی
Smoothsort	(O(n	—	(O(n log n	(O(۱	خیر	بله	گزینشی
Quicksort	(O(n log n	(O(n log n	(O(n^۲	(O(n	خیر	بله	Partitioning	Naive variants use (O(n space
Introsort	(O(n log n	(O(n log n	(O(n log n	(O(n	خیر	بله	Hybrid
Pigeonhole sort	(O(n+k	—	(O(n+k	(O(k	بله	خیر	Indexing
Bucket sort	(O(n	(O(n	(O(n^۲	(O(k	بله	خیر	Indexing
Counting sort	(O(n+k	—	(O(n+k	(O(n+k	بله	خیر	Indexing
Radix sort	(O(nk	—	(O(nk	(O(n	بله	خیر	Indexing
Patience sorting	(O(n	—	(O(n log n	(O(n	خیر	بله	درجی	تمام زیر دنباله‌های صعودی را با (O(n log (log(n پیدا می‌کند.

این جدول الگوریتم‌هایی را توضیح می‌دهد که به علت اجرای بسیار ضعیف و یا نیاز به سخت‌افزار خاص، کاربرد زیادی ندارند.

نام	بهترین	میانگین	بدترین	حافظه	پایدار	مقایسه‌ای	توضیحات
Bogosort	(O(n	O(n × n!)	بدون حد	(O(۱	خیر	بله
Stooge sort	(O(n^۲٫۷۱	—	(O(n^۲٫۷۱	(O(۱	خیر	بله
Bead sort	(O(n	—	(O(n	—	N/A	خیر	به سخت‌افزار مخصوص نیاز دارد.
Pancake sorting	(O(n	—	(O(n	—	خیر	بله	به سخت‌افزار مخصوص نیاز دارد.
Sorting networks	(O(log n	—	(O(log n	—	بله	بله	Requires a custom circuit of size (O(log n

پانویس [ویرایش]

^ inplace
^ stability

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

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

منابع [ویرایش]

Wikipedia contributors, «Sorting algorithm», Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/wiki/Sorting_algorithm

[۱]

[۲]

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

محتویات

طبقه‌بندی [ویرایش]

مرتب‌سازی حبابی [ویرایش]

مرتب سازی انتخابی [ویرایش]

مرتب سازی درجی [ویرایش]

مرتب سازی پایه‌ای (مبنایی) [ویرایش]

مرتب‌سازی سطلی [ویرایش]

مرتب سازی هرمی [ویرایش]

مرتب سازی شل [ویرایش]

مرتب سازی سریع [ویرایش]

مرتب سازی ادغامی [ویرایش]

مرتب سازی درجی [ویرایش]

مرتب سازی بوگو [ویرایش]

فهرست الگوریتم‌های مرتب‌سازی [ویرایش]

پانویس [ویرایش]

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

منابع [ویرایش]

منوی ناوبری

ابزارهای شخصی

گویش‌ها

فضاهای نام

جستجو

عملکردها

بازدیدها

گشتن

چاپ/برون‌بری

جعبه‌ابزار

به زبان‌های دیگر