[C++] HackerRank : Correctness and the Loop Invariant

[문제]

Correctness and the Loop Invariant | HackerRank

 

 

[문제 설명]

- 주어진 삽입 정렬 코드를 수정하여 프로그램을 완성

- 주어진 삽입 정렬 코드

void insertionSort(int N, int arr[]) {
    int i,j;
    int value;
    for(i=1;i<N;i++)
    {
        value=arr[i];
        j=i-1;
        while(j>0 && value<arr[j])
        {
            arr[j+1]=arr[j];
            j=j-1;
        }
        arr[j+1]=value;
    }
    for(j=0;j<N;j++)
    {
        printf("%d",arr[j]);
        printf(" ");
    }
}

- N: 배열의 크기

- arr: 입력 받은 수를 저장할 배열

 

 

[문제 풀이]

- main에서 입력받은 N으로 배열의 크기를 할당 받는 식이 잘못되었으므로 동적할당을 이용하여 메모리를 할당해줌

- i보다 하나 작은 j의 값이 그 뒤 값인 i보다 작을 때 while을 반복해야 함

  > j>0 인덱스에 대한 조건식 수정

 

 

[코드]

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

void insertionSort(int N, int *arr) {
    int i,j;
    int value;
    for(i=1;i<N;i++)
    {
        value=arr[i];
        j=i-1;
        while(j>=0 && value<arr[j])
        {
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=value;
    }
    
    for(j=0;j<N;j++)
    {
        printf("%d",arr[j]);
        printf(" ");
    }
}

int main(void) {

    int N,i;
    scanf("%d", &N);
    int* arr;
    arr = (int*)malloc(sizeof(int)*N);
    
    for(i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }

    insertionSort(N, arr);

    return 0;
}

 

 

[실행결과]