03강 - 버블 정렬 (Bubble Sort)

다음으로 버블 정렬 알고리즘이다

---

[ 버블 정렬 ]

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보낸다!

 

몹시 직관적인 해결 방법이다

바로 가까이에 있는 두 숫자끼리 비교해서 지금 당장의 더 작은 숫자를 앞으로 보내주는 것을 반복하는 것이다!

구현은 가장 쉽지만 그만큼 가장 비효율적인 알고리즘이다

 

이 과정을 반복하면 한 사이클을 돌고 나면 최댓값이 맨 뒤에 가있다

물론 최솟값이 맨 앞에 있다는 것은 보장할 수 없다

왜냐? 옆의 놈이랑만 비교해서 작으면 앞으로 보내주는 거지 최소값을 찾아서 보내는게 아니니까!

그치만 최댓값은 맨 뒤에 있다

왜냐? 옆의 값이랑 비교하는데 크면 계속 뒤로뒤로뒤로.. 보내니까 사이클 당 최댓값은 맨 뒤에 있을 수밖에 없는 것이다

 

위의 그림처럼!

예전에 강의들을떈 뭔소리야.. 했는데 지금 보니까 이해가 간다ㅋㅋ

 

[ 코드 ]

아무튼 코드로 구현해보자

#include <iostream>
#include <stdio.h>
using namespace std;

//버블정렬 - Bubble sort
int main(){

  int array[10]={1,10,5,8,7,6,4,3,2,9};
	int temp;
	
	for(int i=0;i<10;i++){
		for(int j=0;j<9-i;j++){
			if(array[j]>array[j+1]){
				temp=array[j];
				array[j]=array[j+1];
				array[j+1]=temp;
			}
		}
	}
	for(int i=0;i<10;i++){
		printf("%d ",array[i]);
	}

    return 0;
}

그냥 중첩반복문 돌리고 그 안에서 배열의 범위만 뒤에부터 줄여나가면서 계속 작은 값은 앞으로 앞으로 보내주면 되는것이다

아주 단순하게 반복적으로 두 숫자를 비교하여 앞으로 보낸다

그럼 보다시피 각 싸이클마다 가장 큰 값이 맨 뒤로 보내지게 된다

컴퓨터 내부적인 연산이 가장 비효율적으로 일어나며 실제 수행시간 또한 가장 느린 안 좋은 알고리즘이다

 

 

[ 시간 복잡도 ]

버블 정렬의 시간 복잡도는 선택 정렬과 같은 O(N^2)이다

비록 시간 복잡도는 선택 정렬과 같지만, 사실 가장 비효율적인 알고리즘이다

 

버블 정렬의 시간 복잡도는 O(N^2)이다

 

---

총평 : 정렬하면 바로 생각날만큼 간단한 코드이지만 그만큼 비효율적이다