가장 기본적인 정렬 Bubble Sort

가장 기본적인 거품정렬이 나열되는 순서를 표현해본 그림 이라고 한다.

버블 솔트( Bubble Sort ) 혹은 거품 정렬 이라고도 불리는 이 정렬법은 아주 단순한 알고리즘과 단순한 코드로 구현된 정렬법이다.

우리가 오름차순으로 정렬을 하고 싶다. 할수 있는 가장 쉬운 방법이 뭘까 ?

처음부터 끝까지 인접한 두 원소를 검사하여 정렬을 한다. 이를 모든 원소에대해 계속 도는 것이다. 

두 수를 비교해서 큰 ( 혹은 작은 ) 수를 만나면 둘이 자리를 바꾸고 끝까지 가서 다시 처음+1 자리부터 다시한번 이를 반복한다.

마지막 하나만 남을떄 까지 ! 

말로만 해서는 이해하기 힘드므로 예시를 듣는 쪽이 이해하기 쉬울것 같다. 

딱 5개의 숫자만 가지고 진행을 해보자. 

10	5	7	8	2
5	10	7	8	2
5	10	7	8	2
5	7	10	8	2
5	7	10	8	2
5	7	8	10	2
5	7	8	10	2
5	7	8	2	10
5	7	8	2	10
5	7	8	2	10
5	7	8	2	10
5	7	2	8	10
5	7	2	8	10
5	7	2	8	10
5	2	7	8	10
5	2	7	8	10
2	5	7	8	10
2	5	7	8	10

자 5개를 정렬하는것을 완료하였다. 딱 봐도 비효율적이라고 생각할지도 모르겠다. 실제로도비효율적이다.

알고리즘을 정리하자면 이렇다.

1. 첫번째 요소와 두번째 요소의 대소관계를 비교하고 그에따라 두 위치를 바꾼다.

2. 비교하는 인덱스를 하나씩 증가하여, 1의 과정을 끝까지 반복한다.

3. 1과2의 과정을 배열요소의 개수 - 1 번 반복한다.  ( 끝부분을 제외한 부분을 반복 )

왜 끝부분을 빼는가 ?  위의 표를 보면 첫번째 한바퀴를 돌았을때 끝의 오는 원소가 10 이다. 

10은 최대값이므로 더이상 확인할 필요도 없이 무조건 바뀌지 않을 값이다.

2번째 바퀴가 끝났을때 8이 와있고 이는 10을 제외한 원소들 중 Max 값이다.

이처럼 한바퀴가 끝날때 마다 Max 값이 정렬이 되므로 끝부분을 빼고 연산을 해도 상관이 없다.

간단하게 코드로 생각을 해보자면

int arr[n] ;

int temp;

for( int a = 0 ; a < n ; a++ ){

for( int b = 0 ; b < n - a ; b ++ ) {

if( arr[ b ] > arr[ b + 1 ] ){

temp = arr[b + 1] ;

arr[ b + 1 ] = arr[ b ] ;

arr[ b ] = temp ;

}

}

}

이 정도가 되겠다.

시간 복잡도를 계산해보면 N 크기의 배열을 쭉 보고 다시 쭉보고 다시 보고.... 를 N 번 반복하지만 어찌됬든

Big O 표기법에 의하면 결국은 N X N 이므로 O ( N ^ 2 ) 의 시간복잡도를 가진다.

비 효율적이긴 하지만 코드가 간결하기 때문에 의외로 많이 쓰이는 부분이고, 어차피 적은 케이스에 대해서는 큰 차이가 나지않는다. 

또하나의 장점이 있다면, 공간을 변수 1개 만큼만 더쓰고 추가적인 메모리 낭비가 없다는 것인데, 이는 다른 좋은 정렬들도

많이 가지고 있는 장점이다.

아주 기초적인 정렬 법인 버블 솔트에 대해 정리해보았다 .