[알고리즘] 버블 정렬(bubble sort) 쉽게 이해하기!

 

버블 정렬 (bubble sort)

 

버블 정렬, 거품을 뜻하는 그 버블이 맞다. 

 

서로 인접한 두 원소끼리 비교하고 크기 순으로 위치를 바꾸는 알고리즘인데,

 

예를 들면 이런 느낌이다. 

 

임의의 배열 [7, 21, 18, 36, 2 ] 이 있다고 가정하면

 

 

버블 정렬은 이렇게 비교를 해주는 식이다. 

 

(저 동글 동글한 게 꼭 버블같다고 해서 버블 정렬인 듯 하다. ㄱㅇㅇ..)

 

 

오름차순으로 정렬한다고 치면, 과정은 다음과 같다.

 

 

1. 7과 21을 비교하고 작은 수를 왼쪽에 둔다.

 

-> 7이 더 작으므로 순서는 7 , 21 그대로

 

[7, 21 , 18 , 36, 2] 

 

 

 

 

2. 21과 18을 비교하고 작은 수를 왼쪽에 둔다.

-> 18이 더 작으므로 순서 18, 21로 바뀜

[7, 18, 21, 36, 2] 

 

 

 

3. 21과 36을 비교하고 작은 수를 왼쪽에 둔다.

-> 21이 더 작으므로 순서는 21, 36 그대로

[7, 18, 21 , 36, 2]

 

 

 

 

4. 36과 2를 비교하고 작은 수를 왼쪽에 둔다.

-> 2가 더 작으므로 순서는 2, 36으로 바뀜

[7, 18, 21 , 2, 36] 

 

 

 

이렇게 한 바퀴를 돌아도, 2 때문에 정렬이 완전 다 되진 않은 걸 확인할 수 있다.

그렇다. 버블 정렬은.. 더이상 원소들끼리 바뀌지 않을 때까지 반복해야한다.

(더 이상 원소들끼리 바뀌지 않는다는 게 결국 정렬이 다 되었음을 의미하므로)

그럼 마저 진행해보겠다.

 

.

 

5. 7과 18은 그대로 두어도 되고 

6. 18과 21도 그대로 두어도 된다.

 

[7, 18, 21, 2, 36]

 

 

 

7. 21과 2를 비교하니 2가 더 작으므로

    자리를 바꾸어주어야 한다.

[7, 18, 2, 21, 36]

 

8. 21과 36은 그대로 두어도 된다.

 

 

 

 

 

이런 식으로, 가장 작은 수인 2가 맨 앞에 갈 때까지 

 

이 과정을 반복해주면 된다. 

 

 

대충 이런 식으로 될 것이다 :)