AHRIBORI.COMv0.9
HomeAbout (2)Javascript (7)CSS (12)React (3)Webpack (1)Java (0)Node.js (4)ElasticSearch (1)자료구조 (8)알고리즘 (6)Selenium (1)Linux (2)Docker (1)Git (1)Tip (4)Issue (1)Memo (3)

버블 정렬(Bubble Sort)

아리보리 | 2017.07.03 05:20 | 조회 195 | 추천 0 | 댓글 0

버블 정렬(Bubble Sort)의 특징

  • 비교 기반 알고리즘
  • 안정적 정렬
  • 제자리 정렬
  • 최악 O(n^2), 최적 O(n)의 수행시간

 

알고리즘

  1. 리스트의 0번 인덱스와 1번 인덱스의 대소를 비교하여, 오름차순의 경우 0번 인덱스가 1번 인덱스보다 클 때 두 원소를 교환한다.
  2. 리스트의 1번 인덱스와 2번 인덱스의 대소를 비교하여, 마찬가지로 1번 인덱스가 더 크다면 2번 인덱스와 자리를 바꾼다.
  3. 반복하여 리스트의 마지막까지 도달하였다면 첫 번째 사이클을 마친 것이다. (0 ~ n)
  4. 다시 0번 인덱스로 돌아와 위의 과정을 반복하여 두 번째 사이클을 수행한다. (0 ~ n-1) 
  5. 같은 규칙으로 반복하여 정렬한다.

구현

class BubbleSort {
    constructor(_list) {
        const list = _list;

        const swap = (list, a, b) => {
            const temp = list[a];
            list[a] = list[b];
            list[b] = temp;
        };

        const bubbleSort = list => {
            if(Array.isArray(list)) {
                if (list.length === 0) {
                    return [];
                }

                for (let i = list.length - 1; i > 0; i --) {
                    for (let j = list.length - 1 ; j >= list.length - i; j --) {
                        if (list[j-1] > list[j]) {
                            swap(list, j, j-1);
                        }
                    }
                }

                return list;
            }
        };

        return bubbleSort(list);
    }
}

//----------------------------------

const data = [18, 15, 23, 28, 52, 59, 13];

const sortedData = new BubbleSort(data);

console.log(sortedData); // [13, 15, 18, 23, 28, 52, 59]