08 선택 정렬

8.1 선택 정렬 소개

  선택 정렬은 버블 정렬과 비슷하지만 약간의 정렬 방식에 차이점이 있다. 많은 스왑을 통해서 가장 큰 값을 맨 뒤에 위치시키는 대신, 한 번에 모든 요소를 비교하여 가장 작은 값을 맨 앞에 위치시킨다. 그리고 그 요소를 제외한 나머지 요소들을 다 비교하여 가장 그 중 가장 작은 값을 첫 번째에 정렬된 요소 다음에 위치시킨다. 즉 배열내의 요소들 중 최솟값을 찾아 마지막에 바꾸어 맨 앞에 정렬시킨다. 

 

  우선 비교를 해야 하기 때문에 비교해야 할 요소들 중 가장 앞에 있는 값을 최솟값으로 잡고 그 다음 요소들과의 비교를 통해 최솟값을 찾는다. 이렇게 찾은 최솟값은 배열의 맨 앞에 정렬시키고, 그 다음 루프에서는 제외시키고 나머지를 비교한다. 이 과정을 반복하여 정렬하는 방식이 선택 정렬이다. 선택 정렬은 말 그대로 최솟값을 선택하여 앞에서 부터 차례대로 위치시켜 정렬시키는 방법이다. 선택 정렬도 버블 정렬과 마찬가지고 스왑을 해야하기 때문에 버블 정렬에서 만들어 놓은 스왑 알고리즘을 이용할 것이다.

 

의사코드

1. 함수를 만들고 배열을 인수로 받는다.

2. 최솟값을 저장할 변수를 만든다.

3. 처음 시작은 정렬의 첫 번째 요소가 가장 작은 값인것으로 저장하고 시작한다.

4. 그런 다음 반복문을 통해 다음 요소와 비교한다.

5. 만약 해당 요소보다 그 다음 요소의 값이 더 작을 경우 다음 요소를 최솟값을 저장한 변수에 할당한다.

6. 반대로 작지 않다면 계속 반복문을 진행한다.

7. 주의해야 할 점은 최솟값을 저장하는 변수에 저장되는 것은 값 그 자체가 아니라 해당 값의 인덱스를 저장하는 것이다!!

8. 루프의 한바퀴가 돌면 가장 앞에 최솟값을 정렬한다.

9. 가장 중요한 점은 루프의 한 바퀴가 돌고나면 가장 작은 최솟값은 가장 앞에 정렬되어 있으므로 그 다음 루프가 돌아갈때는 가장 앞에 있는 값을 제외하고 비교가 이뤄져야 한다. 그렇지 않으면 언제나 같은 최솟값을 찾게 된다.

 

8.2 선택 정렬 구현

function selectionSort(arr){
for(let i = 0 ; i < arr.length ; i++){
    let min = i;
    for(let j = i + 1 ; j < arr.length ; j++){
        if(arr[j] < arr[min]){
            min = j;
        }
    }
    if(arr[i] !== arr[min]){
        let temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}
return arr;

  스왑 알고리즘에 조건문을 단 이유는 arr[i]와 arr[min]이 같은 값이라면, 이미 최솟값이 제대로 정렬되어 있는 것이기 때문에 스왑을 할 필요가 없다. 그렇기 때문에 조건문으로 다른 경우에 스왑이 일어날 수 있도록 작성한것이다.