[HackerRank] Correctness and the Loop Invariant

5주차 자유 문제
Prepare > Algorithms > Sorting

 

풀이

삽입 정렬 코드를 완성하는 문제이다. 삽입 정렬의 기본 알고리즘은 다음과 같다.

1. 리스트의 인덱스 0번 위치의 항목 한 개는 이미 정렬이 완료된 리스트로 취급한다.
2. 정렬 리스트의 오른쪽에 있는 정렬되지 않은 원소(1번 위치의 원소)는 자신의 앞에 있는 원소와 크기를 비교하여 앞쪽 원소가 더 크면 자리를 바꾼다.
3. 동일하게 2번 위치에 있는 원소도 왼쪽으로 전진하면서 자기 자리를 찾을 때까지 왼쪽으로 전진한다.
4. 이 과정을 더 이상 비교 대상 원소가 없을 때까지 반복한다.

위 알고리즘을 바탕으로 코드를 작성해 보았다.

int main() {
    int n, temp, i, j; 
    vector<int> arr;
    
    cin >> n;
    for(i=0; i<n; i++){
        cin >> temp;
        arr.push_back(temp);
    }
    
    //insertion sort
    for(i=1; i<arr.size(); i++){
        temp = arr[i];
        for(j=i-1; j>=0 && temp < arr[j]; j--)
            arr[j+1] = arr[j];
        arr[j+1] = temp;
    }
    
    for(i=0; i<arr.size(); i++){
        cout << arr[i] << " ";
    }
     
    return 0;
}

실행 결과는 다음과 같다.