실력키우기 삽입정렬(C++)

1158 : 삽입정렬

제한시간: 1ms    메모리제한: 32MB
해결횟수: 642회    시도횟수: 1068회   

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

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

 

 

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

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

 

첫줄에 수열의 길이 N(4≤N≤100)이 주어진다.

두 번째 줄에 N개의 0이상 100이하의 정수가 주어진다.

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

[Copy] 5 5 4 3 7 6

[Copy] 4 5 3 7 6 3 4 5 7 6 3 4 5 7 6 3 4 5 6 7

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

/**************************************************************     Problem: 1158     User: a132034     Language: C++     Result: Success     Time:3 ms     Memory:1740 kb ****************************************************************/     #include    <iostream> #include    <algorithm> using namespace std;   int main() {     int n;     int * arr;     cin >> n;     arr = new int[n];     for (int i = 0; i < n; ++i)         cin >> arr[i];       for (int i = 1; i < n; ++i)     {         for (int j = 0; j <= i - 1; ++j)         {             if (arr[i] < arr[j])             {                 int tmp = arr[i];                 for (int a = i-1; a >= j; --a)                 {                     arr[a + 1] = arr[a];                 }                 arr[j] = tmp;                                   break;             }         }           for (int k = 0; k < n; ++k)         {             cout << arr[k] << " ";         }         cout << endl;     }     return 0; }

이 문제의 핵심은 앞의 배열은 정렬이 되어 있다는 것! 

때문에 앞의 배열과 비교한 후 값을 교환해줄 때, 해당 값만 교환해줘서는 안된다. 

입력 예에서는 

2 단계에서 

4 5 3 7 6 -> 4 5 까지는 정렬이 되어있을 때 3을 비교한 결과 4보다도 작기 때문에 3을 4의 자리로 옮겨주면서 

4 5는 변경없이 그대로 밀려야 한다. 

그 것이 for loop 중 a를 index로 사용한 가장 안쪽의 for loop이다. 

이것만 조심하여 푼다면 어려울 것은 없는 문제다.