[정렬 알고리즘] Bubble Sort(버블정렬, 거품정렬)

§버블 정렬

잘못된 순서로 정렬된 인접한 원소를 반복적으로 교체하는 정렬 알고리즘이다.

 

Example:

First Pass:

( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.

( 1 5 4 2 8 ) –>  ( 1 4 5 2 8 ), Swap since 5 > 4

( 1 4 5 2 8 ) –>  ( 1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )

( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) –>  ( 1 2 4 5 8 )

Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

 

Time Complexity: O(n2) as there are two nested loops.

 

구현언어( C )

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

//////////////////////////////// //    Bubble Sort //    버블 정렬 ////////////////////////////////     #include <stdio.h>   void swap(int *xp, int *yp) {     int tmp = *xp;     *xp = *yp;     *yp = tmp; }   void bubbleSort(int arr[], int n) {     int i, j;     for (i = 0; i < n - 1; i++)         for (j = 0; j < n - i - 1; j++)             if (arr[j] > arr[j + 1])                 swap(&arr[j], &arr[j + 1]); }   void printArray(int arr[], int size) {     int i;     for (i = 0; i < size; i++)         printf("%d ", arr[i]);     printf("\n"); }   int main() {     int arr[] = { 64, 34, 25, 12, 22, 11, 90 };     int n = sizeof(arr) / sizeof(arr[0]);     printf("Unsorted array: ");     printArray(arr, n);     bubbleSort(arr, n);     printf("Sorted array: ");     printArray(arr, n);     return 0; }   Colored by Color Scripter

cs