선택 정렬 구현하기

선택 정렬이란

첫 번째 턴에서는 첫 번째 자료를 두 번째부터 마지막 자료까지 비교하여 최소값을 첫 번째 자료와 위치를 바꾸고, 그 다음 턴은 두 번째 자료를 마지막 자료와 비교하여 최소값을 두 번째 자료의 위치와 바꾸는 식으로 반복하여 정렬하는 방법이다.

선택 정렬 구현하기

선택 정렬을 자바스크립트로 구현하면 다음과 같다.

function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++){
      	// 가장 첫 번째 인덱스를 최소값의 인덱스로 초기화
        let lowest = i;
		// i가 최소값으로 시작하기 때문에 i+1부터 비교해야 함
        for (let j = i+1; j < arr.length; j++){
            // 현재 최소값이 비교하는 값보다 크다면 최소값의 인덱스를 비교하는 값(arr[j])으로 바꿈
          	if (arr[j] < arr[lowest]) {
                lowest = j;
            }
        }
      	// 내부 loop에서 바뀐 인덱스를 외부 loop에서 실제로 값을 서로 swap해줌
        let temp = arr[i]
        arr[i] = arr[lowest]
        arr[lowest] = temp;
    }
    return arr;
}

선택 정렬의 시간 복잡도

선택 정렬은 첫 번째 값과 나머지 값들을 비교해서 가장 작은 값의 인덱스를 찾고, 최소값을 첫 번째 값으로 보내주는 것을 반복한다. 버블 정렬과는 달리 최적화할 부분도 없고 아주 간단하다.

하지만 주어진 배열의 정렬 상태가 어떻든 항상 같은 방식으로 비교하기 때문에 중첩 for문으로 인하여 시간 복잡도는 O(N²)가 된다.

참고 자료

JavaScript 알고리즘 & 자료구조 마스터클래스 (유데미 강의)