ㅠㅠ처음으로 제 시간 이내에 풀어서 냈다...!
이번주 화요일~금요일 동안 매일 아침 한 문제씩 풀면서 내내 성취감을 느낄 수 없어서 참 우울했는데,
어쩌다 쉬운문제 걸린거였어도 이렇게 뿌듯할 줄이야 ㅠㅠ!
오늘 문제는 버블정렬에 관한 알고리즘 문제다.
버블정렬 알고리즘이란?
- 첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
- 두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
- 1, 2를 마지막까지 반복합니다. (마지막에서 두 번째 요소와 마지막 요소를 비교)
- 1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다.
- 1~3의 과정을 첫 요소부터 다시 반복합니다.
- 5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 번째로 밀려납니다.
- 1~3의 과정을 총 n번(배열의 크기) 반복합니다.
풀이 과정
아래와 같이 for문을 중첩하여 먼저 swapping을 구현해주었다.
안쪽 for문은 한 번 배열 순회이고,
바깥쪽 for문을 통해 배열의 길이만큼 또 반복해주었다.
for(let j=0; j<arr.length-1; j++){
for(let i=0; i<arr.length-1; i++){
if(arr[i]>arr[i+1]){
let x = arr[i+1];
arr[i+1] = arr[i];
arr[i] = x;
}
}//1~3과정임.
}이 상태에서 바로 arr를 리턴해줬더니 런타임 초과가 떴다.
구글링해보니... 아래와 같은 내용을 찾을 수 있었다.
장점
버블 정렬은 in place 알고리즘이기 때문에 메모리가 절약된다는 장점이 있다. 여기서 "in place"라는 것은 자료를 정렬할 때 추가적인 메모리 공간이 필요한 것이 아니고 데이터가 저장된 그 공간 내에서 정렬을 한다는 뜻이다.
또한 구현하기 매우 쉽다는 장점도 있다. 그 외에도 이미 정렬된 데이터를 순회하는 경우 O(n)번만 순회하면 되기 때문에 정렬이 되었는지 안되었는지 테스트하는 용도로 사용될 수도 있다.
단점
버블 정렬의 가장 큰 단점은 자료의 개수가 많아질수록 성능이 매우 떨어진다는 점이다. 왜냐면 최악의 경우 O(n^2)이 소요되기 때문이다. 만약 데이터가 위 이미지처럼 5개밖에 없다면 최대 25번 순회를 해야하지만 데이터가 1,000개라면 1,000,000번이나 순회를 해야한다.
Big O
- Worst Case: O(n^2): 정렬이 하나도 안되어있는 경우
- Best Case: O(n): 이미 정렬이 되어있는 경우
버블 정렬은 최악의 경우에 O(n^2)의 시간 복잡도를 가진다. 왜냐하면 각 자리를 찾기 위해서 n번의 순회를 해야하며 n번의 회전 동안에 요소의 개수만큼 또 순회를 해야하기 때문이다. 그러나 이미 정렬이 되어있는 경우에는 한 번의 순회로 정렬 여부를 알 수 있다.
따라서, 안 쪽 for문이 한 번 작동이 끝났을 때 if문으로 어떤 요소도 위치가 바뀌지 않은 경우, break로 바깥for문이 더 이상 작동하지 않도록 해주었다.
또한 기존의 배열과 for문이 작동된 후의 배열을 구분시켜주기 위하여 초반에 slice메소드로 배열을 복사하였고,
배열이 같은지 여부를 판단할 때 JSON.stringify메소드로 두 배열(기존 배열 vs for문이 돌고난 후의 배열)을 비교해주었다.
코드를 종합해보면
const bubbleSort = function (arr) {
// TODO: 여기에 코드를 작성합니다.
let newArr = arr.slice(0) //배열을 복사한다
for(let j=0; j<newArr.length-1; j++){
for(let i=0; i<newArr.length-1; i++){
if(newArr[i]>newArr[i+1]){
let x = newArr[i+1];
newArr[i+1] = newArr[i];
newArr[i] = x;
}
}//1~3과정임.
if(JSON.stringify(newArr)===JSON.stringify(arr)){ //어떠한 요소도 바뀌지 않은 경우
break;
}
}
return newArr;
};