Bubble Sort (거품 정렬)

정렬 알고리즘

알고리즘을 조금씩 공부해나가야 할 것 같아 인강을 듣는다. Bubble Sort 부터 하루 하나씩 개념 익히기 도전.

Bubble Sort(거품정렬)란?

  • 두 개의 인접한 원소를 비교해서 정렬하는 알고리즘이다.
    • 가장 대표적으로는 배열 속 숫자를 오름차순으로 정렬시키는 것
  • 논리는 굉장히 단순하지만 시간복잡도는 O(n2)으로 엄청나게 효율적이진 않다.
  • 정렬될 원소가 거품처럼 하나하나 타고 올라가서 붙여진 이름이라고 한다.

배열 속 정수 오름차순 정렬하기로 보는 Bubble Sort 구현

중첩된 for문

1
2
3
4
5
6
7
arr = [ 3, 6, 1, 2, 4, 23, 4214 ]

for i in range(len(arr)-1):
for j in range(len(arr)-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = a[j+1], a[j]
return arr
  • n개의 정수가 담긴 배열에 대해, 작은 수부터 앞에 오도록 정렬해보자
  • 앞에서부터 두개씩 크기를 비교하고 앞의 숫자가 크면 뒤의 숫자와 바꿔주는 연산을 n-1번 수행한다.
    • 최대값이 이동하여 가장 뒷자리로 간다. 하지만 그 앞의 값들은 여전히 정렬되지 않은 상태이다.
  • 동일한 연산을 앞에서부터 n-2번 수행한다. 가장 뒷자리는 이미 최대값이므로 비교하지 않아도 된다.
    • 이제 가장 뒤쪽에서 두개는 정렬된 최대값 2개이다. 하지만 앞에서부터 n-2개 값은 여전히 정렬되지 않은 상태.
  • 이런식으로 비교하고 바꾸는 작업을 첫번째는 n-1번, 두번째는 n-2번, 세번째는 n-3번 … n-1번째는 1번 수행한다.
    • 중첩된 for문: outer for문의 전체 range는 (n-1)번, inner for문의 range는 (n-index(outer for문이 몇번째 돌고있는지)-1)이다.

정렬된 상황에 대해 break하기

  • 정렬이 완료되면 inner for문을 돌며 한 번도 교체작업이 일어나지 않는다. 그러면 굳이 나머지 for문을 돌릴 필요가 없다.
  • outer for문에 swap이라는 변수를 0으로 초기화해둔다.
  • 교체작업이 일어날 때마다 swap 이라는 변수에 교체작업의 횟수를 기록하고, 이 횟수가 0일 경우 그냥 for문을 break 한다.
1
2
3
4
5
6
7
8
9
10
11
arr = [ 3, 6, 1, 2, 4, 23, 4214 ]

for i in range(len(arr)-1):
swap = 0
for j in range(len(arr)-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = a[j+1], a[j]
swap += 1
if swap == 0:
break
return arr

Bubble Sort의 시간복잡도

  • n-1번 도는 for문이 중첩되어 있어서 O(n2)의 시간복잡도를 갖는다.
  • 그러나 이미 정렬되어 있는 경우, 첫 순회 후 break 되므로 O(n)까지도 줄어든다.

느낀 점

  • 기억도 나지 않는데 이 정렬문제를 해커랭크에서 풀고 블로그에도 기록하기까지 했다.
  • 당시에는 왜 교체한 횟수가 0일 때 break를 썼는지 궁금해했는데, 의문이 풀렸다.

참고자료