자료구조[선택정렬(Selection Sort)]

선택정렬이란?

정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아

정렬되지 않은 부분의 가장 앞의 데이터와 교환해나가는 알고리즘입니다.

직관적이고 단순한 정렬방법중 하나입니다.

정렬되지 않은 값중에서 가장 작은 숫자를 선택하는 방식으로 정렬을 진행합니다.

시간 복잡도

Worst : O(n²)

Average : O(n²)

Best : O(n²)

 

 

진행 방법

1. 주어진 배열이 있습니다.

5

3

2

1

4

 

2. 가장 첫번째 값을 작은 값이라고 가정하고 뒤로 가면서 비교를 합니다.

5

3

2

1

4

 

3. 작은 값을 하나씩 찾습니다. 첫번째로 3, 그다음 2, 그다음 1 , 4는 1보다 작으므로 1,  가장 작은 값을 찾아갑니다.

5

3

2

1

4

 

4. 가장 작은 값을 만나면 비교하던 숫자와 자리를 바꿉니다.

1

3

2

5

4

 

5.1은 가장 작은 값으로 정렬이 됐으므로 그 다음 인덱스인 3을 가장 작은 값으로 가정하고 다시 비교 합니다.

1

3

2

5

4

 

6. 앞쪽은 정렬이 됐으니 뒤로가면서 비교해보니 2가 가장 작으므로 2와 자리를 바꿔줍니다.

1

2

3

5

4

 

7. 그다음 인덱스로 가서 비교를 해보니 자기 자신이 가장 작으므로 그 자리에 정렬됩니다.

1

2

3

5

4

 

8. 4번째 인덱스와 마지막 인덱스를 비교 해보니 마지막 인덱스가 가장 작은 값이므로 위치를 바꿉니다.

1

2

3

4

5

 

이런식으로 앞에서부터 가장 작은 값으로 정렬을 해가며 오름 차순으로 정렬합니다.

 

이를 알고리즘으로 구현해보면

• 정렬기준이 되는 배열의 인덱스는 0부터 시작해서 1씩 증가하고 3번쨰 인덱스에서 끝납니다. →  i = 0; i < arr.length - 1; i++

 

• 정렬기준이 된 배열은 기준 + 1 부터 한칸씩 마지막 배열까지 비교하며 진행합니다. j = i + 1; j < arr.length; j++

 

• 가장 작은 값의 기준이 되는 인덱스를 저장합니다. minIdx = i

 

• 가장 작은 값의 기준배열을 가지고 마지막 배열까지 비교하는데 만약?

   가장 작은 값이 있다면 그 배열의 인덱스를 저장합니다. if ( arr[ min ] > arr[ j ] ) minIdx = j;

 

• 비교가 끝났다면 해당 값을 교환 해줍니다.

 

• 다시 다음 인덱스로 비교합니다. 위와 같은 과정을 반복 합니다.

 

코드 작성(Js)

function selectionsort(arr) {
    let n = arr.length
    for (let i = 0; i < n-1; i++) {
        let minidx = i;
        for (let j = i+1; j < n; j++) {
            if (arr[minidx]> arr[j]) {
                minidx = j;
            }
        }
        let temp = arr[i];
        arr[i] = arr[minidx];
        arr[minidx] = temp;
    }
    return arr;
}
console.log(selectionsort([5, 3, 2, 1, 4]))

 

선택정렬의 장점

1. 구현이 간단합니다.

    - 구현이 간단하여 이해하기 쉽습니다.

    - 단순 반복문과 조건문으로 이루어져 있어 간단한 문제나 초기 학습에 도움이 됩니다.

2. 공간 복잡도가 작습니다.

    - 입력 리스트 안에서 원소들을 직접 교환하면서 정렬을 수행하므로 초가적인 메모리를 필요로 하지 않습니다.

    - 

선택정렬의 단점

1. 시잔 복잡도가 큽니다.

    - 최악, 평균, 최선의 경우 모두 O( n² )의 시간 복잡도를 가지므로, 대부분의 상황에서 효율적이지 않습니다.

    - 입력 크기가 증가할수록 비효율성이 두드러집니다.

2. 비교 횟수가 많습니다.

    - 비교횟수가 n( n - 1 )/2 로 많이 발생하며, 비교 횟수는 입력 크기에 따라 크게 늘어납니다.

3. 다른 정렬 알고리즘보다 느립니다.

    - 퀵 정렬, 병합 정렬 등과 비교하면 성능 면에서 느린 편에 속합니다.

 

 

 

 

참조  - 혀니 c코딩