정렬 알고리즘: 선택 정렬(Selection Sort)

 

선택 정렬 (Selection Sort)

: 정렬되지 않은 영역에서 가장 작은 값을 찾아서 맨 앞과 바꾸는 방식

• 정렬된 영역과 정렬되지 않은 영역으로 나눠서 계산함
• 배열의 정렬되지 않은 영역의 첫 번째 원소부터 마지막 원소까지 비교한 후 가장 작은 값을 첫 번째 원소와 교체함
• 바깥 반복문이 돌수록 정렬된 영역이 늘어나고, 안쪽 반복문의 횟수는 줄어드는 형태

 

 

 

 

선택 정렬의 성능

• 시간 복잡도: O(n²)
• 성능이 좋지 않음

 

 

 

선택 정렬의 장단점

장점

• 이해와 구현이 간단함

 

단점

• 성능이 O(n²)으로 별로 좋지 않음

 

 

 

예시: 숫자가 무작위로 들어있는 배열 정렬하기([4, 2, 3, 1])

• 배열의 원소가 n개라면 n-1번 반복시켜줘야 함
• 최솟값을 가진 인덱스를 저장할 변수를 만들어줌
• 바깥 반복문에서 배열의 시작으로 0이 아닌 i를 넣은 이유
  ⇒ 반복문을 진행할때마다 최솟값이 하나씩 정렬되기 때문에 정렬된 영역은 반복에서 제외하기 위한 것임

let arr = [4,2,1,3];

function SelectionSort(arr){
    for(let i = 0; i < arr.length - 1; i++){  // 👉 바깥 반복문
        let minValueIndex = i;  // 👉 최솟값의 인덱스를 저장할 변수
        for(let j = i + 1; j < arr.length; j++){ // 👉 정렬되지 않은 영역 순회
            if(arr[j] < arr[minValueIndex]){ // 👉 가장 작은 값을 발견하면
                minValueIndex = j;   // 최솟값의 인덱스를 변수에 저장
            }
        }

        let temp = arr[i];   // 👉 자리 바꾸기
        arr[i] = arr[minValueIndex];
        arr[minValueIndex] = temp;
    }
}

console.log("===== 정렬 전 =====");
console.log(arr); //  [ 4, 2, 1, 3 ]

SelectionSort(arr);

console.log("===== 정렬 후 =====");
console.log(arr); // [ 1, 2, 3, 4 ]

 

실행 흐름

• 1회전 (i = 0) 👉 바깥 반복문
  
  • minValueIndex = 0 (값은 4)
  • j = 1 ⇒ 2(arr[1]) < 4(arr[0]) → minValueIndex = 1
  • j = 2 ⇒ 1(arr[2]) < 2(arr[1]) → minValueIndex = 2
  • j = 3 ⇒ 3(arr[3]) > 1(arr[2]) → 그대로
  • 👉 4(arr[0]) ↔️ 1(arr[2]) 자리 바꿈 → [1, 2, 4, 3]
    ➡️ 가장 작은 숫자 1이 맨 앞으로 이동
• 2회전 (i = 1) 👉 바깥 반복문
  
  • minValueIndex = 1 (값은  2)
  • j = 2 ⇒ 4(arr[2]) > 2(arr[1]) → 그대로
  • j = 3 ⇒ 3(arr[3]) > 2(arr[1]) → 그대로
  • 👉 자리 바꿈 없음 → [1, 2, 4, 3]
    ➡️ 두 번째로 작은 숫자 2는 이미 제자리
• 3회전 (i = 2) 👉 바깥 반복문
  
  • minValueIndex = 2 (값은  4)
  • j = 3 ⇒ 3(arr[3]) < 4(arr[2]) → minValueIndex = 3
  • 👉 4(arr[2]) ↔️ 3(arr[3]) 자리 바꿈 → [1, 2, 3, 4]
    ➡️ 3이 제자리로 이동