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

الگوریتم مرتب‌سازی ، در دانش رایانه و ریاضی، الگوریتمی است که فهرستی از داده‌ها را به ترتیبی مشخص می‌چیند.
پرکاربردترین ترتیب‌ها، ترتیب‌های عددی و واژه‌نامه‌ای هستند. مرتب‌سازی کارا در بهینه‌سازی الگوریتم‌هایی که به فهرست‌های مرتب شده نیاز دارند (مثل جستجو و ترکیب) اهمیت زیادی دارد.
از آغاز علم رایانه مسائل مرتب‌سازی بررسی‌های فراوانی را متوجه خود ساختند، شاید به این علت که در عین ساده بودن، حل آن به صورت کارا پیچیده است. برای نمونه مرتب‌سازی حبابی در سال ۱۹۵۶ به وجود آمد. در حالی که بسیاری این را یک مسئله حل شده می‌پندارند، الگوریتم کارآمد جدیدی همچنان ابداع می‌شوند (مثلا مرتب‌سازی کتاب‌خانه‌ای در سال ۲۰۰۴ مطرح شد).
مبحث مرتب‌سازی در کلاس‌های معرفی علم رایانه بسیار پرکاربرد است، مبحثی که در آن وجود الگوریتم‌های فراوان به آشنایی با ایده‌های کلی و مراحل طراحی الگوریتم‌های گوناگون کمک می‌کند؛ مانند تحلیل الگوریتم، داده‌ساختارها، الگوریتم‌های تصادفی، تحلیل بدترین و بهترین حالت و حالت میانگین، هزینه زمان و حافظه، و حد پایین.
طبقه‌بندی
در علم کامپیوتر معمولا الگوریتم‌های مرتب‌سازی بر اساس این معیارها طبقه‌بندی می‌شوند:
پیچیدگی (بدترین و بهترین عملکرد و عملکرد میانگین)
با توجه به اندازه فهرست (n). در مرتب‌سازی‌های معمولی عملکرد خوب (O(n log n و عملکرد بد (O(n ۲ است. بهترین عملکرد برای مرتب‌سازی (O(n است. الگوریتم‌هایی که فقط از مقایسه کلیدها استفاده می‌کنند در حالت میانگین حداقل (O(n log n مقایسه نیاز دارند.
حافظه (و سایر منابع کامپیوتر)
بعضی از الگوریتم‌های مرتب‌سازی «در جا» هستند. یعنی به جز داده‌هایی که باید مرتب شوند، حافظه کمی ((O(۱) مورد نیاز است؛ در حالی که سایر الگوریتم‌ها به ایجاد مکان‌های کمکی در حافظه برای نگه‌داری اطلاعات موقت نیاز دارند.
پایداری
الگوریتم‌های مرتب‌سازی پایدار ترتیب را بین داده‌های دارای کلیدهای برابر حفظ می‌کنند. فرض کنید می‌خواهیم چند نفر را بر اساس سن با یک الگوریتم پایدار مرتب کنیم. اگر دو نفر با نام‌های الف و ب هم‌سن باشند و در لیست اولیه الف جلوتر از ب آمده باشد، در لیست مرتب شده هم الف جلوتر از ب است.
مقایسه‌ای بودن یا نبودن
در یک مرتب‌سازی مقایسه‌ای داده‌ها فقط با مقایسه به وسیله یک عملگر مقایسه مرتب می‌شوند.
روش کلی
درجی، جابجایی، گزینشی، ترکیبی و غیره. جابجایی مانند مرتب‌سازی حبابی و مرتب‌سازی سریع و گزینشی مانند مرتب‌سازی پشته‌ای.
مرتب‌سازی حبابی
مرتب‌سازی حبابی یک الگوریتم مرتب‌سازی ساده‌است که لیست را پشت سرهم پیمایش می‌کند تا هر بار عناصر کنارهم را با هم سنجیده و اگر در جای نادرست بودند جابه‌جایشان کند. در این الگوریتم این کار باید تا زمانی که هیچ جابه‌جایی در لیست رخ ندهد، ادامه یابد و در آن زمان لیست مرتب شده‌است. این مرتب‌سازی از آن رو حبابی نامیده می‌شود که هر عنصر با عنصر کناری خود سنجیده‌شده و درصورتی که از آن کوچک‌تر باشد جای خود را به آن می‌دهد و این کار همچنان پیش می‌رود تا کوچک‌ترین عنصر به پایین لیست برسد و دیگران نیز به ترتیب در جای خود قرار گیرند (یا به رتبه‌ای بالاتر روند یا به پایین‌تر لیست رانده شوند) این عمل همانند پویش حباب به بالای مایع است.
این مرتب‌سازی از آن رو که برای کار با عناصر آن‌ها را با یکدیگر می‌سنجد، یک مرتب‌سازی بر مبنای مقایسه‌است.
با فرض داشتن n عضو در لیست، در بدترین حالت عمل لازم خواهد بود.
یک آرایه با مقادیر “۵, ۱, ۴, ۲, ۸” را در نظر بگیرید. آن را به ترتیب صعودی با استفاده از مرتب‌سازی حبابی مرتب می‌کنیم.
گذر اول:
(۱, ۵, ۴, ۲, ۸)
A i + 1 then
swap(A i , A i + 1 )
swapped:= true
end if
end for
while swapped
end procedure
مرتب‌سازی انتخابی
معمولا اطلاعات و داده‌های خامی که در اختیار برنامه‌نویس قرار دارد به صورت نامرتب هستند. مواقعی پیش می‌آید که لازم است این داده‌ها بر حسب فیلد خاصی مرتب بشوند؛ مانند لیست دانش آموزان بر حسب معدل، لیست کارمندان بر حسب شماره پرسنلی، لیست دفترچه تلفن بر حسب نام خانوادگی و… روش‌های متعددی برای مرتب‌سازی وجود دارد. برای شروع روش مرتب‌سازی انتخابی (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
__target)
arrayEnd =currentIndex - 1;
else if (__arraycurrentIndex arrayBegin);
return -1;
مرتب‌سازی درجی
در مرتب‌سازی درجی، ابتدا عنصر دوم با عنصر اول لیست مقایسه می‌شود و در صورت لزوم با عنصر اول جابجا می‌شود به‌طوری‌که عناصر اول و دوم تشکیل یک لیست مرتب دوتایی را بدهند. سپس عنصر سوم به ترتیب با دو عنصر قبلی خود یعنی عناصر دوم و اول مقایسه و درجای مناسبی قرار می‌گیرد به‌طوری‌که عناصر اول و دوم و سوم تشکیل یک لیست مرتب سه تایی را بدهند. سپس عنصر چهارم به ترتیب با سه عنصر قبلی خود یعنی عنصرسوم و دوم و اول مقایسه و درجای مناسب قرار می‌گیرد به‌طوری‌که عناصر اول و دوم و سوم و چهارم تشکیل یک لسیت مرتب چهارتایی را بدهند و در حالت کلی عنصر nام باn-1 عنصر قبلی خود مقایسه می‌گردد تا در مکان مناسب قرار گیرد به‌طوری‌که n عنصر تشکیل یک لیست مرتب nتایی را بدهند و این روند تا مرتب شدن کامل لیست ادامه می‌یابد. یا به صورت دقیق‌تر
مرحله 1:1A خودش به‌طور بدیهی مرتب است.
مرحله 2:2A را یا قبل از یا بعد از 1A درج می‌کنیم طوری‌که 1A و 2A مرتب شوند.
مرحله 3:3A را در مکان صحیح در 1A و 2A درج می‌کنیم به گونه‌ای که 1Aو 2A و3A مرتب شده باشند.
مرحله An:n را در مکان صحیح خود در 1Aو 2A و… وAn-1 به گونه‌ای درج می‌کنیم که کل آرایه مرتب باشد.
زمان اجرای الگوریتم مرتب‌سازی درجی از(O(n^2 است.
این الگوریتم از الگوریتم‌های پایدار می‌باشد و در یک آرایه کاملا مرتب بهترین حالت را دارد و برای یک آرایه مرتب شده معکوس بدترین حالت را دارد.
ثابت شده‌است که برای ام‌های کوچکتر از بیست مرتب‌سازی درجی سریع‌ترین روش مرتب‌سازی است.
پیاده‌سازی (مرتب‌سازی درجی) در ++C
void Insertion_sort (int A , int n)
int i , j ,temp;
for (i =1 ; i 0 -- Aj-1>temp ; j--)
Aj=Aj-1;
Aj=temp;
مرتب‌سازی پایه‌ای (مبنایی)
مرتب‌سازی مبنایی الگوریتمی است که لیستی با اندازه ثابت و اعضایی با طول k را در زمان (O(kn اتجام می‌دهد. ورودی‌ها را به بخش‌های کوچکی تقسیم می‌کنیم (اگر یک کلمه‌است آن را به حرف‌هایش می‌شکنیم و اگر عدد است آن را به ارقامش) سپس ابتدا لیست را بر اساس کم ارزش‌ترین بیت (حرف یا رقم) مرتب می‌کنیم، سپس بر اساس دومین بیت، تا در نهایت بر اساس پرارزش‌ترین بیت. به این ترتیب پس از k مرحله لیست مرتب می‌شود.
این روش مرتب‌سازی پایدار است و در تهیه واژه‌نامه‌ها و مرتب‌سازی اعداد استفاده می‌شود.
مرتبه اجرایی این الگوریتم در بهترین حالت از(O(nlgn و در بدترین حالت از(O(n^2 است.
پیاده‌سازی radix sort
int i , j , k ;
for (i = 1 ; i
1)
++; K
Gapk=gapk-1/2;
//end of while
For (i= ۰; i
low)
st.push(low);
st.push(p – 1);
if (p
j; a--)
arra = arra - 1;
arrj = 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;
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 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 خود آرایه و اندیسهای بالا، پایین و جداکننده زیر آرایه‌ای را که باید ادغام بشود دریافت می‌کند، و به صورت درجا (بدون استفاده از آرایه کمکی) دو قمست مرتب شده زیر آرایه رو ادغام می‌کند.
مثالی در این مورد را مشاهده می‌کنید:
پرونده:Merge sort algorithm diagram.svg
مرتب‌سازی بوگو
در علوم کامپیوتر، مرتب‌سازی بوگو (که به آن مرتب‌سازی تصادفی، مرتب‌سازی میمونی هم می‌گویند) یک روش غیر موثر در الگوریتم‌های مرتب‌سازی محسوب می‌شود. از این مرتب‌سازی برای اهداف آموزشی در تقابل با دیگر روش‌های واقع گرایانه در مرتب‌سازی به کار می‌رود. اگر در مرتب‌سازی دسته‌ای از کارت‌ها از مرتب‌سازی بوگو استفاده شود، بدین صورت خواهد بود که ابتدا بررسی می‌شود که آیا لیست مرتب است یا خیر. اگر نبود، دوباره ترتیب کارت‌ها را تغییر می‌دهیم، و پردازه قبلی را دوباره اجرا می‌کنیم تا زمانی که به یک لیست مرتب از کارت‌ها برسیم. نام این مرتب‌سازی از واژه 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
مقایسه الگوریتم‌های مرتب‌سازی