الگوریتم مرتب سازی حبابی (Bubble Sort)

الگوریتم مرتب سازی حبابی (Bubble Sort)

الگوریتم مرتب سازی حبابی (Bubble Sort) ساده ترین الگوریتم مرتب سازی است که با تغییر دادن مکرر عناصر مجاور در صورت نامرتب بودن، آرایه را مرتب می کند.

مثال

اولین گام:

( ۵۱ ۴ ۲ ۸ ) –> ( ۱ ۵ ۴ ۲ ۸ ): در اینجا دو مقدار ۵ و ۱ با هم مقایسه می شوند و چون ۵ از ۱ بزرگتر است با هم عوض می شوند.
( ۱ ۵۴ ۲ ۸ ) –> ( ۱ ۴ ۵ ۲ ۸ ): چون ۵ > 4 است، تعویض می شوند.
( ۱ ۴ ۵۲ ۸ ) –> ( ۱ ۴ ۲ ۵ ۸ ): چون ۵ > 2 است، تعویض می شوند.
( ۱ ۴ ۲ ۵۸ ) –> ( 1 4 2 ۵ ۸ ): در اینجا چون ۵ < 8 است، تعویضی نمی شود.

دومین گام:

( ۱۴ ۲ ۵ ۸ ) –> ( ۱ ۴ ۲ ۵ ۸ ): تعویضی صورت نمی گیرد.
( ۱ ۴۲ ۵ ۸ ) –> ( 1 ۲ ۴ ۵ ۸ ): چون ۴ > 2 است، تعویض می شوند.
( ۱ ۲ ۴۵ ۸ ) –> ( 1 2 ۴ ۵ ۸ ): تعویضی صورت نمی گیرد.
( ۱ ۲ ۴ ۵۸ ) –> ( ۱ ۲ ۴ ۵ ۸ ): تعویضی صورت نمی گیرد.

حال آرایه ما مرتب شده است. اما الگوریتم از این موضوع با خبر نیست و تمام گام ها را انجام می دهد.

سومین گام:

( ۱۲ ۴ ۵ ۸ ) –> ( ۱ ۲ ۴ ۵ ۸ ): تعویضی صورت نمی گیرد.
( ۱ ۲۴ ۵ ۸ ) –> ( 1 ۲ ۴ ۵ ۸ ): تعویضی صورت نمی گیرد.
( ۱ ۲ ۴۵ ۸ ) –> ( 1 2 ۴ ۵ ۸ ): تعویضی صورت نمی گیرد.
( ۱ ۲ ۴ ۵۸ ) –> ( 1 2 4 ۵ ۸ ): تعویضی صورت نمی گیرد.

پیاده سازی این الگوریتم با زبان سی پلاس پلاس:

// C++ program for implementation of Bubble sort 
#include <bits/stdc++.h>
using namespace std;
void swap(int *xp, int *yp) 
{ 
    int temp = *xp; 
    *xp = *yp; 
    *yp = temp; 
} 
// A function to implement bubble sort 
void bubbleSort(int arr[], int n) 
{ 
    int i, j; 
    for (i = 0; i < n-1; i++)     
    // Last i elements are already in place 
    for (j = 0; j < n-i-1; j++) 
        if (arr[j] > arr[j+1]) 
            swap(&arr[j], &arr[j+1]); 
} 
/* Function to print an array */
void printArray(int arr[], int size) 
{ 
    int i; 
    for (i = 0; i < size; i++) 
        cout << arr[i] << " "; 
    cout << endl; 
} 
// Driver code 
int main() 
{ 
    int arr[] = {64, 34, 25, 12, 22, 11, 90}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    bubbleSort(arr, n); 
    cout<<"Sorted array: \n"; 
    printArray(arr, n); 
    return 0; 
}

امتحان کنید

خروجی:

Sorted array:
11 12 22 25 34 64 90

تصویری از نحوه کار این الگوریتم:

پیاده سازی این الگوریتم به زبان سی پلاس پلاس (بهینه شده):

// Optimized implementation of Bubble sort
#include <stdio.h>
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
// An optimized version of Bubble Sort
void bubbleSort(int arr[], int n)
{
   int i, j;
   bool swapped;
   for (i = 0; i < n-1; i++)
   {
     swapped = false;
     for (j = 0; j < n-i-1; j++)
     {
        if (arr[j] > arr[j+1])
        {
           swap(&arr[j], &arr[j+1]);
           swapped = true;
        }
     }
     // IF no two elements were swapped by inner loop, then break
     if (swapped == false)
        break;
   }
}
/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("n");
}
// Driver program to test above functions
int main()
{
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

امتحان کنید

خروجی:

Sorted array:
11 12 22 25 34 64 90

نکات

در بدترین حالت و حالت متوسط پیچیدگی زمانی برابر با O(n*n) است. بدترین حالت زمانی است که آرایه به صورت بر عکس مرتب شده باشد.
در بهترین حالت پیچیدگی زمانی الگوریتم برابر با O(n) است. بهترین حالت زمانی است که آرایه قبلا مرتب شده باشد.
فضای موقت برابر با O(1) است.

نوشته الگوریتم مرتب سازی حبابی (Bubble Sort) اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.