روش مرتب‌سازی حبابی

این روش از نظر منطق، ساده‌ترین و از نظر کارآیی پایین‌‌ترین روش مرتب‌سازی اطلاعات به شمار می‌رود. در این روش ابتدا عنصر اول با عنصر دوم مقایسه می‌شود. اگر عنصر اول بزرگ‌تر از دومی باشد، جای آن دو تعویض می‌شود. سپس این عمل در مورد عنصر دوم با سوم و همین‌طور برای بقیه عناصر به صورت متوالی انجام می‌گیرد؛ یعنی، در پایان با عنصر n-1 اُم مقایسه می‌شود که اگر بزرگ‌تر از آن بود جایشان تعویض می‌شود. وقتی که ‌این عمل یک بار کامل شد، بزرگ‌ترین عنصر آرایه به آخر آرایه منتقل می‌شود. حال اگر خانه آخر را نادیده بگیریم و این عمل را دوباره برای خانه‌ها یا عناصر ۱ تا n-1 تکرار کنیم، این بار بزرگ‌ترین عنصر خانه‌ها ۱ تا n-1 (که دومین عنصر بزرگ آرایه خواهد بود) به خانه n-1 آرایه منتقل می‌شود. اگر این عمل را به صورت تکراری برای n-1 بار انجام دهیم و برای سرعت عمل بیشتر، در هر بار تکرار نیز خانه آخر محدوده جاری آرایه را نادیده بگیریم، یعنی هر بار از طول ناحیه مورد مقایسه یک واحد کاسته شود، در پایان، عناصر آرایه به صورت صعودی مرتب می‌گردد. اگر بخواهیم که عناصر آرایه مورد نظر به‌صورت نزولی مرتب شود، باید در مقایسه دو عنصر متوالی ai با ai+1، چنانچه ai کوچک‌تر از ai+1 باشد، جای آن دو با یکدیگر تعویض شود.
از آنجایی که در این روش مرتب ‌سازی در هر بار تکرار، بزرگترین عنصر آرایه به سمت بالا یا انتهای آرایه حرکت می‌کند (مانند حبابهای هوا که در آب جوش موجود است)، آن را مرتب ‌سازی حبابی نامند.
v مثال ۷ـ۱۲ تابع زیر آرایه n عنصری A را به روش حبابی مرتب می‌کند.
void BubbleSort (int A[ ] , int n)
{
int i , j , temp ;
for (i =1 ; i<n ; + +i)
for (j =0 ; j<n-i ; + +j)
if (A[ j] > A[ j+1])
{
temp = A [ j] ;
A[ j] = A[ j+1] ;
A[ j+1] = temp ;
}
}