정렬관련해서 한번은 정리하고 올려야한다고 생각했는데,, 이제서야 공부하는 나 ,, 그래도 지금이라도 해서 다행이라고 생각하며 폿으팅을 해봅니다.
만약 배열이 있고, 순서대로 정렬하고 싶을 때 요소를 하나하나씩 돌면서 배열을 정렬하려고 한다.
1. 첫 번째 요소가 두 번째 요소보다 크다면 둘의 자리를 교환한다.
2. 두 번째 요소가 세 번째 요소보다 크다면 둘의 자리를 교환한다.
이 방식을 제대로 정렬이 될 때까지 한무 반복한다.
● 내가 처음에 적었던 답안
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if(arr[j] > arr[j+1]){
let bigger = arr[j];
let lower = arr[j+1];
arr[j+1] = bigger;
arr[j] = lower;
}
}
}
return arr
}
각각의 값을 저장하고 바꿔주었는데, 배열의 구조할당으로 더 간편하게 코드가 짧아진다는 걸 알게 됐다.
● 배열의 구조할당을 통한 답안
function bubbleSort(arr) {
for (let i = 0; i < arr.length; 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 arr
};심각히 짧아진다..
하지만 코드 최적화는 되었지만 실제 실행했을 경우에의 최적화는 이루어지지 않았다. 예를 들어 아래와 같이 배열이 있다고 했을 때,
const arr = [2, 1, 3, 4, 5]3이후로는 제대로 정렬이 되어있기 때문에 볼 필요가 없지만, 정렬이 제대로 이루어져있는 부분까지 for문을 돌고 있다.
● 코드 최적화
function bubbleSort(arr) {
let noSwaps;
for (let i = arr.length; i > 0; i--) {
noSwaps = true; // 외부 for 문 돌 때마다 이전 swap 기록 초기화
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
noSwaps = false; // 이번 순회에서 swap했다면 false 할당
}
}
if (noSwaps) break; // 지난 번 순회에서 swap하지 않았다면(true) 루프를 break;
}
return arr;
};매번 noSwap을 true로 주고, 만약에 자리를 바꾸는 행위를 이전에 했다면 for문을 break하지 않지만, 만약에 바꾸는 행위를 하지 않았다면 for문은 break하게 된다.
