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

정렬 이야기 (첫번째 이야기) -  버블 정렬

오늘은 많은 정렬 중 

버블 정렬에 대해서 설명해보려고 한다.

버블 정렬, 거품 정렬 등등으로 많이 불린다.

왜 거품, 버블 정렬 일가?

이 질문에 답은 아래를 읽다 보면 해결 할 수 있다.

먼저 방법을 알고 가자

버블 정렬의 방법은 인접한 2개의 레코드를 비교하여

순서대로 되어 있지 않으면 서로 교환(SWAP) 하여서

계속 진행하는 방식이다.

이렇게 말하면 절대 모르지... ㅋㅋ

그림으로 보자

5 - 3 -  8 - 1 - 2 - 7

 순서로 나열되어 있다.

이를 오름차순으로 나열 하기 위하여 

버블 정렬을 사용하면 

인접한 두개의 값을 비교하여 조건과 일치하면 

서로 교환해주는 것이다.

5 - 3 - 8 - 1 - 2 - 7     (5>3) <SWAP>

3 - 5 - 8 - 1 - 2 - 7     (5<8) <PASS>

3 - 5 - 8 - 1 - 2 - 7     (8>1) <SWAP>

3 - 5 - 1 - 8 - 2 - 7     (8>2) <SWAP>

3 - 5 - 1 - 2 - 8 - 7     (8>7) <SWAP>

3 - 5 - 1 - 2 - 7 - 8      8고정             

한 패턴이 끝난다. 

이 말은 마지막 수는 항상 최대값이기에 고정이다.

마지막 수가 초기값이 될 때 까지

패턴을 지속 적용하면

3 - 5 - 1 - 2 - 7      (3<5) <PASS>

3 - 5 - 1 - 2 - 7      (5>1) <SWAP>

3 - 1 - 5 - 2 - 7      (5>2) <SWAP>

3 - 1 - 2 - 5 - 7      (5<7) <PASS>

3 - 1 - 2 - 5 - 7      7 고정            

3 - 1 - 2 - 5    (3>1) <SWAP>

1 - 3 - 2 - 5    (3>2) <SWAP>

1 - 2 - 3 - 5    (3<5) <PASS>

1 - 2 - 3 - 5    5고정             

1 - 2 - 3    (1>2) <PASS>

1 - 2 - 3    (2>3) <PASS>

1 - 2 - 3    3고정             

1 - 2      (1>2) <PASS>

1 - 2      2고정             

1      1고정        

이런 식으로 정렬이 되는 것이다.

쉽게 설명한 건지는 모르겠다.

아 왜 버블이냐 하는 질문이 있었다.

내가 표현한 것은 색상으로 빨간색으로 두 인접 수를 표현 하였지만

보통은 위에 둥글게 둥글게 선을 그어서 표현한다.

그 둥근 모양이 거품 모양을 닮았다고 해서

 버블 정렬 이라 부른다고 한다.

그럼 소스를 한번 살펴 보장

5, 1, 7, 4, 2, 6, 3  

위 코드를 수행하여 보면

결과는 

버블정렬의 복잡도는 최상 평균 최악의 경우에도 일정하게 O(n^2) 이다.

최악의 경우는 정렬이 역순으로 되어 있는 경우 이고,

최상의 경우는 정렬이 이미 되어 있는 경우 이다.

버블정렬은 SWAP에 대한 오버헤드가 크다는 단점을 지니고 있다.

도움이 되었다면.  리플을 남겨주시길 많은 힘이 됩니다. ^^