삽입 정렬 (insertion sort)

삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여
자신의 위치를 찾아 삽입하는 알고리즘이다.

 

매번 비교할 때마다 앞 부분에 해당하는 범위 모두 타겟값과 비교하여 해당 원소를 삽입할 수 있는 위치를 찾아 배열 위치에 넣는다. 

 

특징

• 구현이 간단하다.
• 배열의 사이즈가 커질 수록 효율성이 떨어진다.
• 선택 정렬이나 버블 정렬과 같은 O(n^2) 알고리즘에 비해 빠르고 안정된 정렬이다.
• 추가적인 공간을 필요로 하지 않는다.
• 데이터를 서로 교환하기 때문에 임시 변수가 필요하다.

시간 복잡도

• best
  • 이동없이 한번씩만 비교할 경우
  • O(n)
• worst
  • 비교할때마다 i번씩 비교
  • O(n^2)

 

구현하기

void print(vector<int> v, string s);
void insertion_sort(vector<int> v);
void insertion_sort_reverse(vector<int> v);

int main() {
    vector<int> v = { 1, 7, 4, 3, 2, 9, 4 };
    insertion_sort(v);
    insertion_sort_reverse(v);

    return 0;
}


void print(vector<int> v, string s) {
    cout << s << " : ";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}

void insertion_sort(vector<int> v) {
    int size = v.size();
    for (int i = 1; i < size; i++) {
        int value = v[i];
        int pos = i - 1;

        while (pos >= 0) {
            if (v[pos] > value) {
                v[pos + 1] = v[pos];
                pos--;
            }
            else {
                break;
            }
        }
        v[pos + 1] = value;
    }
    print(v, "Insertion Sort");
}

void insertion_sort_reverse(vector<int> v) {
    int size = v.size();
    for (int i = 1; i < size; i++) {
        int value = v[i];
        int pos = i - 1;

        while (pos >= 0) {
            if (v[pos] < value) {
                v[pos + 1] = v[pos];
                pos--;
            }
            else {
                break;
            }
        }
        v[pos + 1] = value;
    }
    print(v, "Insertion Sort Reverse");
}

 

insertion_sort 함수

• index 1부터 반복이 시작되며 1에 위치한 값과 그 보다 왼쪽에 있는 원소들 간에 비교를 수행한다.
• 오름차순이기 때문에 작은 수일 수록 왼쪽에 위치해야한다. 인접한 왼쪽 값과 비교했을 때 왼쪽에 값이 클 경우 위치를 교환해준다.
• 반복해서 수행하다보면 정렬된 리스트를 얻을 수 있게 된다.

 

insertion_sort_reverse

• 내림차순 선택 정렬을 하는 함수이다.
• 인접한 왼쪽 값과 비교할 때 왼쪽 값이 더울 작을 경우 교환을 수행함으로 써 내림차순으로 정렬이 된다.