JUNGOL 실력키우기 1158 : 삽입정렬

삽입정렬(Insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 방법이다.

 

수열이 {5 4 3 7 6}이 있을 경우의 삽입정렬 과정은 다음과 같다.
처음상태에서 처음 값 5 앞에 아무것도 없으므로 5는 이미 정렬된 상태가 되므로, 이후 4부터 정렬과정을 살펴보자.

※ 3단계의 경우 7은 앞의 "3 4 5"보다 크므로 제자리에 삽입된다.

n개의 수열이 주어지면 위와 같은 방법으로 정렬하는 과정 각 단계를 출력하는 프로그램을 작성하시오.

 

첫줄에 수열의 길이 N(4≤N≤100)이 주어진다.
두 번째 줄에 N개의 0이상 100이하의 정수가 주어진다.

처음 상태를 제외하고 정렬과정의 각 단계별 결과를 "출력예"와 같이 출력한다.

5 5 4 3 7 6

4 5 3 7 6 3 4 5 7 6 3 4 5 7 6 3 4 5 6 7

---

지난번 정렬에서 알고리즘을 삽입 정렬로 바꿔주면 되는 문제입니다.

삽입 정렬은 정렬이 된 배열로 정렬되지 않은 원소를  하나씩 이동시켜 정렬을 완료하는 알고리즘으로 시간복잡도는 n(n-1)/4이며

선택 정렬과 버블 정렬에 비해 약 2배 정도 빠르다고 볼 수 있으나 빅O 표기법으로 볼 때는 O(n^2)로 동일한 시간 복잡도를 가지는 알고리즘 입니다.

#include <iostream>
 
using namespace std;
 
void printArr(int *arr, int n);
 
int main()
{
    int n;
 
    cin >> n;
 
    // 데이터를 저장할 행렬 생성
    int *arr = new int[n];
 
    // 데이터 저장
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    // 첫번째 인덱스의 값이 있는 부분을 정렬된 배열로 가정
    // 정렬된 배열로 새 데이터 위치를 지정해 삽입해 정렬한다.
    for (int i = 1; i < n; ++i)
    {
        int data{ arr[i] };
        int index{ i };
 
        // 비교할 값의 왼쪽 부터 검사해 자리를 찾는다.
        for (int j = i - 1; j >= 0; --j)
        {
            if (arr[j] < data) break;
            arr[index--] = arr[j];
        }
 
        // 자리 확정
        arr[index] = data;
 
        // 결과를 출력한다.
        printArr(arr, n);
    }
 
    delete[] arr;
}
 
void printArr(int *arr, int n)
{
    for (int i = 0; i < n; ++i)
    {
        cout << arr[i] << ' ';
    }
    cout << endl;
}

JUNGOL) 문제은행) 실력키우기) 삽입정렬