버블정렬은 가장 간단한 알고리즘입니다.

인접한 원소를 비교하고 반복적으로 재배열 하면서 작동합니다.

 

예:

(5 1 4 2 8)->(1 5 4 2 8), 처음 두 원소를 비교하고 5와 1을 바꿉니다.

(1 5 4 2 8)->(1 4 5 2 8), 5와 4를 바꿉니다.

(1 4 5 2 8)->(1 4 2 5 8), 5와 2를 바꿉니다.

(1 4 2 5 8)->(1 4 2 5 8), 순서가 올바르기에 5와 8은 바꾸지 않습니다. pass

 

(1 4 2 5 8)->(1 4 2 5 8)pass

(1 4 2 5 8)->(1 2 4 5 8), 4와 2 교환

(1 2 4 5 8)->(1 2 4 5 8)pass

(1 2 4 5 8)->(1 2 4 5 8)pass

 

이제 정렬이 되었지만 알고리즘 내에서는 완료 되었는지 알 수 없기에, 전부 pass될 때 까지 반복합니다.

(1 2 4 5 8)->(1 2 4 5 8)pass

(1 2 4 5 8)->(1 2 4 5 8)pass

(1 2 4 5 8)->(1 2 4 5 8)pass

(1 2 4 5 8)->(1 2 4 5 8)pass

 

#include <bits/stdc++.h> 
using namespace std; 

void swap(int *xp, int *yp) 
{ 
	int temp = *xp; 
	*xp = *yp; 
	*yp = temp; 
} 

void printArray(int arr[], int size) 
{ 
	int i; 
	for (i = 0; i < size; i++) 
		cout << arr[i] << " "; 
	cout << endl; 
} 

void reculsiveBubbleSort(int arr[], int n) 
{ 
    // Base case 
    if (n == 1) 
        return; 
  
    bool all_pass = true;
    for (int i=0; i<n-1; i++) 
        if (arr[i] > arr[i+1]){
        	swap(arr[i], arr[i+1]);
        	all_pass = false;
		}
    printArray(arr, n); 
  	if(all_pass == true){
  		return;
	  }

    reculsiveBubbleSort(arr, n-1); 

void bubbleSort(int arr[], int n) 
{ 
	
	for(int i=0; i<n-1;i++){//원소와 원소 사이마다 한번씩만 반복하면 된다. 그러므로 1회 제거 
		bool all_pass = true;
		for(int j=0; j < n-1-i; j++){//1회 반복 시 제일 뒤의 원소는 정렬이 된 상태가 된다 그러므로 i만큼 빼준다. 
			if (arr[j] > arr[j+1])
			{
				swap(&arr[j], &arr[j+1]);
				all_pass=false;
			}
		}
		printArray(arr, n); 
		if(all_pass == true){
			break;
		}
	}
} 

int main() 
{ 
	int arr[] = {5, 4, 3, 2, 1};
	int n = sizeof(arr)/sizeof(int); 
	bubbleSort(arr, n); 
	cout<<"Sorted array: \n"; 
	printArray(arr, n); 
	return 0; 
} 

 

제자리 정렬이며 안정정렬이다.

최악의 경우 시간복잡도 O(n^2)이다.

 

"인접한 원소를 정렬해나가기 때문에 버블처럼 보인다. 1회 반복때마다 가장 큰 원소는 맨 뒤에 자리하게 된다."

'알고리즘 > 지식' 카테고리의 다른 글

[정렬 알고리즘] 합병 정렬  (0) 2020.03.03
[정렬 알고리즘] 삽입 정렬  (0) 2020.03.03
[정렬 알고리즘] 선택 정렬  (0) 2020.03.02
[기본] 정렬 알고리즘  (0) 2020.03.02
소수 판별  (0) 2019.12.06

+ Recent posts