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

الف) مرتب‌سازی انتخابی

در این الگوریتم در هر مرحله عنصر بزرگتر پیدا می‌شود (اگر مرتب سازی نزولی باشد کوچکترین عنصر) و با یک جابه‌جایی در جای خود قرار می‌گیرد، عمل مقایسه در مرحله اول به اندازه N-1  انجام می‌شود (N تعداد داده‌های موجود است)، و در مرحله دوم به اندازه N-2. به‌همین ترتیب در مرحله iام N-i مقایسه باید انجام شود، در کل n*(n-1)/2 مقایسه باید انجام شود، و در هر مرحله حداکثر 1 جابه‌جایی انجام می‌شود. در بهترین شرایط‌داده‌ها از اول بصورت مرتب شده هستند که در این حالت هیچ جابه‌جایی صورت نمی‌گیرد؛ در بدترین حالت در هر مرحله یک جابه‌جایی داریم و حداکثر n-1  جا‌به‌جایی صورت می‌گیرد. بدین ترتیب مرتبه اجرایی این الگوریتم در بهترین و بدترین شرایط به ترتیب به صورت زیر است:

O(N^2) مقایسه، O(1) جابه‌جایی

O(N^2) مقایسه، O(N) جابه‌جایی

می‌توان اثبات کرد که در مرتب سازی صعودی اگر داده‌ها به‌صورت نزولی مرتب شده باشند، میزان جابه‌جایی همان n*(n-1)/2 است ولی تعداد تعویض‌ها برابر n/2 است.

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

در این الگوریتم چندین بار داده‌های مورد نظر را بررسی می‌کنیم، در هر مرحله هر عنصر با عنصر بعدی مقایسه می‌شود اگر بزرگتر بود، با عنصر بعدی جابه جا می‌شود، در پایان مرحله اول بزرگترین عنصر در آخرین خانه قرار می‌گیرد. در مرحله بعد از خانه صفر تا خانه n-1 بررسی می‌شود و به‌همین ترتیب تا اینکه به اولین عنصر که کوچکترین عنصر است برسیم. در این الگوریتم مانند الگوریتم انتخابی میزان مقایسه‌ها برابر n(n-1)/2 است و تعداد جابه‌جایی‌ها در بهترین حالت زمانی است که داده‌ها مرتب شده باشند و میزان جابه‌جایی برابر صفر می‌گردد، در بدترین شرایط زمانی است که داده‌ها به‌صورت معکوس مرتب شده‌باشند، که برابر n(n-1)/2 است، مرتبه اجرایی این الگوریتم در بهترین و بدترین شرایط به ترتیب به صورت زیر است:

O(N) مقایسه، O(1) جابه‌جایی

O(N^2) مقایسه، O(N^2) جابه‌جایی

ج) مرتب‌سازی خارجی

در این الگوریتم به ترتیب عناصر 0 تا n خوانده شده و عنصر nام در جای درست خود در زیر آرایه از قبل مرتب شده x[0]، x[1]، ... x[n-1] قرار می‌گیرد.

در مرحله اول، عنصر 0ام را در نظر می‌گیریم که بطور بدیهی مرتب است.

در مرحله دوم، عنصر 1ام را با عنصر 0ام مقایسه می‌کنیم و در جای مناسب خود قرار می‌دهیم به‌طوری که عناصر 0ام و 1ام مرتب شده باشند.

در مرحله سوم، عنصر 2ام را با دو عنصر قبلی مقایسه کرده و در جای خود قرار می‌دهیم، به‌طوری که آرایه حاصله مرتب شده باشد. و در مرحله iام، عنصر iام را با کل آرایه. حال از مرحله i-1 مقایسه کرده و در جای خود قرار می‌دهیم به‌طوری که آرایه حاصل مرتب شده باشد.

در این الگوریتم نیز میزان مقایسه مانند دو الگوریتم ذکر شده برابر n*(n-1)/2 است، در بهترین شرایط داده‌ها مرتب شده هستند، که در این حالت تعداد مقایسه‌ها برابر n-1 است و هیچ جابه‌جایی نیز صورت نمی‌پذیرد، مرتبه اجرایی این الگوریتم در بهترین و بدترین شرایط به ترتیب به صورت زیر است:

O(N) مقایسه، O(1) جا به جایی

O(N^2) مقایسه ، O(N^2) جا به جایی

د) مرتب‌سازی ادغامی

اساس این الگوریتم از روش تقسیم و حل برای مرتب سازی استفاده می‌کند، در این روش مساله به چند مساله کوچکتر تقسیم می‌شود، و با حل هر کدام از این مساله‌های کوچک و ترکیب آنها با هم مساله اصلی حل می‌شود. پس می‌توان پی‌برد که بخشی از این الگوریتم بصورت بازگشتی پیاده‌سازی می‌شود، نکته‌ای که قبل از توضیح روش کار باید در نظر گرفت بحث ترکیب است، در این الگوریتم حاصل هر مرحله با حاصل‌های دیگر باید ترکیب شده تا نتیجه درست حاصل شود. در این بحث از توضیح این الگوریتم صرف نظر می‌کنیم ولی این الگوریتم برای دو آرایه x[s,m] و y[m+1,n] از مرتبه O(n-s+1) است که n-s+1 تعداد عناصری هستند که با هم ترکیب شده‌اند.

شرح الگوریتم

در مرحله اول داده‌ها به N آرایه 1 عضوی تقسیم می‌شوند و سپس عناصر دو به دو با هم ادغام می‌شوند تا n/2 آرایه دو عضوی حاصل شود (اگر n عددی فرد باشد یک آرایه تک عضوی پدید می‌آید)، سپس این n/2 آرایه را دو به دو با هم ترکیب کرده تا به یک لیست n عضوی مرتب برسیم، از این رو به حداکثر Log n مرحله جهت مرتب‌کردن آرایه نیاز دارد، مرتبه اجرایی این الگوریتم همواره O(n*Log n) است، معمولا از این الگوریتم برای فایل‌ها استفاده می‌کنند.

ح) مرتب‌سازی درختی

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

درج هر داده در درخت BST به مدت O(Log N) انجام می‌پذیرد و درج n داده O(n*Log n) انجام می‌گیرد پیمایش inorder درخت جستجوی دودویی باعث نمایش لیست مرتب شده بصورت صعودی می‌شود.

بدترین وضیعت در درخت جستجوی دودویی زمانی است که داده‌های ورودی به‌صورت مرتب شده باشند (چه صعودی چه نزولی)، که درخت حاصل بصورت اریب ظاهر می‌شود در این حال اگر داده‌های تکراری نباشند برای درج n(n-1)/2 مقایسه باید انجام شود و مرتبه زمانی درج داده ها بصورت O(N2) است.

بهترین حالت برای این الگوریتم زمانی است که داده ها نا مرتب بوده، که عمق درخت در حال متوازن (Log(n,2 قرار گیرد، در نتیجه زمان درج n داده همانطور که گفته شد برابر O(nLog n) است و زمان مرتب سازی برابر O(n*Log(n,2)) است.

امیربهاالدین سبط‌الشیخ