버블 정렬
Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 입니다.
이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 합니다.
문제 설명
N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 버블정렬입니다.
입력 설명
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.
- 13 5 11 7 23 15
출력 설명
오름차순으로 정렬된 수열을 출력합니다.
- 5 7 11 13 15 23
풀이 과정
[5,1,7,4,6,3,2,8] 처음 두 수를 비교해서 순서대로 숫자를 서로 바꿔줍니다.
[1,5,7,4,6,3,2,8] 5와 7은 이미 정렬되어 있으니까 그대로 놔둡니다.
[1,5,7,4,6,3,2,8] 7과 4는 서로 바꿔줍니다.
[1,5,4,7,6,3,2,8] .
[1,5,4,6,7,3,2,8] .
[1,5,4,6,3,7,2,8] .
[1,5,4,6,3,2,7,8] 끝까지 정렬을 했으면 다시 처음부터 비교합니다.
[1,5,4,6,3,2,7,8] .
[1,4,5,6,3,2,7,8] 5,6은 넘어가고 6,3 순서를 바꿔줍니다.
[1,4,5,3,6,2,7,8] .
[1,4,5,3,2,6,7,8] 다시 처음부터 비교합니다.
[1,4,3,5,2,6,7,8] .
[1,4,3,2,5,6,7,8] 다시 처음부터
[1,3,4,2,5,6,7,8] .
[1,3,2,4,5,6,7,8] 다시 처음부터
[1,2,3,4,5,6,7,8] 정렬 끝
풀이 코드
function solution(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length-i-1; j++) {
// 두 수를 비교하여 앞 수가 뒷 수보다 크면 두 수를 서로 교환
if (arr[j] > arr[j+1]) [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
}
}
return arr;
}
console.log(solution([5, 1, 7, 4, 6, 3, 2, 8]));시간복잡도
시간복잡도를 계산하면, (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2이므로, O(n^2) 입니다. 또한, Bubble Sort는 정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2) 으로 동일합니다. (개선된 Bubble Sort가 존재하긴 하나, 이번 장은 기초를 다지기 위한 학습이므로 넘어가겠습니다.)
공간복잡도
주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 입니다.
장점
- 구현이 매우 간단하고, 소스코드가 직관적입니다.
- 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. => 제자리 정렬(in-place sorting)
- 안정 정렬(Stable Sort) 입니다.
단점
- 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적입니다.
- 정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 됩니다.
REFERENCE
