[알고리즘] 정렬알고리즘 #1 삽입정렬 (insertion Sort)

📍 삽입 정렬 (Insertion Sort)

삽입 정렬은 실제로 내가 카드를 가지고 있다고 생각하면 더 이해가 쉬운 것 같다. 정렬되지 않고 나열된 카드 중 두 번째 카드를 들어 손에 쥔다. 그러면 내가 두 번째 카드를 들고 있으므로 두 번째 칸이 빌 것이다. 바로 앞의 카드와 비교하여 내가 들고 있는 카드보다 크다면 앞 카드를 한 칸 뒤로 민다. 해당 카드 바로 뒤는 비어있다. 카드를 밀어서 빈 공간을 채워주면 된다. 이를 반복하다가 내가 들고 있는 카드보다 큰 카드가 나오면 지금 빈 공간에 내가 들고 있는 카드를 내려놓는다.

우리가 실제로 숫자카드를 가지고 정렬하고자 할 때 사용하곤 하는 직관적인 방법이라고 생각할 수 있다.

 

📍 C++ 구현 코드

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

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

 

📍 코드 동작 원리

삽입정렬은 i = 1부터 시작한다. 0번째 인덱스는 정렬된 상태이다. i 인덱스 앞의 요소들을 하나하나 now와 비교해간다.

i 인덱스보다 앞에 있는 원소가 now보다 크다면 now를 해당 원소보다 더 앞으로 옮겨주어야 할 것이다. 그런데 swap을 하지는 않고 해당 원소만 한칸 뒤로 밀어준다. now를 더 앞으로 보내야 할 수도 있기 때문이다. 앞의 모든 원소를 비교하고 난 뒤 now의 위치가 최종적으로 결정되었을 때 now를 넣는 것이 가장 효율적이다.

i 이전의 인덱스는 모두 정렬된 상태인데, i 인덱스 이전의 원소가 now보다 작다면 now는 지금의 인덱스 위치가 올바른 위치라는 것이다. 따라서 더 수행할 것 없이 break로 for문을 빠져나간다. 

 

📍 시간복잡도(time complexity)

삽입 정렬의 시간복잡도는 O(n^2)이다. 이중 for문을 통해 구현되어 있으며 index i를 이용한 바깥 for문에서는 1부터 n-1까지, index j를 이용한 안쪽 for문에서는 i-1부터 0까지 실행된다. 따라서 O(n^2)에 속한다.

📍 Stable / In-Place

삽입 정렬은 Stable한 정렬 알고리즘이다. 구현 코드 중 정렬의 핵심이 되는 부분은 now와 앞의 원소를 비교하는 부분이다. 이 부분에서 now<nums[j] 로 부등호가 "<"가 사용된다. 같은 값은 더 앞으로 넘기지 않기 때문에 이로 인해 정렬의 안정성이 유지된다. 

또한 삽입 정렬은 In-Place 알고리즘이다. In-Place 알고리즘이란 input 이외에 input 길이만큼의 메모리를 사용하지 않는 알고리즘을 의미한다. 삽입 정렬은 주어진 배열 안에서 원소를 옮겨가며 정렬을 진행하기 때문에 주어진 배열 이외에는 크게 메모리를 사용하는 부분이 없고 따라서 In-Place 알고리즘이라고 할 수 있다. 하지만 배열의 길이가 길면 시간이 매우 오래 걸린다는 단점이 있다.

 

---

 

음 간단한데 은근.. 어려운 삽입정렬. 뭔가 다른 정렬들은 딱 특징이 드러나는데 삽입정렬은 어떻게 하는거였지? 구현을 시작할 때 잘 생각이 안난다.