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)

선택 정렬(Selection Sort)

아리보리 | 2017.07.03 05:14 | 조회 176 | 추천 0 | 댓글 0

선택 정렬(Selection Sort)의 특징

  • 매 루프마다 최소값 또는 최대값을 선택해서 정렬하는 알고리즘
  • 비교 기반 정렬 알고리즘
  • 안정적이지 않은 정렬(동일한 키 값이 있을 경우 순서가 바뀔 수 있음)
  • 최악, 최적, 평균 모두 O(n^2)의 수행시간을 보임
  • 제자리 정렬

 

알고리즘

  1. 리스트를 순차적으로 탐색하면서 최대값/최솟값을 찾아낸다.
  2. 찾아낸 최대값/최솟값을 리스트의 맨 앞, 또는 맨 뒤 인덱스와 교환한다.
  3. 두번째에도 마찬가지로 순차적으로 탐색하여 찾아낸 최대값/최솟값을 리스트의 맨 앞, 또는 맨 뒤에서 두번째 인덱스와 교환한다.
  4. 위의 과정을 반복한다.

구현

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

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

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

                for (let i = 0; i < list.length; i++) {
                    let minIndex;
                    for (let j = i; j < list.length; j++) {
                        if (!minIndex || list[minIndex] > list[j]) {
                            minIndex = j;
                        }
                        console.log(j)
                    }
                    swap(list, i, minIndex);
                }

                return list;
            }
        };
        return selectionSort(list);
    }
}

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

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

const sortedData = new SelectionSort(data);

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