در پست قبل مفهومی از مرتب سازی را برای شما گفتیم و یک تابع برای مرتب سازی ارایه دادیم ، در این پست به سراغ مرتب سازی حبابی (bubble sort) می رویم که از معروف ترین الگوریتم های مرتب سازی است .قبل از این که به ادامه بحث بپردازیم یک مرور بکنیم از سایر الگوریتم ها که در روز های آینده آن ها را بررسی خواهیم کرد:
-bubble sort
-insertion sort
-merge 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 رو می شه جور دیگری پیاده سازی کرد ولی این بهتره.اگر برنامه را طور دیگری نوشته اید یا با زبان دیگری حتما آن را در نظرات بیان کنید.