Y@SiN
09-13-2009, 01:07 PM
يکي از مهم‌ترين مولفه‌ها در برنامه‌نويسي، بهينه بودن الگوريتم است. منظور از بهينه بودن اين است که با کمترين هزينه، بيشترين بازده را دريافت کنيم. منظور از هزينه، ميزان حافظه مصرفي و منظور از بازده، انجام سريع‌تر عمليات است. اين دو عامل معمولا رابطه مستقيم با يکديگر ندارند و معمولا سريع‌ترين الگوريتم‌ها، اگر هزينه پاييني داشته‌باشند، بسيار پيچيده‌اند و از طرف ديگر، الگوريتم‌هاي ساده (بازگشتي) هزينه بالايي دارند. روش‌هاي مختلفي براي مرتب سازي داده‌ها وجود دارد. از مولفه‌هاي مهم در الگوريتم‌هاي مرتب‌سازي ميزان مقايسه و ميزان جابهجايي است، در زير چند نمونه از آنها را بررسي مي‌کنيم:
الف) مرتب‌سازي انتخابي
در اين الگوريتم در هر مرحله عنصر بزرگتر پيدا مي‌شود (اگر مرتب سازي نزولي باشد کوچکترين عنصر) و با يک جابهجايي در جاي خود قرار مي‌گيرد، عمل مقايسه در مرحله اول به اندازه 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://pnu-club.com/imported/mising.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
الف) مرتب‌سازي انتخابي
در اين الگوريتم در هر مرحله عنصر بزرگتر پيدا مي‌شود (اگر مرتب سازي نزولي باشد کوچکترين عنصر) و با يک جابهجايي در جاي خود قرار مي‌گيرد، عمل مقايسه در مرحله اول به اندازه 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://pnu-club.com/imported/mising.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