مرتب سازی حبابی ( به انگلیسی: Bubble sort ) یک الگوریتم مرتب سازی ساده است که فهرست را پشت سرهم پیمایش می کند تا هر بار عناصر کنارهم را با هم سنجیده و اگر در جای نادرست بودند جابه جایشان کند. در این الگوریتم این کار باید تا زمانی که هیچ جابه جایی در فهرست رخ ندهد، ادامه یابد و در آن زمان فهرست مرتب شده است. این مرتب سازی از آن رو حبابی نامیده می شود که هر عنصر با عنصر کناری خود سنجیده شده و درصورتی که از آن کوچک تر باشد جای خود را به آن می دهد و این کار همچنان پیش می رود تا کوچک ترین عنصر به پایین فهرست برسد و دیگران نیز به ترتیب در جای خود قرار گیرند ( یا به رتبه ای بالاتر روند یا به پایین تر فهرست رانده شوند ) این عمل همانند پویش حباب به بالای مایع است.
این مرتب سازی از آن رو که برای کار با عناصر آن ها را با یکدیگر می سنجد، یک مرتب سازی سنجشی است.
با فرض داشتن n عضو در فهرست، در بدترین حالت n ( n − 1 ) / 2 عمل لازم خواهد بود.
بدترین زمان اجرا و پیچیدگی متوسط مرتب سازی حبابی هر دو O ( n 2 ) می باشند که در آن n تعداد عناصری است که باید مرتب شوند. الگوریتم های مرتب سازی بسیاری وجود دارند که بدترین زمان اجرای آن ها از این بهتر است یا پیچیدگی متوسط آن ها O ( n log n ) است. حتی بقیه الگوریتم های مرتب سازی از O ( n 2 ) مثل مرتب سازی درجی، عملکرد بهتری نسبت به مرتب سازی حبابی از خود نشان می دهند.
در مرتب سازی حبابی موقعیت عناصر درون فهرست نقش بسزایی در تعیین عملکرد آن دارد. از آنجایی که عناصر بزرگ در ابتدای فهرست به سرعت جابجا ( swap ) می شوند، مشکل چندانی در سرعت عملکرد الگوریتم ایجاد نمی کنند. اگرچه عناصر کوچک نزدیک به آخر فهرست ( که باید به سمت ابتدای فهرست بیایند ) بسیار کند حرکت می کنند. این تفاوت در سرعت به حدی است که به عناصر بزرگ، خرگوش ها، و به عناصر کوچک، لاک پشت ها می گویند. تلاش بسیاری انجام شده که سرعت حرکت لاک پشت ها در مرتب سازی حبابی افزایش یابد. از جمله می توان از نام برد که در این زمینه بسیار خوب عمل می کند ولی بدترین زمان اجرای آن هنوز O ( n 2 ) است. عناصر بزرگ با فاصله های زیاد را مقایسه می کند و لاک پشت ها را با سرعت فوق العاده ای حرکت می دهد سپس با کم تر و کم تر کردن این فاصله ها فهرست را به سرعت مرتب می کند، به طوری که سرعت متوسط آن قابل مقایسه با الگوریتم های پر سرعتی مثل مرتب سازی سریع می باشد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاین مرتب سازی از آن رو که برای کار با عناصر آن ها را با یکدیگر می سنجد، یک مرتب سازی سنجشی است.
با فرض داشتن n عضو در فهرست، در بدترین حالت n ( n − 1 ) / 2 عمل لازم خواهد بود.
بدترین زمان اجرا و پیچیدگی متوسط مرتب سازی حبابی هر دو O ( n 2 ) می باشند که در آن n تعداد عناصری است که باید مرتب شوند. الگوریتم های مرتب سازی بسیاری وجود دارند که بدترین زمان اجرای آن ها از این بهتر است یا پیچیدگی متوسط آن ها O ( n log n ) است. حتی بقیه الگوریتم های مرتب سازی از O ( n 2 ) مثل مرتب سازی درجی، عملکرد بهتری نسبت به مرتب سازی حبابی از خود نشان می دهند.
در مرتب سازی حبابی موقعیت عناصر درون فهرست نقش بسزایی در تعیین عملکرد آن دارد. از آنجایی که عناصر بزرگ در ابتدای فهرست به سرعت جابجا ( swap ) می شوند، مشکل چندانی در سرعت عملکرد الگوریتم ایجاد نمی کنند. اگرچه عناصر کوچک نزدیک به آخر فهرست ( که باید به سمت ابتدای فهرست بیایند ) بسیار کند حرکت می کنند. این تفاوت در سرعت به حدی است که به عناصر بزرگ، خرگوش ها، و به عناصر کوچک، لاک پشت ها می گویند. تلاش بسیاری انجام شده که سرعت حرکت لاک پشت ها در مرتب سازی حبابی افزایش یابد. از جمله می توان از نام برد که در این زمینه بسیار خوب عمل می کند ولی بدترین زمان اجرای آن هنوز O ( n 2 ) است. عناصر بزرگ با فاصله های زیاد را مقایسه می کند و لاک پشت ها را با سرعت فوق العاده ای حرکت می دهد سپس با کم تر و کم تر کردن این فاصله ها فهرست را به سرعت مرتب می کند، به طوری که سرعت متوسط آن قابل مقایسه با الگوریتم های پر سرعتی مثل مرتب سازی سریع می باشد.
wiki: مرتب سازی حبابی