자바스크립트 코딩테스트 강좌, 버블 소트 프로그램 2

문제 설명

주어진 정수 배열을 오름차순으로 정렬하는 프로그램을 작성하세요. 배열의 요소는 양의 정수와 음의 정수,
그리고 0이 포함될 수 있습니다. 기본적인 정렬 알고리즘인 버블 소트를 사용하여 구현해야 합니다.

버블 소트 알고리즘 설명

버블 소트는 가장 단순한 정렬 알고리즘 중 하나로, 인접한 요소들을 비교하여 정렬하는 방법입니다. 이
알고리즘은 반복적으로 배열을 순회하며 두 인접한 요소를 비교하여 필요에 따라 교환하는 방식입니다.
배열을 n번 순회하면 정렬이 완료됩니다. 매 번의 반복에서 가장 큰 요소가 배열의 끝으로 “거품”처럼
올라가게 되므로 ‘버블 소트’라는 이름이 붙여졌습니다.

버블 소트의 동작 과정

  1. 배열의 길이를 n이라고 할 때, n-1번의 반복을 수행합니다.
  2. 각 반복에서 인덱스 i를 0부터 n-1까지 순회 및 비교합니다.
  3. 두 인접한 요소를 비교하여 왼쪽 요소가 오른쪽 요소보다 큰 경우, 두 요소를 교환합니다.
  4. 이 과정을 통해 최대값이 일관되게 배열의 끝으로 이동하게 됩니다.
  5. 정렬이 완료될 때까지 이 과정을 반복합니다.

문제 풀이 과정

Step 1: 배열 선언

먼저 정렬할 배열을 선언합니다. 예를 들어, 다음과 같은 배열을 사용하겠습니다.

let arr = [64, 34, 25, 12, 22, 11, 90];

Step 2: 버블 소트 함수 작성

버블 소트를 구현하는 bubbleSort 함수를 작성합니다. 이 함수는 파라미터로 배열을 받아
정렬된 배열을 반환합니다.


function bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 요소 교환
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}
    

Step 3: 함수 호출 및 결과 출력

작성한 함수를 호출하여 결과를 확인합니다. 다음 코드와 같이 함수를 호출하고 결과를 출력합니다.


let sortedArr = bubbleSort(arr);
console.log("정렬된 배열:", sortedArr);
    

전체 코드 조합

모든 과정을 종합하여 최종적인 코드는 다음과 같습니다.


function bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

let arr = [64, 34, 25, 12, 22, 11, 90];
let sortedArr = bubbleSort(arr);
console.log("정렬된 배열:", sortedArr);
    

성능 분석

버블 소트의 시간 복잡도는 최악의 경우 O(n2)입니다. 이는 모든 요소를 한 번씩 비교해야
하기 때문에 발생합니다. 평균적인 경우 역시 O(n2)로 유지되며, 최선의 경우 (이미
정렬된 배열)에도 O(n)입니다. 따라서 버블 소트는 데이터가 적을 때는 효율적으로 사용할 수 있지만,
큰 데이터 세트에는 적합하지 않은 알고리즘입니다.

결론

이번 강좌에서는 버블 소트를 이용하여 배열을 정렬하는 방법을 알아보았습니다. 간단한 알고리즘이지만,
반복적으로 같은 작업을 수행하여 성능이 떨어질 수 있다는 점을 유의해야 합니다. 이러한 기초 알고리즘
의 이해는 더욱 복잡한 알고리즘을 접하는 데 중요한 초석이 될 것입니다. 다음 강좌에서는 더 효율적인
정렬 알고리즘인 퀵 소트(Quick Sort)를 다뤄보겠습니다.