[HackerRank] Sorting-Correctness and the Loop Invariant

https://www.hackerrank.com/challenges/correctness-invariant/problem

Correctness and the Loop Invariant | HackerRank

 

<문제>

 

배열의 크기를 입력받고, 배열의 원소들을 크기만큼 입력받아서 배열에 저장한다. 완성된 배열을 insertion sort를 통해 정렬하고 화면에 출력한다.

 

 

<코드>

 

#include <stdio.h>
#pragma warning(disable:4996)
#define n 10000

int main()
{
    int size, arr[n], i, temp, j;
    scanf("%d", &size); 

    for (i = 0; i < size; i++) 
    {
        scanf("%d", &arr[i]);
    }

    for (i = 1; i < size; i++)  //insertion sort code
    {
        temp = arr[i]; 
        j = i - 1;    
        while (j >= 0 && arr[j] > temp) 
        {
            arr[j + 1] = arr[j]; 
            j--;
        }
        arr[j + 1] = temp;  
    }

    for (i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
}

 

 

<풀이>

 

1. sanf("%d", &size); 로 배열의 크기를 입력받고 그 아래 for문을 통해 배열의 원소들을 모두 입력받는다.

2. for문을 통해 insertion sort를 하였다.

   - i번째 배열을 temp에 저장하고, j=i-1을 하여 arr[i-1]과 arr[i], 즉 temp와 비교한다.

   - arr[i-1]이 arr[i]보다 큰 동안 arr[i-1]의 값을 arr[i]에 대입한다.

   - arr[i-1]이 arr[i]보다 작으면 arr[i]에 temp값을 저장한다.

3. 정렬한 배열을 출력하였다.

 

 

<제출 결과>