[JavaScript/section 7] 02 - 버블 정렬

📌 문제

N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 문제이다. 정렬하는 방법은 버블 정렬이다.

 

🧐 버블 정렬(bubble sort)이란 무엇일까❓

• 주어진 배열에서 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘
  • 인접한 2개의 요소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
• 구현이 매우 간단하지만 비효율적인 방법이다. 평균 시간복잡도 O(N^2)

 

📝 풀이

function solution(arr) {
  let answer = arr;
  
  // 1회전을 수행할 때마다 정렬이 확정되는 요소가 하나씩 증가
  for (let i = 0; i < arr.length - 1; i++) {
    // j가 도는 범위는 하나씩 감소
    for (let j = 0; j < arr.length - (1 + i); j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return answer;
}

let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr));

 

🙇🏻 참고한 사이트

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog