Bubble Sort

버블정렬의 기본적인 구조

• 인접한 두 요소를 비교한다.
• 첫번째 인덱스의 값과 두번째 인덱스의 값, 두번째 인덱스의 값과 세번째 인덱스의 값을 비교하여, 정렬하는 방법이다.

arr = [5,4,3,2,1]이라고 하는 배열의 예를 들면,

// 전체 배열의 길이만큼 순회하면서 버블정렬을 하게 될 건데, 이전 인덱스 값이 현재 인덱스 값보다 크면 자리를 바꾸는 방식이 버블정렬이다. 

//그러니까 첫번째에는 인덱스 0번 값인 5를 가지고 비교를 할텐데, 
//arr[0]이 arr[1]보다 크기 때문에 자리를 바꾼다. 
  >>>> [4,5,3,2,1]
//그리고 두번째에는 arr[1]이 arr[2]인 3보다 크기 때문에, 
  >>>> [4,3,5,2,1]
//그리고 세번째에는 arr[2]가 arr[3]인 2보다 크기 때문에, 
  >>>> [4,3,2,5,1]
//마지막으로는 arr[3]이 arr[4]인 1보다 크기 때문에,
  >>>> [4,3,2,1,5]
//이런식으로 정렬을 하게 되고, 이것을 버블정렬이라고 부른다. 

이런 정렬을 전체 배열의 길이만큼 반복을 하는데,
이 때 이미 가장 마지막 자리 한 자리는 위치가 지정이 되므로 순회를 하지 않아도 된다.
그래서 자리를 바꾸는 행위는 (전체 배열의 길이 -1 -위치가 정해진 자리 수) 만큼만 순회를 하면 된다.

다시 말하면 시간복잡도는 for loop을 2번 적용하기 때문에 제곱이 된다.
그래서 효율적이지는 못한 정렬 방법이라고 생각이 되지만, 상대적으로 다른 정렬에 비해서 쉽게 작성할 수 있다.

const swaps = (idx1, idx2, arr) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}


const bubbleSort = function (arr) {

  for(let n = 0; n< arr.length; n++){
    let cnt = 0
    
  for (let i = 0; i< arr.length-1-n; i++){
    if(arr[i] > arr[i+1]){ 
      cnt++
      swaps(i, i+1, arr)
      }
    }
    if(cnt === 0){
      break;
    }
  }

  return arr
};

처음에는 아래와 같이 풀었는데, 마지막 문제인 Advanced문제가 해결이 안되었다.
알고보니까 효율성?의 문제였는데, 사실 시간복잡도에 대한 효율성의 문제는 아닐 것이라고 생각을 처음에는 했었다. 단순히 어차피 n번의 순회를 해야하기 때문에 효율적이지 못하다고 생각했었지만,
콘솔에 찍어보니, n의 제곱의 시간 복잡도를 정렬이 되어 있는 경우의 한에서 n번 순회로 바꿀 수 있었기 때문에, 어느정도 효율성을 줄 수 있다고 생각을 하게 되었다.

그렇지만 위의 코드처럼 작성을 다시 해서, 정렬이 잘 되어 있는 경우에는 swap을 하지 않고, 더 이상 코드를 진행하지 않으며 바로 리턴을 하게 하니까, 마지막 advanced 문제가 해결이 되었다.
아래는 손코딩 내용. 어려울 땐 이렇게 적어보라고 했다....