버블 정렬
드디어 만났다 버블 정렬...
부트캠프 시작 전에 들었던 무료 강의에서 버블 정렬을 맞닥뜨린 적이 있었는데
오늘은 데일리 코딩에서 버블 정렬을 직접 구현해보는 시간을 가지게 되었다.
테스트는 통과가 되었으나... 래퍼런스를 보니 내가 너무 단순하게 구현한 것 같아서 (+시간 복잡도가 잘 고려가 안 되지 않았나?) 래퍼런스와 내 풀이를 비교해서 정리해보려고 한다
버블 정렬이란?
첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿈.
두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿈.
1, 2를 마지막까지 반복. (마지막에서 두 번째 요소와 마지막 요소를 비교)
위 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려남.
1~3의 과정을 첫 요소부터 다시 반복.
두 번째로 큰 요소가 배열의 마지막 바로 두 번째로 밀려남.
1~3의 과정을 총 n번(배열의 크기) 반복.
(모두 정렬될 때까지)
이 모습이 마치 '거품이 밀려 올라가는 것과 같은 모습'과 같아서 bubble sort라고 부름.
내 풀이
const bubbleSort = function (arr) {
//반복문으로 순회하고, if 조건문으로 앞에거랑 그 다음 거 비교해서 자리 바꾸도록 해야함
//마지막까지 돌았는데 바뀐 녀석들이 없으면 정렬된 상태이므로 탈출 조건을 만들어주어야 할듯?
//자리 바꿈이 없음을 어떻게 알지 ?
//변수 before과 after를 만들어서 그 두 수가 undefined 상태이면 탈출하도록 하자 (한 번도 자리바꿈이 일어나지 않았으므로)
let before
let after
for(let i=0;i<arr.length;i++){
if(arr[i]>arr[i+1]){
before=arr[i]
after=arr[i+1]
arr[i] = after
arr[i+1] = before
}//이 조건문이 돌지 않으면 before와 after는 undefined상태
}
if(before === undefined && after === undefined){
return arr;
}
return bubbleSort(arr);
//재귀를 돌려주었기 때문에 다음 턴에서는 다시 before와 after가 undefiend인 상태부터 시작한다.
};
래퍼런스 분석
const swap = function (idx1, idx2, arr) {
// 두 변수를 바꾸는 방법 세 가지
// 1) 임시 변수를 활용한 방법 (내가 사용한 것과 비슷)
// let temp = arr[idx1];
// arr[idx1] = arr[idx2];
// arr[idx2] = temp;
// 2) Destructuring assignment를 활용한 방법
// (arr이 reference type이라 가능)
// 하나씩 바꾸면 첫번째 바꾼 인덱스의 값이 이미 바뀌어버리니까
// 이렇게 동시에 바꾸면 그 문제 해결 가능할듯
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
// 3) XOR 연산을 활용한 방법
// arr이 reference type이라 가능
// arr[idx1] ^= arr[idx2];
// arr[idx2] ^= arr[idx1];
// arr[idx1] ^= arr[idx2];
};
let bubbleSort = function (arr) {
let N = arr.length;
for (let i = 0; i < N; i++) {
// swap 횟수를 기록한다.
// 어떤 요소도 swap되지 않은 경우, 배열은 정렬된 상태이다.
let swaps = 0;
// 매 반복(iteration)마다 i번째로 큰 수가 마지막에서 i번째 위치하게 된다.
// 이미 정렬된 요소는 고려할 필요가 없으므로, 'j < N - 1 - i'만 비교하면 된다.
for (let j = 0; j < N - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swaps++;
swap(j, j + 1, arr);
}
}
if (swaps === 0) {
break;
}//
}
return arr;
};-
래퍼런스에서는 바꾼 횟수를 변수에 기록하도록 해서 swaps가 0일 때 더이상 비교하지 않도록 함.
-
swap 함수를 만들 때 XOR 연산 사용하는 방법이 잘 이해가 안 갔는데
검색하다가 이것에 대해 설명해둔 블로그를 찾았다. 감사합니다
살펴보니 이진법을 이용해서 값을 정렬하는 것 같았는데, 사실 완벽하게 이해한 건 아니다. -
이해한 바로는 두 가지 개념 정도를 이해해야 하는데
-
XOR 연산자를 사용했을 때는 주어진 숫자를 이진법으로 바꾸어서 각 자리수를 비교할 때 1이 한 개만 있으면 1이 나오고 그 외에는 다 0이 나오게된다.(피셋 언어 논리 문제 풀 때 배웠떤 배타적 선언과 비슷)
2.두 수 (x,y)를 XOR한 결과값이 z일 때 z^x = y, z^y = x 가 된다. (이걸 이용해서 자리를 바꾼다)
- '매 반복(iteration)마다 i번째로 큰 수가 마지막에서 i번째 위치하게 된다. 이미 정렬된 요소는 고려할 필요가 없으므로, 'j < N - 1 - i'만 비교하면 된다.'
라는 말이 잘 이해가 안 갔는데 바깥 반복문의 i가 0일 때 안쪽 반복문에서는 0부터 맨 끝 인덱스의 앞까지 j가 순회하게 되고, 실제로 반복문 내부에서 비교는 arr[j]와 arr[j+1]까지 하기 때문에 맨 끝 인덱스와도 비교를 하게 된다. 그 과정에서 가장 큰 수(0번째로 큰 수)는 맨 끝 인덱스, 그러니까 마지막에서 0번째에 위치하게 되는데, 그렇게 이미 정렬된 수까지 크기 비교에 포함시킬 필요는 없기 때문에 안쪽 반복문에서 j의 한계를 이미 정렬된 요소의 바로 앞 항목의 전까지!로 만들어준다. (조심해야 하는 것이 j는 j+1과 비교를 한다는 것!)
만약 미래의 내가 이걸 읽었는데 이해가 안 간다면 그냥 임의의 arr를 하나 만들어서 직접 반복문을 돌려보는 과정을 거치길 바란다 ^^... 그것이 가장 빠른 이해의 길...
