Algorithm problem-04

1. 문제

• 정수를 오름차순으로 정렬한다
• 버블 정렬을 이용하여 코드를 작성한다
• 기존의 정렬 method(arr.sort)는 금지한다

2. 시도
3. 수도코드

// 이 경우는 n번 인덱스를 기준으로 잡고 뒤에까지 다 비교를 해보는 방식
// 어드밴스드를 제외하고는 통과하지만, 효율이 떨어짐
const bubbleSort = function (arr) {
  if (arr.length === 0) {return [];}
  for (let i = 0; i < arr.length - 1; i++) {
    let cnt = 0
    for (let j = i+1; j < arr.length; j++) {
      if (arr[i] >= arr[j]) { // 같은 경우를 처음에는 배제했는데
      // 같은 경우도 뒤로 미뤄줘야 중간에 중복되는 값에 걸려서 뒤의 값을
      // sort 못하는 케이스가 발생하여 중복값도 미루기로 하였음
        let a = arr[j];
        arr[j] = arr[i];
        arr[i] = a;
        cnt++
      } 
      // else { // 0인덱스일 때 한번도 안바뀌면 브레이크를 걸도록 해보자
      //   break; // 이 지점이 아닌듯 하다
      // }
    }
    //if (cnt === 0) break;
    //break // 이 지점도 아니다
  }
  return arr;
}

4. 레퍼런스

const bubbleSort = function (arr) {
  // base case
  if (arr.length === 0) {return [];}
  // recursive case
  // 처음의 케이스는 n번 인덱스값을 기준으로 뒤에까지 다 비교해서 밀어놓는 방식
  // sort는 잘 되지만, 모든 인덱스를 전부 비교해줘야 함, 콜스택이 많이 쌓임
  for (let i = 0; i < arr.length - 1; i++) {
    let cnt = 0;
    // 한바퀴를 돌때마다 가장 큰 수가 뒤에 쌓이므로, 미뤄놓은 인덱스를 제외하기 위해
    // 맨 뒤의 값에 i를 더해준다, 바퀴를 돌았을 때에 바뀌는 값이 없다면 정렬된 상태
    // 그 때에 브레이크를 걸어주고, 탈출하게 하면 좀 더 효율적인 코드가 된다
    for (let j = 0; j < arr.length - 1 + i; j++) {
      if (arr[j] > arr[j + 1]) {
        let big = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = big
        cnt++ // 값을 스왑할 때마다 카운트를 올려서 탈출 지점을 찾는다
      } 
    }
    if (cnt === 0) break; // 바뀐 값이 없다면 정렬상태임, 그때 탈출한다
  }
  return arr;
}