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

다음과 같은 숫자들이 주어졌을 때 정렬과정은 밑과 같다.

숫자 배열 : 9 6 3 2 7

 

9 6 3 2 7  ->  6 9 3 2 7 -> 6 3 9 2 7 -> 6 3 2 9 7 -> 6 3 2 7 9 -> 3 6 2 7 9 -> 3 2 6 7 9 -> 2 3 6 7 9 

 

버블 정렬의 시간 복잡도는 선택 정렬과 마찬가지로 O(N^2)이며 그렇게 효율적인 정렬 방법은 아니다.

 

//				bubble sort


#include<iostream>
#include<time.h>

int main(){
	clock_t start, end;
	double result;
	
	start = clock();
	int N;
	std::cout << "Plz enter the array numbers : ";
	std::cin >> N;
	
	int* arr = new int[N];
	std::cout << "Now enter all the elements of your array : ";
	for(int i = 0; i < N; i++){
		std::cin >> arr[i];
	}
	
	char show_process;
	while(1){
		std::cout << "Do u want to see the process?[y/n] : ";
		std::cin >> show_process;
		if(show_process == 'y' || show_process == 'n'){
			break;
			std::cout << "Plz enter between 'y' and 'n' " << '\n';
		}
		else
			std::cout << "Plz enter between 'y' and 'n' " << '\n';
		
	}
	
	int temp;
	for(int i = 0; i < N; i++){
		for(int j = 0; j<N-i-1 ;j++){
			if(arr[j] > arr[j+1]){
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;	
			}
		}
		if(show_process == 'y'){
			std::cout << i+1 << " round : ";
			for(int z = 0; z < N; z++){
				std::cout << arr[z] << " ";
			}
			std::cout << '\n';
		}
	}
	
	
	std::cout << "The final result is : ";
	for(int i = 0; i < N; i++){
		std::cout << arr[i] << " ";
	}
	std::cout << '\n';
	
	end = clock();
	result = (double)(end-start);
	std::cout << "Compile time : " << result << "ms"<< "\n";
	return 0;
}

버블 정렬 구현은 어렵지 않으므로 설명은 따로 하지 않겠다. 

 

버블 정렬에 대해서는 오바마 전대통령의 언급으로 유명해진적이 있다. 시간이 있다면 밑 영상에서 확인해보도록...

 

https://www.youtube.com/watch?v=koMpGeZpu4Q