javascript 코딩테스트 - 버블 정렬 bubble sort

정렬은 코딩테스트나 알고리즘에서 많이 등장하는 주제 중 하나이다. 

정렬 알고리즘은 위키피디아에 검색해보면 정말 많이 등장한다.

https://en.wikipedia.org/wiki/Sorting_algorithm#Memory_usage_patterns_and_index_sorting

Sorting algorithm - Wikipedia

 

이 중에서 버블 정렬(bubble sort) , 선택 정렬 (selection sort), 삽입 정렬 (insertion sort), 합병 정렬 (merge sort), 퀵 정렬 (quick sort), 지수 정렬 (radix sort)을 살펴볼 예정이다.

 

이번 글에서는 버블 정렬 bubble sort 부터 살펴보자.

 

버블 정렬의 원리는 이러하다. (오름차순 기준)

1. 오른쪽에서 왼쪽으로(반대 방향으로도 가능) 두개씩 순서대로 값을 비교한다.

2. 만약 왼쪽값이 오른쪽값보다 크다면 두 값의 위치를 바꾼다.

3. 이걸 원소의 갯수만큼 반복한다. 

 

여기서 가장 핵심적인 원리는 두 값의 위치를 바꾸는 것이다.

 

예를 들어,

 

1 25 5 2  가 있다고 하면

 

(5랑 2를 비교했을 때 5가 더 크므로 스왑) 1 25 2 5

(25랑 2를 비교했을 때 25가 더 크므로 스왑) 1 2 25 5

(1이랑 2를 비교했을 때 2가 더 크므로 스왑 안 함) 1 2 5 25

 

그다음 반복문 사이클

(5랑 25를 비교했을 때 25가 더 크므로 스왑 안 함) 1 2 5 25

(2랑 5를 비교했을 때 5가 더 크므로 스왑 안 함) 1 2 5 25

 

그 다음 반복문 사이클

(5랑 25를 비교했을 때 25가 더 크므로 스왑 안 함) 1 2 5 25

 

끝

 

지금 반복문 사이클이 하나씩 줄어드는 것을 확인할 수 있다. 

이게 버블 정렬의 핵심이다.

버블 정렬은 반복문 사이클을 한 번 돌면 가장 작은 값이 맨 왼쪽에 오도록 (또는 가장 큰 값이 맨 오른쪽에) 확정지을 수 있다.

그러므로 이미 확정된 값을 제외하고 나머지끼리 반복문을 돌면 되는 것이다.

 

이를 코드로 구현하면 다음과 같다.

// 배열에서 두 원소의 위치를 바꿔주는 함수
function swap(arr, idx1, idx2){
    let temp =arr[idx1]
    arr[idx1] = arr[idx2]
    arr[idx2] = temp
}

function bubbleSort(arr){
    // 맨 오른쪽에서부터 시작
    for(let i=arr.length-1; i>0;i--){
        // 맨 오른쪽에서 시작하여 최솟값을 하나씩 확정짓기 때문에 범위가 i에 따라 변함
        for(let j=arr.length-1;j>arr.length-i-1;j--){
            // 2개 중 작은 값이 왼쪽에 올 수 있도록
            if(arr[j]<arr[j-1]){
                swap(arr, j,j-1)
            }
        }
    }
    return arr
}

위의 버블정렬 알고리즘은 최솟값을 하나씩 확정해나가는 방식으로 구성되어있는데 이 때 범위 계산이 조금 헷갈릴 수 있다.

최솟값보다는 최댓값을 확정해 나가는 게 이해하기가 좀 더 쉬울테니 i=0에서부터 반복문을 시작할 수 있게 구현해보면 좋은 연습이 될 것 같다.