버블 정렬

문제

• 버블 정렬(buble sort)은 순차적으로 배열을 순회하면서 인접한 두 요소를 비교하여 작은 요소를 왼쪽으로, 큰 요소를 오른쪽으로 교환한다.
• 버블 정렬은 가장 간단하지만 가장 느린 정렬 알고리즘이다.
• 시간 복잡도: O(n2)

버블 정렬을 통해 주어진 배열(array)을 정렬하는 함수를 구현하라. 단, 어떠한 빌트인 함수도 사용하지 않고 for 문을 사용하여 구현하여야 한다.

function bubbleSort(array) {

}

console.log(bubbleSort([2, 4, 5, 1, 3]));     // [1, 2, 3, 4, 5]
console.log(bubbleSort([5, 2, 1, 3, 4, 6]));  // [1, 2, 3, 4, 5, 6]
console.log(bubbleSort([3, 1, 0, -1, 4, 2])); // [-1, 0, 1, 2, 3, 4]

풀이 과정 설계

배열안의 임의의 서로 다른 두 수(i, j)를 뽑아 비교한다. 오름차순으로 정렬한다면 i가 j보다 작을 때(i < j), array[i]가 array[j]보다 작아야 한다.

따라서 만약 array[i]가 array[j]보다 크다면, 두 수를 교환해주도록 하자.

풀이 과정

function bubbleSort(array) {
  for ( let i = 0; i < array.length; i++ ) {
    for ( let j = i + 1; j < array.length; j++ ) {
      if ( array[i] > array[j]) [array[i], array[j]] = [array[j], array[i]];
    }
  }
  return array;
}

console.log(bubbleSort([2, 4, 5, 1, 3]));     // [1, 2, 3, 4, 5]
console.log(bubbleSort([5, 2, 1, 3, 4, 6]));  // [1, 2, 3, 4, 5, 6]
console.log(bubbleSort([3, 1, 0, -1, 4, 2])); // [-1, 0, 1, 2, 3, 4]

풀이 과정 설계에서 언급했듯이 서로 다른 두 수를 뽑아 비교해야 하므로 j는 i + 1인 수에서 시작하도록 했다.