[HackerRank] Insertion Sort-Part2

<sorting 문제>

https://www.hackerrank.com/challenges/insertionsort2/problem

Insertion Sort - Part 2 | HackerRank

 

<문제>

배열의 크기를 입력받고, 배열을 입력받는다. 입력받은 배열을 왼쪽부터 오른쪽 순서대로 정렬한 결과를 출력하고, 마지막으로 정렬완료한 배열을 출력한다.

 

<코드>

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

void insertionSort(int *A, int n)
{
    for (int i = 1; i <= n - 1; i++)
    {
        int key, j;
        key = A[i];
        j = i - 1;
        while (j >= 0 && A[j] > key)
        {
            A[j + 1] = A[j];
            j--;
        
        }
        A[j + 1] = key;
         for(int k=0;k<n;k++){
                  printf("%d ",A[k]);
            }
            printf("\n");
            
    }
    
}
int main()
{
    int size;
    int arr[10000];
    scanf("%d",&size);
    for (int i=0; i<size; i++) {
        scanf("%d",&arr[i]);
    }
    insertionSort(arr, size);

    return 0;
}

 

<풀이>

1. arr으로 배열을 선언했다.

2. 배열의 크기인 size를 입력받는다.

3. for문을 통해 배열의 크기만큼 배열을 입력받는다.

4. insertion sorting을 함수로 정의하여 진행했다. 먼저 i번째 배열 값을 key에 저장하였다.

arr[j] 값이 arr[i], 즉 key보다 작을 때까지 arr[j+1]=arr[j]를 통해 뒤로 한 칸씩 민다.

arr[j]<key이면 while문을 빠져나와서 배열의 다음 값인 arr[j+1]에 n값을 저장하고 배열을 출력한다.

 

<제출결과>