[HackerRank] Correctness and the Loop Invariant

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

Correctness and the Loop Invariant | HackerRank

Algorithms > Sorting

 

배열을 정렬하는 함수의 잘못된 코드가 주어지면 올바르게 동작하도록 수정한다.

 

 

코드

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(" ");
    }
}

 

설명

첫 번째 for문에서 배열을 정렬하고, 두 번째 for문에서 배열의 원소들을 출력한다.

먼저, 배열의 i번째 값을 기준으로 잡고 해당 인덱스 이전의 값들과 비교한다.

만약 기준이 되는 값이 그 앞에 위치한 값보다 작으면 앞에 위치한 값을 뒤로 이동시킨다.

이 과정을 반복하여 정렬이 완료되면 정렬된 배열의 원소들을 차례로 출력한다.