[정렬 알고리즘] 선택정렬

선택정렬

- 선택 정렬이란, N-1번부터 1번까지의 자리에 대하여 해당 자리에 넣어야 하는 원소를 선택하는 알고리즘이다.

- 오름차순으로 정렬한다면, N-1번부터 1번까지의 자리에는 남아있는 수들 중 가장 큰 수를 선택하여 넣어야 한한다.

 

예를 들어보자.

이 배열에서 오름차순으로 정렬을 하고자 한다.

선택정렬이란 idx라는 임의의 변수에다가 제일 작은 숫자의 인덱스를 저장하면서

맨 앞 자리부터 작은 숫자로 채워나가는 정렬 방법이다.

idx는 우선 인덱스 0으로 초기화를 해놓고 이중 for문을 돌면서 arr[j] < arr[idx] 를 비교한다.

 

그렇게 되면 한 바퀴를 돌았을 때 즉 for 문이 끝났을 때는 idx에 가장 작은 값의 인덱스가 저장된다.

해당 인덱스에 위치한 값이 i가 가리키는 위치서부터 배열의 끝에 있는 값 중 가장 작은 값이 저장되는 것이다.

그 후 arr[i]에 arr[idx] 값을 넣어주고 arr[idx] 값에 arr[i] 값을 넣어주면 된다.

 

      function solution(arr) {
        let answer = arr;

        for (let i = 0; i < arr.length; i++) {
          let minIdx = i;
          for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIdx]) {
              minIdx = j;
            }
          }
          let prevItem = arr[i];
          arr[i] = arr[minIdx];
          arr[minIdx] = prevItem;
        }

        return answer;
      }

      let arr = [13, 5, 11, 7, 23, 15];
      console.log(solution(arr));

선택정렬을 이용하여 [13, 5, 11, 7, 23, 15] 배열을 오름차순으로 정렬했다.

시간복잡도는 2중 for문을 사용했기에 O(n) = n^2 이다.

결과는 다음과 같이 잘 나오는 것을 확인할 수 있다.