# Correctness and the Loop Invariant (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(" ");
    }
}

 

- 수정 코드

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

 

[코드설명]

루프불변자에 대한 이해를 요구하는 문제였다.

이번 문제에서는 코드가 이미 주어져있었다.

다만 루프불변자에서 잘못된 점을 찾아 수정해야 했다.

 

기존 코드에서는 while loop에서 j > 0이라고 되어있다.

삽입정렬을 할 때 실제로는 비교 원소 앞에서부터 인덱스 0까지 비교를 해야하기 때문에 j >= 0으로 고쳐줬다.

 

[채점 결과]

 

 

 

 

 

# Running Time of Algorithms (Sorting)

[문제]

 

[코드]

int runningTime(vector<int> arr) {
    int temp, i, j;
    int shift = 0;
    
    for(i = 1; i < arr.size(); i++) {
        temp = arr[i];
        j = i-1;
        while(j >= 0 && temp < arr[j]) {
            arr[j+1] = arr[j];
            j = j-1;
            shift++;
        }
        arr[j+1] = temp;
    }
    return shift;
}

 

[코드설명]

삽입정렬이 실행될 때 요소가 swap되는 횟수를 구하는 문제다.

이전 코드에서 shift라는 변수를 추가해서 요소가 swap될 때마다 shift를 1씩 증가시켰다.

삽입정렬이 완료된 후에는 shift를 반환한다. 

 

[채점 결과]

 

 

 

 

 

# Counting Sort 1 (Sorting)

[문제]

 

[코드]

vector<int> countingSort(vector<int> arr) {
    vector<int>result(100);
    
    for(int i = 0; i < arr.size(); i++)
        result[arr[i]]++;
        
    return result;
}

 

[코드설명]

주어진 정수 리스트에서 각각의 정수들이 나타난 횟수를 카운팅하는 문제다.

주어진 정수 리스트 arr의 크기만큼 반복문을 실행해서 인덱스 0부터 마지막 인덱스까지 순회했다.

이때 arr[i]의 값을 result의 인덱스로 활용해서 정수의 출현 횟수를 카운팅했다.

마지막엔 카운팅 정보를 담은 result를 반환한다.

 

[채점 결과]

복사했습니다!