[정렬 알고리즘][파이썬] 버블 정렬

버블 정렬(bubble sort)은 '오른쪽부터 왼쪽 방향으로 인접한 두 개의 숫자를 비교해서 교환하는 작업을 반복합니다.' 오른쪽부터 왼쪽으로 숫자를 옮겨가는 모양이 물속에서 거품이 올라오는 모양과 비슷하다고 해서 버블이라고 합니다. -책 알고리즘 도감

 

위의 그림처럼 생긴 막대기들을 버블 정렬을 이용해 오름차순으로 정렬한다고 해봅시다.

오른쪽부터 왼쪽 방향으로 인접한 두 개의 숫자를 비교해서 교환하는 작업을 반복한다고 했죠?

오른쪽부터 좌우 숫자를 비교해서 오른쪽 숫자가 작으면 위치를 바꿔줍니다.

 

 

 

1. 40과 50을 비교한다. 40이 더 작으므로 50과 위치를 변경한다.

2. 30과 40을 비교한다. 30이 더 작으므로 위치를 변경하지 않는다.

3. 10과 30을 비교한다. 10이 더 작으므로 위치를 변경하지 않는다.

1~3번 수행후 모습

 

 

 

4. 20과 10을 비교한다. 10이 더 작으므로 20과 위치를 변경한다.

 

버블정렬 완료

끝! 하지만, 만약에 이렇게 오른쪽에서 왼쪽으로 한 번 쭈~~ 욱 했는데 아직 정렬이 안되어있다면 정렬이 될 때까지 위의 단계들을 반복해주면 되겠죠? 물론, 한 바퀴씩 돌 수록 왼쪽부터 비교하지 않아도 될 숫자들이 하나씩 늘어나겠죠?

 

근데 작성하다 보니까 그런 생각이 들었어요.

'왜 오른쪽에서 왼쪽 방향이지? 왼쪽에서 오른쪽 방향이면 안되나?'

왼쪽에서 오른쪽 방향도 됩니다!

대신 왼쪽에서 오른쪽 방향으로 가려면 (왼쪽 숫자 > 오른쪽 숫자) 일 때 위치를 서로 바꿔줘야 하겠죠?(오름차순 정렬이라고 가정할 때)

 

해설
버블 정렬은 1바퀴에서 n-1회, 2바퀴에서 n-2회,... n-1바퀴에서 1회를 비교합니다. 이 때문에 비교 회수는 (n-1) + (n-2) +... + 1 ≒ n∧2 / 2 가 됩니다. 이 비교 횟수는 입력 데이터의 순서와 상관없이 일정합니다. 숫자의 교체 횟수는 입력 데이터에 의존합니다. 극단적인 경우로, 입력 데이터가 우연히 작은 순서대로 나열돼 있을 때는 교체가 한 번도 발생하지 않습니다. 반대로, 숫자가 큰 순서대로 나열돼 있으면 비교할 때마다 교체해 주어야 합니다. 따라서 버블 정렬의 계산 시간은 O(n∧2)가 됩니다. 

 

이상으로 버블 정렬에 대해서 알아보았습니다!

 

참고 - 책 알고리즘 도감

 

 

버블 정렬 코드 - 파이썬

출력

출력 해설

i와 j를 순서쌍 (i, j)로 설명하겠습니다.

1. (0, 4) / if arr[j-1] > arr[j] 에서 50 > 40이므로 자리를 바꾸고 [20, 10, 30, 40, 50]이 출력됩니다.

2. (0, 3) / if arr[j-1] > arr[j] 에서 30 < 40이므로 자리를 바꾸지 않고 [20, 10, 30, 40, 50]이 출력됩니다.

3. (0, 2) / if arr[j-1] > arr[j] 에서 10 < 30이므로 자리를 바꾸지 않고 [20, 10, 30, 40, 50]이 출력됩니다.

4. (0, 1) / if arr[j-1] > arr[j] 에서 20 > 10이므로 자리를 바꾸고 [10, 20, 30, 40, 50]이 출력됩니다. => 정렬 완료!

 

5. (1, 4) / 생략

6. (1, 3) / 생략

7. (1, 2) / 생략

8. (2, 4) / 생략

9. (2, 3) / 생략

10. (3, 4) / 생략

11. (4, 4)이므로 안쪽 for문 실행 X

 

*참고

왼쪽에서 오른쪽 방향 코드

출력