Bubblesort

var bubbleSort = function(array) {
  let temp
  for (let i = 0; i < array.length - 1; i++) { // 순차적으로 비교하기 위한 반복문
    for (let j = 0; j < array.length - 1 - i; j++) { // 끝까지 돌았을 때 다시 처음부터 비교하기 위한 반복문
      console.log("i:",i,"j",j)
      console.log('array',array)
      if (array[j] > array[j + 1]) { // 두 수를 비교하여 앞 수가 뒷 수보다 크면
        temp = array[j]; // 두 수를 서로 바꿔준다
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
};



bubbleSort([7,4,5,6,8,3,1,2])

'i:' 0 'j:' 0
'i:' 0 'j:' 1
'i:' 0 'j:' 2
'i:' 0 'j:' 3
'i:' 0 'j:' 4
'i:' 0 'j:' 5
'i:' 0 'j:' 6
'i:' 1 'j:' 0
'i:' 1 'j:' 1
'i:' 1 'j:' 2
'i:' 1 'j:' 3
'i:' 1 'j:' 4
'i:' 1 'j:' 5
'i:' 2 'j:' 0
'i:' 2 'j:' 1
'i:' 2 'j:' 2
'i:' 2 'j:' 3
'i:' 2 'j:' 4
'i:' 3 'j:' 0
'i:' 3 'j:' 1
'i:' 3 'j:' 2
'i:' 3 'j:' 3
'i:' 4 'j:' 0
'i:' 4 'j:' 1
'i:' 4 'j:' 2
'i:' 5 'j:' 0
'i:' 5 'j:' 1
'i:' 6 'j:' 0
[
  1, 2, 3, 4,
  5, 6, 7, 8
]
[
  1, 2, 3, 4,
  5, 6, 7, 8
]

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

• i,j 가 갈 수록 줄어드는 부분이 이해가 잘 되지 않았다.
• 왜 -i를 하는지..
• 라고 생각했지만 console을 j에 찍고 보니
• 당연한거였다. 실제로 i는 줄어드는게 아니고, j가 줄어들기 때문에 j 안에서 console을 찍으니 i가 줄어든 것 처럼 보인것이었다.. (멍청하긴)
• 그리고 j에서 i를 i가 돌 때마다 빼주기 때문에 줄어드는 것이 당연했다.

• 처음에는 도대체 왜 빼주는 건가 했는데.. i가 한 번 돌 때마다

  [ 7 , 4]만 기준으로 봤을 때, 7이 4보다 크기 때문에 if절로 들어가게 되고, if절로 들어가면 7과 4가 바뀐다.

  [7,4] » [4,7]

  그리고 이 과정이 array끝까지 반복이 되기 때문에, 7은 계속해서 if절로 들어가고 바뀌고 끝으로 밀려나게 된다.

  [… 7]

  그럼 이제 7은 필요 없는 수가 되어버린다. (앞에서 이미 비교를 다 하고 난 다음이기 때문)

  혹시 7보다 더 큰수가 존재한다고 해도 이미 7과 비교를 해서 7보다 크기 때문에 swap이 일어나질 않게 되고 계속 array[j]가 7이었다가 더 큰 수를 만나는 순간 array[j]는 7보다 더 큰 수가 되어 뒤로 밀려나게 된다.

  이 과정을 반복 하다보면 큰 수는 결국 뒤로 밀리고, 작은수는 앞으로 오게 된다.

  결국 이미 비교가 끝난 수는 필요 없는 수가 되어버린다.