버블 정렬이란 ?
정렬 알고리즘 중 하나
버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말합니다.
버블정렬의 단점
이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있습니다.
버블정렬의 진행과정
아래와 같은 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
이러한 정렬 방식을 ‘버블 정렬’이라고 합니다.
버블정렬 코드로 나타내기
function solution(arr) {
let answer = arr;
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length; j++) {
if (arr[j] > arr[j + 1])
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
return answer;
}내 경우에 최악의 경우를 생각해보면 for문을 왜 저렇게 작성되어있는지 직관적으로 이해하기 쉬웠다
최악의 경우 : 정렬되지 않은 배열에서 제일 작은수가 제일 뒤에 있는경우
for문이 한번 돌때마다 한번만 swap이 일어나므로(한칸만 앞으로 이동할 수 있다) 제일 앞으로 가기위해서는 for문이 n-1번 돌아야 한다
- for (let i = 0; i < arr.length - 1; i++) n-1번의 for문을 돈다는 것 말고는 크게 의미가 없다
출처 boostcourse 모두를 위한 컴퓨터 과학
인프런 자바스크립트 알고리즘 문제풀이
