Published 2021. 8. 28. 19:37
# 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를 반환한다.
[채점 결과]