[정렬 알고리즘] - 선택 정렬(Selection Sort)

Donggu(oo)·2023년 2월 3일
0
post-thumbnail

1. 선택 정렬


  • 선택 정렬은 배열의 첫 요소 부터 선택하여 배열 끝까지 다른 요소들과 비교하면서 다른 요소들 중 선택한 요소보다 작은 값(최솟값)이 있을 경우 서로의 위치를 바꾼다(최솟값을 맨 앞에 둔다).

  • 선택 정렬은 arr[0] 요소와 다른 요소들을 비교하여 다른 요소가 arr[0] 보다 작을 경우 그 요소와 arr[0] 요소의 위치를 바꾼다. 이번엔 arr[1] 요소와 다른 요소들을 비교하여 다른 요소가 arr[1] 보다 작을 경우 서로의 위치를 바꾼다. 이 작업을 배열의 마지막 요소까지 반복한다.

의사 코드

  1. 배열의 첫 번째 요소를 최솟값으로 저장한다.
  2. 저장한 최솟값 보다 더 작은 숫자를 찾을 때까지 저장한 최솟값과 배열의 다음 요소들과 비교한다.
  3. 더 작은 숫자가 발견되면 더 작은 숫자를 새로운 최솟값으로 저장하고 배열이 끝날 때까지 계속 다시 찾는다.
  4. 최소값이 처음 시작한 값(인덱스)이 아닌 경우 두 값의 위치를 바꾼다.
  5. 배열이 정렬될 때까지 다음 요소를 최솟값으로 저장하여 이 과정을 반복한다.
// selection sort
function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        // 최솟값의 index 설정
        let lowest = i;
        // arr[i]의 다음 요소(arr[i + 1])들과 비교하면서
        for (let j = i + 1; j < arr.length; j++) {
            // 먼저 지정한 최솟값보다 더 작은 값이 나오면
            if (arr[j] < arr[lowest]) {
                // 더 작은 값의 index를 최솟값의 index로 변경한다.
                lowest = j;
            }
        }
        // 배열의 끝까지 비교한 후 처음 지정한 최솟값과 중간에 찾은 최솟값의 위치를 바꾼다.
        let temp = arr[i];
        arr[i] = arr[lowest];
        arr[lowest] = temp;
    }
    return arr;
}
console.log(selectionSort([6, 5, 7, 4, 1, 3]));  // [1, 3, 4, 5, 6, 7]

0개의 댓글