단순 선택 정렬

1. 단순 선택 정렬

단순 선택 정렬은 컬렉션의 가장 작은 요소부터 정렬을 시작해 알맞은 위치로 옮기며 정렬하는 알고리즘입니다. 단순 선택 정렬의 시간복잡도는 O(n^2)입니다.

다음과 같은 배열을 단순 선택 정렬로 정렬해보겠습니다.

---

우선 배열에서 가장 작은 요소를 선택합니다. 그리고 배열의 맨 앞의 요소와 자리를 바꿔줍니다.

이때 앞 부분(초록칸)은 정렬된 부분이라고 하고, 그 뒤쪽 부분들은 정렬되지 않은 부분이라고 합니다.

---

마찬가지로 정렬되지 않은 부분에서 가장 작은 요소를 선택해서 정렬되지 않은 부분의 첫 번째 요소와 자리를 바꿔줍니다. 하지만 가장 작은 요소인 3이 맨앞에 있으므로 그대로 남겨둡니다.

---

이제 남은 부분에 대해서도 가장 작은 요소를 선택하고 맨 앞 요소와 바꾸는 작업을 모든 부분이 완료될 때까지 수행합니다. 이때 마지막 요소는 따로 정렬하지 않아도 정렬된 상태이므로 정렬 작업을 총 n길이의 컬렉션에 대해서 n-1회 수행하게 됩니다.

 

 

2. 단순 선택 정렬 구현

단순 선택 정렬을 구현해보겠습니다. 정렬 방식 자체는 버블 정렬 방식을 이용할 것이고, 선택하는 부분에 대해서 알려드리겠습니다.

우선 교환 횟수(패스 횟수)는 총 n-1번 수행해야하므로 n-1번 만큼 반복하는 반복문을 만들어줍니다. 그리고 정렬되지 않은 부분에서 최솟값을 찾기위한 제어문들을 정의합니다. 우리는 정렬되지 않은 부분을 일일히 검사하면서 현재 정렬되지 않은 부분의 최솟값을 찾아내어 버블 정렬 시켜줍니다.

let simpleSelectSort = (arr) => {
    for (let i = 0; i < arr.length - 1; i++) {	//n-1회의 교환 횟수
        let minIndex = i;	//현재 수행하는 i번째의 인덱스를 우선 최소 인덱스 값으로

	//정렬되지 않은 부분에서 최소 인덱스값을 찾는 반복문
        for (let j = i + 1; j < arr.length; j++) {
            //최소 인덱스 값 변경
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        //정렬 자체는 버블 정렬방식 이용
        let temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
};

결과

---

https://github.com/Bam-j/algorithm-study/blob/main/study-code/sort/simple-select-sort.js

GitHub - Bam-j/algorithm-study: 블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록