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

[آبجی]

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

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


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


منبع: ويكيپديا

[آبجی]

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

الف) مرتب‌سازي انتخابي
در اين الگوريتم در هر مرحله عنصر بزرگتر پيدا مي‌شود (اگر مرتب سازي نزولي باشد کوچکترين عنصر) و با يک جابه‌جايي در جاي خود قرار مي‌گيرد، عمل مقايسه در مرحله اول به اندازه 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) است، معمولا از اين الگوريتم براي فايل‌ها استفاده مي‌کنند.


http://www.algooritm.ir/images/stories/other/A-Sorting-1.jpg

ح) مرتب‌سازي درختي
اين مرتب‌سازي بر اساس درخت 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)) است.


اميربهاالدين سبط‌الشيخ
روزنامه كليك، شماره 243