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

سه شنبه ۳۰ مهر ۱۳۹۸
بازدید ۵,۸۵۲ نفر
آرتین
(24 امتیاز از 5 رای)
Loading...

تصویر bubble-sort-algorithm_7311 الگوریتم مرتب سازی حبابی (Bubble Sort)

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

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

مثال

اولین گام:

( 51 4 2 8 ) –> ( 1 5 4 2 8 ): در اینجا دو مقدار 5 و 1 با هم مقایسه می شوند و چون 5 از 1 بزرگتر است با هم عوض می شوند.
( 1 54 2 8 ) –> ( 1 4 5 2 8 ): چون 5 > 4 است، تعویض می شوند.
( 1 4 52 8 ) –> ( 1 4 2 5 8 ): چون 5 > 2 است، تعویض می شوند.
( 1 4 2 58 ) –> ( 1 4 2 5 8 ): در اینجا چون 5 < 8 است، تعویضی نمی شود.

دومین گام:

( 14 2 5 8 ) –> ( 1 4 2 5 8 ): تعویضی صورت نمی گیرد.
( 1 42 5 8 ) –> ( 1 2 4 5 8 ): چون 4 > 2 است، تعویض می شوند.
( 1 2 45 8 ) –> ( 1 2 4 5 8 ): تعویضی صورت نمی گیرد.
( 1 2 4 58 ) –> ( 1 2 4 5 8 ): تعویضی صورت نمی گیرد.

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

سومین گام:

( 12 4 5 8 ) –> ( 1 2 4 5 8 ): تعویضی صورت نمی گیرد.
( 1 24 5 8 ) –> ( 1 2 4 5 8 ): تعویضی صورت نمی گیرد.
( 1 2 45 8 ) –> ( 1 2 4 5 8 ): تعویضی صورت نمی گیرد.
( 1 2 4 58 ) –> ( 1 2 4 5 8 ): تعویضی صورت نمی گیرد.

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

// 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; 
}

// 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

1 2	Sorted array: 11 12 22 25 34 64 90

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

تصویر bubble-sort-algorithm_7311_1 الگوریتم مرتب سازی حبابی (Bubble Sort)

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

// 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;
}

// 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

1 2	Sorted array: 11 12 22 25 34 64 90

تغییر به حالت نزولی

برای تغییر به حالت نزولی کافیست در تابع bubbleSort شرط if (arr[j] > arr[j+1]) را به if (arr[j] < arr[j+1]) تغییر دهید.

نکات

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

الگوریتم ها - مرتب سازی انتخابی الگوریتم ها - جستجوی سه گانه