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를 썼는지 궁금해했는데, 의문이 풀렸다.
참고자료
hanana1253문정동에서 코딩하는 하나나입니다.