زنگ تفريح شماره 111
تعريف مرتب سازی حبابی :
یک الگوریتم ساده‌است که لیست را پشت سرهم پیمایش می‌کند تا هر بار عناصر کنارهم را با هم سنجیده و اگر در جای نادرست بودند جابه‌جایشان کند. دراین الگوریتم این کار باید تا زمانی که هیچ جابه‌جایی در لیست رخ ندهد، ادامه یابد و در آن زمان لیست مرتب شده‌است.
در مایع حباب های بزرگتر زودتر به سطح آب می رسند و از آنجا که در هر مرحله از پیمایش لیست بزرگترین عدد زودتر به بالای لیست می رسد از این جهت به این الگوریتم مرتب سازی حبابی می گویند.
شکل بالا طرحی از چگونگی مراحل مرتب سازی حبابی است ( هر خط معرف یک عدد است ) .
در اين الگوريتم اعداد تصادفي در يك آرايه قرار مي‌گيرند و يك نشانگر فرضي بر روي اولين خانه از آرايه قرار مي‌گيرد. در هر گام نشانه‌گر يك خانه به جلو حركت مي‌كند و مقدار آن با مقدار خانه مجاورش مقايسه مي‌شود و در صورت اينكه بزرگتر باشد مقدار دو خانه با هم عوض مي‌شود.
براي مثال آرايه زير را در نظر بگيريد:
در ابتدا نشانه‌گر روي خانه 1 كه مقدارش 60 است قرار دارد. در اين گام مقادير خانه‌هاي 1 و 2 يعني 60 و 42 باهم مقايسه مي‌شوند و چون 60 از 42 بزرگتر است حاي اين مقادير با هم عوض مي‌شود.
در گام بعدي نشانگر روي خانه شماره 2 قرار مي‌گيرد و مقاديرخانه‌هاي مجاور با هم مقايسه مي‌شوند :
چون 60 از 75 كوچكتر است جابجايي صورت نمي‌گيرد.گامهاي بعدي در اين مرحله به همين صورت ادامه دارند تا بزرگترين عدد آرايه در خانه آخر قرار گيرد.ترتيب اين گام‌ها به صورت زير است:
در مراحل بعدي گام‌ها به همين صورت تكرار مي‌شوند آرايه به صورت صعودي مرتب شود. گامهاي مراحل بعدي به صورت زير است:
مراحل بعدي به همين صورت ادامه مي‌يابند تا آرايه به صورت صعودي مرتب شود.
شبه كد جستجوي ترتيبي:
عملكرد مرتب سازي حبابي:
تعداد مقايسه‌ها در بدترين حالت:
(n-1) + (n-2) + ... + 3 + 2 + 1 à O(n²)
بدترین زمان اجرا و پیچیدگی متوسط مرتب سازی حبابی هر دو (O(n^2 می‌باشند که در آن n تعداد عناصری است که باید مرتب شوند .
الگوریتم‌های مرتب سازی بسیاری وجود دارند که بدترین زمان اجرای آنها از این بهتر است یا پیچیدگی متوسط آنها (O(n log n است . حتی بقیه اگوریتم‌های مرتب سازی از (O(n^2 مثل [مرتب سازی درجی] ، عملکرد بهتری نسبت به مرتب سازی حبابی از خود نشان می‌دهند .
تعداد مقايسه‌ها در بهترين حالت:
پيچيدگي زماني مرتب سازي حبابي در كل : O(n²) + O(n²) = O(n²)
نتیجه گیری
در مرتب سازی حبابی موقعیت عناصر درون لیست نقش بسزایی در تعیین عملکرد آن دارد.
از آنجایی که عناصر بزرگ در ابتدای مراحل مرتب سازی به سرعت جابجا (swap) می‌شوند ، مشکل چندانی در سرعت عملکرد الگوریتم ایجاد نمی‌کنند . اما عناصر کوچک (که باید به سمت ابتدای لیست بیایند) بسیار کند حرکت می‌کنند . این تفاوت در سرعت به حدی است که به عناصر بزرگ ، خرگوش‌ها ، و به عناصر کوچک ، لاک‌پشت‌ها می‌گویند .
تلاش بسیاری انجام شده که سرعت حرکت لاک پشت‌ها در مرتب سازی حبابی افزایش یابد . از جمله می‌توان از ] [Cocktail Sortنام برد که در این زمینه بسیار خوب عمل می‌کند ولی بدترین زمان اجرای آن هنوز ( O(n^2 است .