Toy#4 bubbleSort

문제

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.
버블 정렬(bubble sort)은 여러 정렬 알고리즘(삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬 등) 중 가장 기본적인 알고리즘입니다.

버블 정렬 알고리즘은 아래와 같습니다.

1. 첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
2. 두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
3. 1, 2를 마지막까지 반복합니다. (마지막에서 두 번째 요소와 마지막 요소를 비교)
4. 1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다.
5. 1~3의 과정을 첫 요소부터 다시 반복합니다.
6. 5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 번째로 밀려납니다.
7. 1~3의 과정을 총 n번(배열의 크기) 반복합니다.

이 모습이 마치 '거품이 밀려 올라가는 것과 같은 모습'과 같아서 bubble sort라고 부릅니다.

let output = bubbleSort([2, 1, 3]);
console.log(output); // --> [1, 2, 3]

Advanced

• 아래의 힌트를 바탕으로 (최선의 경우) 수행 시간을 단축할 수 있도록 코드를 수정해보세요.
• 위에서 설명된 알고리즘 1~3의 과정 중 어떤 요소도 위치가 바뀌지 않은 경우, 배열이 정렬된 상태라는 것을 알 수 있습니다.

풀이

1. 문제의 1~3번을 기준 삼아 시도

const bubbleSort = function (arr) {

  for(let i = 0; i < arr.length; i++){
    let temp = arr[i];
    if(temp > arr[i+1]){
      arr[i] = arr[i+1];
      arr[i+1] = temp;
    }
  }
  
  return arr;
};

➡️ 위의 코드는 arr.length가 3일때에만 작동하고, 그 외의 케이스에서는 오류

---

2. arr.length가 5인 경우를 기준 삼아 시도

const bubbleSort = function (arr) {

  for(let i = 0; i < arr.length; i++){
    let temp;
      for(let j = 0; j < arr.length - 1;j++){
        if(arr[j] > arr[j + 1]){
          temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
      if(!temp) break;
  }

  return arr;
};

/*

arr = [5, 4, 3, 2, 1] 인 경우, 이중 for문을 돌린다면 

i=0 
j=0  arr[0] > arr[1] => temp = arr[0] = 5 => [4, 5, 3, 2, 1]  
j=1  arr[1] > arr[2] => temp = arr[1] = 5 => [4, 3, 5, 2, 1]
j=2  arr[2] > arr[3] => temp = arr[2] = 5 => [4, 3, 2, 5, 1]
j=3  arr[3] > arr[4] => temp = arr[3] = 5 => [4, 3, 2, 1, 5]
j=4  arr[4] > arr[5] => false 이기 때문에 if문 실행 X
temp = 5 이므로 i++

=> arr = [4, 3, 2, 1, 5]

i=1
j=0  arr[0] > arr[1] => temp = arr[0] = 4 => [3, 4, 2, 1, 5]  
j=1  arr[1] > arr[2] => temp = arr[1] = 4 => [3, 2, 4, 1, 5]
j=2  arr[2] > arr[3] => temp = arr[2] = 4 => [3, 2, 1, 4, 5]
j=3  arr[3] > arr[4] => false 이기 때문에 if문 실행 X
j=4  arr[4] > arr[5] => false 이기 때문에 if문 실행 X
temp = 4 이므로 i++

=> arr = [3, 2, 1, 4, 5]

i=2
j=0  arr[0] > arr[1] => temp = arr[0] = 3 => [3, 2, 1, 4, 5]
j=1  arr[1] > arr[2] => temp = arr[1] = 3 => [2, 3, 1, 4, 5]
j=2  arr[2] > arr[3] => temp = arr[2] = 3 => [2, 1, 3, 4, 5]
j=3  arr[3] > arr[4] => false 이기 때문에 if문 실행 X
j=4  arr[4] > arr[5] => false 이기 때문에 if문 실행 X
temp = 3 이므로 i++

=> arr = [2, 1, 3, 4, 5]

i=3
j=0  arr[0] > arr[1] => temp = arr[0] = 2 => [1, 2, 3, 4, 5]
j=1  arr[1] > arr[2] => false 이기 때문에 if문 실행 X
j=2  arr[2] > arr[3] => false 이기 때문에 if문 실행 X
j=3  arr[3] > arr[4] => false 이기 때문에 if문 실행 X
j=4  arr[4] > arr[5] => false 이기 때문에 if문 실행 X
temp = 2 이므로 i++

=> arr = [1, 2, 3, 4, 5]

i=4
j=0  arr[0] > arr[1] => false 이기 때문에 if문 실행 X
j=1  arr[1] > arr[2] => false 이기 때문에 if문 실행 X
j=2  arr[2] > arr[3] => false 이기 때문에 if문 실행 X
j=3  arr[3] > arr[4] => false 이기 때문에 if문 실행 X
j=4  arr[4] > arr[5] => false 이기 때문에 if문 실행 X
temp = undefined 이므로 break으로 for문 탈출

*/

---

3. 레퍼런스 코드

const getSwap =  (idx1, idx2, arr) =>  {
  // 1) 임시 변수를 활용
  // let temp = arr[idx1];
  // arr[idx1] = arr[idx2];
  // arr[idx2] = temp;

  // 2) Destructuring assignment를 활용(arr가 reference type이라 가능) 
  return [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};

const bubbleSort =  (arr) => {
  const arrLength = arr.length;

  for (let i = 0; i < arrLength; i++) {
    let swaps = 0;

    for (let j = 0; j < arrLength - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swaps++;
        getSwap(j, j + 1, arr);
      }
    }
    if (swaps === 0) break;  
  }

  return arr;
};

/*

# CASE 1

arr = [2, 1, 3]

i=0, swaps=0
j=0 arr[0] > arr[1] => swaps=1, getSwap(2, 1, arr) => arr = [1, 2, 3]
j=1 arr[1] > arr[2] => false

i=1, swaps=0
j=0, arr[0] > arr[1] => false

swap이 0이므로 for문 탈출

# CASE 2

arr = [5, 4, 3, 2, 1] 

i=0 
j=0  arr[0] > arr[1] => swaps=1, getSwap(5, 4, arr) => arr = [4, 5, 3, 2, 1]
j=1  arr[1] > arr[2] => swaps=2, getSwap(5, 3, arr) => arr = [4, 3, 5, 2, 1]
j=2  arr[2] > arr[3] => swaps=3, getSwap(5, 2, arr) => arr = [4, 3, 2, 5, 1]
j=3  arr[3] > arr[4] => swaps=4, getSwap(5, 1, arr) => arr = [4, 3, 2, 1, 5]

=> arr = [4, 3, 2, 1, 5]

i=1
j=0  arr[0] > arr[1] => swaps=1, getSwap(4, 3, arr) => arr = [3, 4, 2, 1, 5]
j=1  arr[1] > arr[2] => swaps=2, getSwap(4, 2, arr) => arr = [3, 2, 4, 1, 5]
j=2  arr[2] > arr[3] => swaps=3, getSwap(4, 1, arr) => arr = [3, 2, 1, 4, 5]

=> arr = [3, 2, 1, 4, 5]

i=2
j=0  arr[0] > arr[1] => swaps=1, getSwap(3, 2, arr) => arr = [2, 3, 1, 4, 5]
j=1  arr[1] > arr[2] => swaps=2, getSwap(3, 1, arr) => arr = [2, 1, 3, 4, 5]

=> arr = [2, 1, 3, 4, 5]

i=3
j=0  arr[0] > arr[1] => swaps=1, getSwap(2, 1, arr) => arr = [1, 2, 3, 4, 5]

=> arr = [1, 2, 3, 4, 5]

i=4
안쪽 for문은 지나치게 되고, swaps가 0이기 때문에 break로 for문 탈출

*/

✅ 음 이렇게 다 써내려가면서 보니, 레퍼런스 코드 동작 방식이 훨씬 효율적이네