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

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

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

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

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

== طبقه‌بندی ==

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

* پیچیدگی (بدترین و بهترین عملکرد و عملکرد میانگین): با توجه به اندازهٔ لیست (n). در مرتب‌سازی‌های معمولی عملکرد خوب (O(n log n و عملکرد بد (O(n۲ است. بهترین عملکرد برای مرتب‌سازی (O(n است. الگوریتم‌هایی که فقط از مقایسهٔ کلیدها استفاده می‌کنند در حالت میانگین حداقل (O(n log n مقایسه نیاز دارند.
* حافظه (و سایر منابع کامپیوتر) : بعضی از الگوریتم‌های مرتب‌سازی «در جا{Ref|۱}» هستند. یعنی به جز داده‌هایی که باید مرتب شوند، حافظهٔ کمی ((O(۱) مورد نیاز است؛ در حالی که سایر الگوریتم‌ها به ایجاد مکان‌های کمکی در حافظه برای نگه‌داری اطلاعات موقت نیاز دارند.
* پایداری{Ref|۲} : الگوریتم‌های مرتب‌سازی پایدار ترتیب را بین داده‌های دارای کلیدهای برابر حفظ می‌کنند. فرض کنید می‌خواهیم چند نفر را بر اساس سن با یک الگوریتم پایدار مرتب کنیم. اگر دو نفر با نام‌های الف و ب هم‌سن باشند و در لیست اولیه الف جلوتر از ب آمده باشد، در لیست مرتب شده هم الف جلوتر از ب است.
* مقایسه‌ای بودن یا نبودن. در یک مرتب‌سازی مقایسه‌ای داده‌ها فقط با مقایسه به وسیلهٔ یک عملگر مقایسه مرتب می‌شوند.
* روش کلی : درجی، جابجایی، گزینشی، ترکیبی و غیره. جابجایی مانند مرتب‌سازی حبابی و مرتب‌سازی سریع و گزینشی مانند مرتب‌سازی پشته‌ای.

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

== مرتب‌سازی حبابی ==

== مرتب سازی انتخابی ==

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

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

۰: ۹ ۱ ۶ ۴ ۷ ۳ ۵

۱: ۵ ۱ ۶ ۴ ۷ ۳ ۹

۲: ۵ ۱ ۶ ۴ ۳ ۷ ۹

۳: ۵ ۱ ۳ ۴ ۶ ۷ ۹

۴: ۴ ۱ ۳ ۵ ۶ ۷ ۹

۵: ۳ ۱ ۴ ۵ ۶ ۷ ۹

۶: ۱ ۳ ۴ ۵ ۶ ۷ ۹ {پایان چپ‌چین}

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

void selection_sort (int arr[] , int n)

register int i , j;

int max , temp;

(–for (i = n – ۱ ; i > ۰ ; i

max = ۰;

for (j = ۱ ; j <= i ; j++) if (arr[ max ] < arr[ j]) max = j; ; ] temp = arr[ i arr[ i ] = arr[ max]; arr[ max ] = temp; == مرتب سازی درجی == * در مرتب سازی درجی، ابتدا عنصر دوم با عنصر اول لیست مقایسه می‌شود و در صورت لزوم با عنصر اول جابجا می‌شود به طوری که عناصر اول و دوم تشکیل یک لیست مرتب دوتایی را بدهند. سپس عنصر سوم به ترتیب با دو عنصر قبلی خود یعنی عناصر دوم و اول مقایسه و درجای مناسبی قرار می‌گیرد به طوری که عناصر اول و دوم و سوم تشکیل یک لیست مرتب سوم و دوم و اول مقایسه و درجای مناسب قرار می‌گیرد به طوری که عناصر اول و دوم و سوم و چهارم تشکیل یک لسیت مرتب چهارتایی را بدهند و در حالت کلی عناصر i ام با i-1 عنصر قبلی خود مقایسه می‌گردد تا در مکان مناسب قرار گیرد به طوری که i عنصر تشکیل یک لیست مرتب i تایی را بدهند و این روند تا مرتب شدن کامل لیست ادامه می‌یابد.یا به صورت دقیق تر : * مرحلهٔ 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 است. * این الگوریتم از الگوریتم های پایدار می‌باشد و در یک آرایهٔ کاملا مرتب بهترین حالت را دارد و برای یک آرایهٔ مرتب شده معکوس بدترین حالت را دارد. * ثابت شده است که برای n های کوچکتر از 20 مرتب سازی درجی سریع ترین روش مرتب سازی است. * پیاده سازی (مرتب سازی درجی) در 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;

== مرتب سازی پایه‌ای (مبنایی) ==

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

int i , j , k ;

for (i = 1 ; i<=5 ; i++) for (j = ۰ ; j http://www.ariapedia.com/?p=1 Sun, 25 Sep 2011 20:27:36 +0000 AriaPedia
http://www.ariapedia.com/?p=1

۱) ++; K Gap[k]=gap[k-۱]/۲; For (i= ۰;i<=k;i++) Step=gap[i]; For(j=step;j=۰ && x 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 – ۱; arr[ low ] = arr[ p]; arr[ p ] = pivot; return p; بر اساس گفته‌های بالا تابع مرتب سازی به این صورت خواهد بود: void quick_sort (int arr[ ] , int low , int high) int p = partition(arr , low , high); quick_sort(arr , low , p – ۱); quick_sort(arr , p + ۱ , high); void quick_sort (int arr[ ] ,int n) stack st; st.push(۰); st.push(n – ۱); 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 – ۱); if (p < high) st.push(p + ۱); st.push(high); == مرتب سازی ادغامی == روش مرتب سازی ادغامی از الگوریتم تقسیم و حل (divide-and-conqure) برای مرتب کردن داده‌ها استفاده می‌کنه. در این الگوریتم مساله به چند جزء کوچک‌تر تقسیم می‌شه. هر کدوم از این قسمت‌ها رو به طور مجزا حل کرده، و با ترکیب اونها به مساله اصلی می‌رسیم. و اما طرح کلی مرتب سازی ادغام: در این روش داده‌ها به دو قسمت مساوی تقسیم می‌شن. و هر کدوم از این قسمت‌ها - به صورت بازگشتی - مرتب، و با ادغامشون دادها بصورت کامل مرتب می‌شن. کلاس merge sort در #C 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 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) / ۲; merge_sort (arr , low , mid); merge_sort (arr , mid + ۱ , high); merge_array (arr , low , mid , high); m : integer; begin if l >= h then exit; m := (l + h) div ۲; merge_sort (arr , l , m); merge_sort (arr , m + ۱ , h); merge_array (arr , l , m , h); end; {پایان چپ‌چین} این توابع اونقدر ساده هستن که نیاز به هیچ توضیحی ندارن. فقط می‌مونه تابع merge_array که دو زیر آرایه رو با هم ادغام می‌کنه. register int i , j , k , t; j = low; for (i = mid + ۱ ; 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 – ۱]; 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 + ۱ 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 + ۱ do arr[ k ] := arr[ k – ۱]; arr[ j ] := t; end; End; {پایان چپ‌چین} تابع merge_array خود آرایه و اندیسهای بالا، پایین و جداکننده زیر آرایه‌ای رو که باید ادغام بشه دریافت می‌کنه، و به صورت درجا (بدون استفاده از آرایه کمکی) دو قمست مرتب شده زیر آرایه رو ادغام می‌کنه. == مرتب سازی درجی == مرتب سازی درجی یکی از روشهای مرتب سازی رایج و البته نه چندان کارا محسوب می‌شه. این روش در مقایسه با مرتب سازی حبابی و انتخابی سرعت بهتری داره و برای مرتب کردن تعداد کمی از عناصر مناسبه. به همین خاطر مراخل انتهایی روش مرتب سازی سریع با کمک گرفتن از این روش انجام می‌گیره. الگوریتم مرتب سازی درجی بر اساس مرتب سازیهایی که معمولاً خود ما بصورت دستی انجام می‌دیم طراحی شده. فرض کنید دسته کارتی با شماره‌های ۱ تا ۱۰ بصورت نامرتب و کنار هم روی زمین چیده شدن: ۵ ۲ ۹ ۳ ۱ ۱۰ ۴ ۶ ۸ ۷ کارت دوم رو نسبت به کارت اول در جای مناسب خودش قرار می‌دیم: ۲ ۵ ۹ ۳ ۱ ۱۰ ۴ ۶ ۸ ۷ حالا نوبت به کارت سوم می‌رسه. این کارت رو نسبت به دو کارت قبلی در جای مناسب قرار می‌دیم. چون ۹ در مقایسه با ۲ و ۵ جای درستی داره بدون هیچ جابجایی به کارت چهارم می‌رسیم. جای این کارت رو نسبت به سه کارت قبلی مشخص می‌کنیم: ۲ ۳ ۵ ۹ ۱ ۱۰ ۴ ۶ ۸ ۷ و به همین ترتیب تا آخر ادامه می‌دیم. اگه n تعداد عناصر رو مشخص کنه، این روش n - ۱ مرحله رو برای مرتب کردن طی می‌کنه. بعد از اتمام مرحله i ام مطمئنا i + ۱ عنصر اول به صورت مرتب شده هستن (قسمتی که زیرشون خط کشیده شده). این مساله یکی از حسنهای مرتب سازی درجی محسوب می‌شه: در هر مرحله حتما قطعه‌ای از عناصر مرتب شذه هستن. مرتب سازی حبابی این ویژگی رو نداره. پیاده سازی(مرتب سازی درجی) در c++ void insertion_sort (int arr[ ] , int n) register int i , j , t; (++ for (i = ۱ ; i < n ; i ]; t = arr[ i (-- for (j = i ; j > ۰ && arr[ j – ۱ ] >= t ; j ; arr[ j ] = arr[ j – ۱] 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 تکرار می‌گردد. == مرتب سازی بوگو == == فهرست الگوریتم‌های مرتب‌سازی == در این جدول، n تعداد داده‌ها و k تعداد داده‌ها با کلیدهای متفاوت است. ستون‌های بهترین، میانگین و بدترین، پیچیدگی در هر حالت را نشان می‌دهد و حافظه بیانگر مقدار حافظهٔ کمکی (علاوه بر خود داده‌ها) است. این جدول الگوریتم‌هایی را توضیح می‌دهد که به علت اجرای بسیار ضعیف و یا نیاز به سخت‌افزار خاص، کاربرد زیادی ندارند. == پاورقی == == منابع == * Wikipedia contributors, «Sorting algorithm», Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/wiki/Sorting_algorithm

درج دیدگاه

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