در پست قبل مفهومی از مرتب سازی را برای شما گفتیم و یک تابع برای مرتب سازی ارایه دادیم ، در این پست به سراغ مرتب سازی حبابی (bubble sort) می رویم که از معروف ترین الگوریتم های مرتب سازی است .قبل از این که به ادامه بحث بپردازیم یک مرور بکنیم از سایر الگوریتم ها که در روز های آینده آن ها را بررسی خواهیم کرد:

– مفهوم مرتب سازی

-bubble sort

-insertion sort

-merge sort

–quick sort

-Distribution sorts

– Concurrent sorts

در این روش مرتب سازی هر عنصر آرایه فقط با عنصر کناری خود مقایسه می شود و اگر عنصر n ام کوچک تر از عنصر n+1 ام بود جای ای دو عنصر عوض می شود این کار تا زمانی که تمام آرایه مرتب شود ادامه می یابد .

اسم این الگوریتم را مرتب سازی حبابی (bubble sort) گذاشته اند  زیرا هر عنصر آرایه فقط با عنصر کناری خو بررسی می شود در تصویر متحرک زیر می توانید آرایه ای را ببینید که با بابل ، سورت می شود :

تابع مرتب سازی حبابی (bubble sort) را در زیر می بینید :

void bubble_sort( int A[],int n)
{
	int i;
	int temp ;
	int flag = 1;

	while( flag == 1)
	{
		flag = 0;

		for( i = 0; i < n-1 ; i++)
		{
			if( A[i] > A[i+1])
			{
				temp = A[i];
				A[i] = A[i+1];
				A[i+1] = temp;
				flag = 1;
			}
		}

	}
}

فرض کنید آرایه ی  ۵ عنصری   ۴ ۱ ۶ ۵ ۸ را دارید و می خواهید آن را با الگوریتم بابل مرتب کنید :

8 5 6 1 4

5 8 6 1 4

5 6 8 1 4

5 6 1 8 4

5 6 1 4 8

5 1 6 4 8

1 5 6 4 8

1 5 4 6 8

1 4 5 6 8

مرتبه این الگوریتم در بدترین حالت  ( O(n^2  است و  در  بهترین حالت  ( O(n است  به همین خاطر برای سورت کردن تعداد زیادی عنصر مناسب نیست .

در زیر برنامه ای آمده است که در آن تابع مرتب سازی حبابی آمده است که در تابع main  برنامه  آرایه ای به  تابع داده شده تا آن را سورت کند و آرایه را قبل و بعد از مرتب سازی چاپ کند

// bubble sort.cpp : تابع مرتب سازی حبابی 
//

#include "stdafx.h"
#include <iostream>

using namespace std;

void bubble_sort( int A[],int n)
{
	int i;
	int temp ;
	int flag = 1;

	while( flag == 1)
	{
		flag = 0;

		for( i = 0; i < n-1 ; i++)
		{
			if( A[i] > A[i+1])
			{
				temp = A[i];
				A[i] = A[i+1];
				A[i+1] = temp;
				flag = 1;
			}
		}

	}
}

int main()
{
	int i = 0;
	int A[5]={8,5,6,1,4};
	//show array before sort
	for( i = 0; i < 5; i++)
	{
		cout<< A[i]<<" ";
	}
	cout<<endl;
	//sort function
	bubble_sort(A,5);
	//show array after sort
	for( i = 0; i < 5; i++)
	{
		cout<< A[i]<<" ";
	}
	cout<<endl;

	return 0;
}

البته  الگوریتم bubble  رو می شه  جور دیگری پیاده سازی کرد ولی این بهتره.اگر برنامه را طور دیگری نوشته اید یا با زبان  دیگری حتما آن را در نظرات بیان کنید.