선택정렬 일반형

 

버블 정렬이 맨 앞부터 하나씩 올라가며 위치를 찾아가는 방법이라면 선택 정렬은 맨 아래부터 값을 쌓아나가는 방법이라고 할 수 있다.

배열을 한 바퀴 돌면서 가장 작은 값을 찾아내 0번 인덱스에 배치하고, 남은 정렬을 다시 순회하면서 그 중에서 가장 작은 값을 찾아내 그 다음 인덱스인 1번에 배치한다. 즉 계속해서 최솟값을 찾아내 스왑해 주는 것이다.

 

선택정렬의 3단계

 

• 1단계: 주어진 배열 중 최솟값 찾기
• 2단계: 값을 맨 앞에 위치한 값과 교체
• 3단계 맨 처음 위치를 뺀 나머지 배열을 위의 방법으로 반복하여 교체

 

//오름차순 정렬: 가장 작은 요소를 찾아 앞으로 이동

function selectionSort(array) {
    const len = array.length;
    // 배열의 처음부터 끝에서 두 번째 요소까지 순회.마지막 요소는 자동으로 정렬되므로 len-1까지만 반복
    for (let i = 0; i < len - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex !== i) {
            [array[i], array[minIndex]] = [array[minIndex], array[i]];
        }
    }
    return array;
}

 

 

예를 들어 i가 처음 순회를 시작하여 0이라고 하자.
이 때 이미 내부의 반복문을 통해 전체 배열을 통해 가장 작은 값을 알게 된다.
그 값이 있는 곳의 위치(인덱스)를 minIndex에 저장시켜 놓는다.

그리고 내부 반복문을 빠져 나와서, minIndex변수에 값의 변경이 있었을 경우,
즉, 가장 작은 원소의 인덱스로 변경되었을 경우,
배열의 i 번째 위치에, 현재로서 가장 작은 값을 가진 minIndex 인덱스를 가진 원소의 값을 저장한다.
따라서 이 경우 배열의 맨 앞에 전체 배열에서 최솟값이 이미 계산되어 위치하게 되는 것이다.
minIndex를 가진 원소에는 원래 i번째(이 경우 0번) 인덱스를 가진 값이 들어가게 된다.

다시 순회를 시작하고, 이번에는 i가 1이 된다. 최솟값은 이미 i가 0일 때 나왔으니,
이번에는 최솟값을 제외한 가장 작은값(차소값?)을 구하여 1번 인덱스를 가진 원소의 자리에 위치시킨다.

이 과정을 반복하여 전체 배열이 정렬된다.

즉, 중요한 것은 제어변수인 i 이다. minIndex는 i 번째 인덱스를 가진 원소에 값을 전달해주기 위한 보조 변수에 지나지 않으며 매 순회마다 바뀔 수 있는 것이다...

 

 

 

 

// 내림차순: 큰 값이 앞에 온다.

function selectionSortDescending(array) {
    const len = array.length;
    for (let i = 0; i < len - 1; i++) {
        let maxIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (array[j] > array[maxIndex]) {
                maxIndex = j;
            }
        }
        if (maxIndex !== i) {
            [array[i], array[maxIndex]] = [array[maxIndex], array[i]];
        }
    }
    return array;
}