Y@SiN
09-13-2009, 12:53 PM
اين الگوريتم ساده ترين و معروف ترين الگوريتم براي مرتب سازي داده است.
فرض کنید می‌خواهیم n داده به صورت صعودی مرتب شوند. عنصر اول را با با عنصر دوم مقایسه کرده، و در صورتی که عنصر اول بزرگتر باشد باشد جای عنصر اول و دوم را عوض می‌کنیم. همین کار را با عناصر دوم و سوم انجام می‌دهیم و همینطور عناصر سوم و چهارم ، الی آخر. وقتی این کار تمام شد بزرگ‌ترین عنصر بین داده‌ها به آخر لیست می‌رسد . حالا یک بار دیگر از اول این کار را انجام می‌دهیم اما این بار تا عنصر (n -۱)ام ادامه می‌دهیم (عنصر nام در مرحله اول در جای خودش قرار گرفته). باز هم این کار را تا عنصر (n - ۲)ام تکرار می‌کنیم ، و بازهم .... تا اینکه بالاخره داده‌ها مرتب می‌شوند.
مثلا:
۰ - ۰) ۵ ۶ ۴ ۲
۱ - ۱) ۵ ۶ ۴ ۲
۱ - ۲) ۵ ۴ ۶ ۲
۱ - ۳) ۵ ۴ ۲ ۶
۲ - ۱) ۴ ۵ ۲ ۶
۲ - ۲) ۴ ۲ ۵ ۶
۳ - ۱) ۲ ۴ ۵ ۶
مرحله اول سه مقایسه ، مرحله دوم دو مقایسه و مرحله سوم یک مقایسه داره ، که روی هم می‌شوند شش مقایسه. در کل این روش n (n - ۱) / ۲ مقایسه لازم داره. اما نه همیشه. به مثال زیر توجه کنید:
۰ - ۰) ۰ ۷ ۱ ۳ ۵ ۴
۱ - ۱) ۰ ۱ ۷ ۳ ۵ ۴
۱ - ۲) ۰ ۱ ۷ ۳ ۵ ۴
۱ - ۳) ۰ ۱ ۳ ۷ ۵ ۴
۱ - ۴) ۰ ۱ ۳ ۵ ۷ ۴
۱ - ۵) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۱) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۲) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۳) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۴) ۰ ۱ ۳ ۴ ۵ ۷
۳ - ۱) ۰ ۱ ۳ ۴ ۵ ۷
۳ - ۲) ۰ ۱ ۳ ۴ ۵ ۷
۳ - ۳) ۰ ۱ ۳ ۴ ۵ ۷
۴ - ۱) ۰ ۱ ۳ ۴ ۵ ۷
۴ - ۲) ۰ ۱ ۳ ۴ ۵ ۷
۵ - ۱) ۰ ۱ ۳ ۴ ۵ ۷
همونطور که می‌بینید انتهای مرحله ۲ داده‌ها مرتب هستن. تشخیص این مساله هم کار سختی نیست: اگه به مرحله‌ای رسیدیم که هیچ جابجایی در اون رخ نداد نتیجه می‌شه که داده‌ها مرتب هستن (مرحله سوم). پس بعد از مرحله ۳ مطمئن می‌شیم که داده هامون مرتب شدن و نیازی به مراحل ۴ و ۵ نیست.
برگرفته از: ويكيپديا
فرض کنید می‌خواهیم n داده به صورت صعودی مرتب شوند. عنصر اول را با با عنصر دوم مقایسه کرده، و در صورتی که عنصر اول بزرگتر باشد باشد جای عنصر اول و دوم را عوض می‌کنیم. همین کار را با عناصر دوم و سوم انجام می‌دهیم و همینطور عناصر سوم و چهارم ، الی آخر. وقتی این کار تمام شد بزرگ‌ترین عنصر بین داده‌ها به آخر لیست می‌رسد . حالا یک بار دیگر از اول این کار را انجام می‌دهیم اما این بار تا عنصر (n -۱)ام ادامه می‌دهیم (عنصر nام در مرحله اول در جای خودش قرار گرفته). باز هم این کار را تا عنصر (n - ۲)ام تکرار می‌کنیم ، و بازهم .... تا اینکه بالاخره داده‌ها مرتب می‌شوند.
مثلا:
۰ - ۰) ۵ ۶ ۴ ۲
۱ - ۱) ۵ ۶ ۴ ۲
۱ - ۲) ۵ ۴ ۶ ۲
۱ - ۳) ۵ ۴ ۲ ۶
۲ - ۱) ۴ ۵ ۲ ۶
۲ - ۲) ۴ ۲ ۵ ۶
۳ - ۱) ۲ ۴ ۵ ۶
مرحله اول سه مقایسه ، مرحله دوم دو مقایسه و مرحله سوم یک مقایسه داره ، که روی هم می‌شوند شش مقایسه. در کل این روش n (n - ۱) / ۲ مقایسه لازم داره. اما نه همیشه. به مثال زیر توجه کنید:
۰ - ۰) ۰ ۷ ۱ ۳ ۵ ۴
۱ - ۱) ۰ ۱ ۷ ۳ ۵ ۴
۱ - ۲) ۰ ۱ ۷ ۳ ۵ ۴
۱ - ۳) ۰ ۱ ۳ ۷ ۵ ۴
۱ - ۴) ۰ ۱ ۳ ۵ ۷ ۴
۱ - ۵) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۱) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۲) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۳) ۰ ۱ ۳ ۵ ۴ ۷
۲ - ۴) ۰ ۱ ۳ ۴ ۵ ۷
۳ - ۱) ۰ ۱ ۳ ۴ ۵ ۷
۳ - ۲) ۰ ۱ ۳ ۴ ۵ ۷
۳ - ۳) ۰ ۱ ۳ ۴ ۵ ۷
۴ - ۱) ۰ ۱ ۳ ۴ ۵ ۷
۴ - ۲) ۰ ۱ ۳ ۴ ۵ ۷
۵ - ۱) ۰ ۱ ۳ ۴ ۵ ۷
همونطور که می‌بینید انتهای مرحله ۲ داده‌ها مرتب هستن. تشخیص این مساله هم کار سختی نیست: اگه به مرحله‌ای رسیدیم که هیچ جابجایی در اون رخ نداد نتیجه می‌شه که داده‌ها مرتب هستن (مرحله سوم). پس بعد از مرحله ۳ مطمئن می‌شیم که داده هامون مرتب شدن و نیازی به مراحل ۴ و ۵ نیست.
برگرفته از: ويكيپديا