들어가기 전에
어떤 배열이 주어졌을 때, 그 배열이 미리 정렬되어 있다면 훨씬 빠른 속도로 검색이 가능합니다. 정렬하기 위한 방법은 여러가지가 있고, 각각 실행 시간도 다릅니다. 이번 강의에서는 그 중 하나인 버블 정렬을 배워 보겠습니다.
학습 목표
버블 정렬의 원리와 실행 시간을 설명하고 구현할 수 있습니다.
핵심 단어
- 버블 정렬
버블 정렬
정렬되지 않은 리스트를 탐색하는 것 보다 정렬한 뒤 탐색하는 것이 더 효율적입니다.
정렬 알고리즘 중 하나는 버블 정렬입니다.
버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말합니다.
버블 정렬은 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중합니다.
이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있습니다.
아래와 같은 8개의 숫자가 임의의 순서로 나열되어 있습니다.
이 숫자들을 오름차순으로 정렬하기 위해 바로 옆의 있는 숫자들과 비교하는 방법을 사용해 보겠습니다.
6 3 8 5 2 7 4 1
먼저 가장 앞의 6과 3을 비교해서 순서를 바꿉니다.
교환 전: 6 3 8 5 2 7 4 1
교환 후: 3 6 8 5 2 7 4 1
다음 쌍인 6과 8을 비교해보면 교환할 필요가 없으므로 그대로 둡니다.
바로 다음에 있는 쌍인 8과 5를 비교해서 순서를 바꿉니다.
교환 전: 3 6 8 5 2 7 4 1
교환 후: 3 6 5 8 2 7 4 1
이런 식으로 숫자 끝까지 진행하면 아래와 같이 정렬이 됩니다.
3 6 5 2 7 4 1 8
하지만 아직 오름차순으로 정렬이 되지 않았기 때문에, 다시 처음부터 동일한 작업을 반복합니다.
3 6 5 2 7 4 1 8
3 6 5 2 7 4 1 8 (교환)
3 5 6 2 7 4 1 8 (교환)
3 5 2 6 7 4 1 8
3 5 2 6 7 4 1 8 (교환)
3 5 2 6 4 7 1 8 (교환)
3 5 2 6 4 1 7 8
조금 더 잘 정렬이 되었습니다. 이 과정을 끝까지 반복하면 최종적으로 아래와 같이 오름차순 정렬이 될 것입니다.
1 2 4 3 5 6 7 8
이러한 정렬 방식을 ‘버블 정렬’이라고 합니다.
마치 거품이(비교 및 교환이) 터지면서 위로 올라오는 (배열의 옆으로 이동하는) 방식이기 때문입니다.
아래와 같이 의사 코드로 나타낼 수 있습니다.
Repeat n–1 times
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap them
중첩 루프를 돌아야 하고, n개의 값이 주어졌을 때 각 루프는 각각 n-1번, n-2번 반복되므로 (n-1)*(n-2) = n^2-3n+2(n−1)∗(n−2)=n2−3n+2 번의 비교 및 교환이 필요합니다.
여기서 가장 크기가 큰 요소는 n^2 이므로 위와 같은 코드로 작성한 버블 정렬 실행 시간의 상한은 O(n^2)이라고 말할 수 있습니다.
정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교를 해야 하므로 위와 같은 코드로 작성한 버블 정렬의 실행 시간의 하한도 여전히 Ω(n^2)이 됩니다.
생각해보기
버블 정렬이 효율적인 경우는 어떤 경우인가요? 반대로 어떤 경우에 비효율적이게 될까요?
나의생각 : 요소의 갯수가 작고 정렬이 되지않았을 때
출처 : https://www.boostcourse.org/cs112/lecture/119022?isDesc=false 네이버커넥트재단