버블 정렬 (Bubble sort) - 오름차순 기준
버블 정렬 알고리즘은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.
예를 들어 [9,4,7,1,2] 라는 배열이 있다고 가정해서 버블 정렬이 어떻게 되는지 알아 보았다.
[1]
1. 배열의 첫번째 원소인 9와 그 다음 두번째 원소인 4를 비교한다. 9는 4보다 크기 때문에 9와 4의 자리를 교환한다.
[4,9,7,1,2]
2. 그 다음 배열의 두번째 원소와 세번째 원소를 비교한다. 9는 7보다 크기 때문에 9와 7을 교환한다.
[4,7,9,1,2]
3. 그 다음도 마찬가지로 진행한다.
[4,7,1,9,2]
[4,7,1,2,9]
4. 마지막 원소는 그 다음 원소가 없기 때문에 첫번째 순회 종료
[2]
1. 다시 배열의 처음 원소부터 [1]번의 과정을 동일하게 거친다. 이때 비교하려는 두 원소중에 앞의 원소가 작으면 교환은 일어나지 않는다.
[4,7,1,2,9]
[4,1,7,2,9]
[4,1,2,7,9]
[3]
1. 마찬가지로 동일한 과정
[1,4,2,7,9]
[1,2,4,7,9]
[4]
1. 동일한 과정을 거치지만 교환은 일어나지 않음
(탐색은 배열 처음부터 끝까지 이루어짐!! 교환만 일어나지 않음)
[5]
1. 4번과 동일
최종적으로 반환되는 결과는 [1,2,4,7,9] 이다.
버블 정렬의 시간 복잡도
버블 정렬의 시간 복잡도를 계산하면 best, worst, average case 모두 O(n^2)의 시간복잡도를 갖는다.
(처음 n, 그 다음 n-1, 그 다음 n-2 ...... 2, 1 = n*n-1*-n-2 .... 2,1 = n(n-1)/2 = O(n^2))
왜냐하면 이미 정렬이 되어 있든 안되어 있든 n개의 input이 있을 때 n개의 대해서 각각 n번, 즉 for문을 2번 돌기 때문에 (교환이 일어나지 않더라도 비교는 계속 진행하기 때문에) 최상, 최악, 평균의 경우 모두 O(n^2)의 시간복잡도를 갖게 된다.
버블 정렬의 장점과 단점
장점
- 구현이 매우 간단하다.
단점
- 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하려면 배열의 모든 요소와 교환이 되어야 한다.
- 이미 특정 요소가 최종 정렬 결과에 맞는 위치에 있더라도 교환되는 일이 일어날 수 있고, 교환하지 않더라도 비교는 배열의 원소 갯수만큼 계속 진행됨
-> 즉, 버블정렬은 구현이 단순함에도 느리기 때문에 잘 쓰이지 않는다.
버블 정렬에서 시간복잡도 최적화하기
버블 정렬은 두 원소를 비교하여 교환을 하지 않더라도, 배열 크기만큼 비교는 계속 진행하기에 항상 어떤 경우에도 O(n^2)의 시간복잡도를 갖는다. 그렇기 때문에 이미 오름차순으로 정렬된 배열이 들어오더라도 똑같은 O(n^2)의 시간복잡도가 나온다.
그래서 처음부터 정렬된 배열이 들어오거나, 혹은 버블 정렬 진행 중간에 정렬이 완성 되는 경우, 더 이상 비교를 진행하지 않고 결과를 바로 반환하도록 하여 시간 복잡도를 최적화 시킬 수 있다.
예를 들어 처음 for문을 돌 때마다 초기 카운트를 0으로 지정하고, 교환이 일어난다면 카운트가 1씩 증가하게 한다.
만약 배열을 한번 다 비교 했을 때, 카운트가 0이라면 (즉, 교환이 1번도 일어나지 않았다면) 그 배열은 이미 정렬이 다 되어있는 배열이라고 생각할 수 있다. 이때 정렬을 중지하고 (for문을 빠져나옴, break) 그 상태의 배열을 바로 반환하면 된다.
이렇게 최적화를 하게 되면 best case (처음부터 정렬된 배열이 들어올 경우)는 처음 한번만 배열의 원소 들을 비교하고, 교환이 한번도 일어나지 않았기 때문에 바로 그 상태의 배열을 반환하게 되고 이때의 시간복잡도는 O(n)이 나오게 된다!!!
(중간에 정렬이 완성되는 경우에도 언제 정렬이 완성될지 모르겠지만, O(n^2)보다는 좀 더 나을 것이다)
'Algorithm' 카테고리의 다른 글
| (191119) 시간복잡도 (Time Complexity) (0) | 2019.11.20 |
|---|
댓글