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

📍 선택정렬 (Selection Sort)

가장 작은 값을 찾아 선택한다.

 정렬되지 않은 배열의 첫 번째 원소부터 현재 원소이고, 그 뒤의 모든 원소를 비교해가며 가장 작은 원소를 찾는다. 가장 작은 원소를 현재 원소와 교체한다. 그러면 점점 앞에서부터(가장 작은 수부터) 순서대로 정렬되어간다.

우리가 실제로 실물 카드를 정렬한다고 했을 때, 선택정렬을 사용할 사람은 없을 것 같다. 가장 작은 수를 찾아서 앞에다가 놓아가며 정렬하는 원리이지만 가장 작은 수를 맨 첫 번째 원소와 교체하기 때문이다. 우리가 실물 카드를 가지고 있다면 교체가 아니라 그냥 작은 수를 앞에다가 놓았을 것이다. 하지만 프로그램으로 구현하려면 원소의 자리를 채워주기 위해 교체가 필요했다. 실제 세상에서 사용되지는 않지만 프로그램으로 구현하기에는 매우 쉽고 간단하다.

 

📍 C++ 구현 코드

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        for(int i=0;i<n-1;i++){
            int minn = i;
            for(int j=i;j<n;j++){
                if(nums[minn]>nums[j]){
                    minn = j;
                }
            }
            swap(nums[minn], nums[i]);
        }
        return nums;
    }
};

https://leetcode.com/problems/sort-an-array/ 에서 위의 코드를 실행시킬 수 있습니다. (testcase는 통과하지만 시간초과 발생)

 

📍 코드 동작 원리

i 인덱스를 minn으로 설정한다. 그리고 그 뒤 원소들을 모두 nums[minn]과 비교해가며 가장 작은 최솟값을 찾는다. 최솟값을 nums[minn]과 swap한다. 이 과정을 반복하여 점점 앞에서부터 가장 작은 원소가 채워지게 된다. i 인덱스를 기준으로 이전은 정렬된 상태, i인덱스부터 맨 마지막 원소까지는 정렬되지 않은 상태이다.

 

📍 시간복잡도(time complexity)

선택정렬은 이중 for문으로 구현된다. 바깥 for문의 index i는 0부터 n-2까지, 안쪽 for문의 인덱스 j는 i부터 n-1까지 돌아간다. 결국 시간복잡도는 O(n^2)이다. 아래 사진을 참고하면 정확하게 알 수 있다. 

 

📍 Unstable / In-Place

선택정렬은 Unstable한 알고리즘이다.!! 원인은 swap이다. 뭔가 값을 찾아서 swap을 하는 알고리즘은 거의(다 인것 같지만 혹시 몰라서) Unstable인 것 같다. (bubble sort는 swap을 하지만 바로 앞에 붙어있는 원소랑 하기 때문에 stable한 성질을 유지할 수 있다.)

아래 사진은 선택 정렬에서 unstable하게 정렬되는 예시이다. 3'이 원래 3보다 앞에 있었지만 swap이 일어나서 3보다 뒤에 배치되었다.

또한 In-Place 알고리즘이다. 선택 정렬은 주어진 배열 안에서 원소를 swap 해가며 정렬을 진행하기 때문에 주어진 배열 이외에는 크게 메모리를 사용하는 부분이 없어 In-Place 알고리즘이다.

---

 

음 선택정렬은 이해도 구현도 좀 쉽다. 가장 작은 값을 선택한다 선택정렬