[Algorithm/알고리즘] Exercise 1: Sorting(정렬)

Master in Data Science/Informatics 2 / / 2023. 3. 27. 01:30

Task 1.1

Consider the Hilbert curves of order 1, 2 and 3 in Figure 1. Assume the canvas that is used for drawing the Hilbert curve is a 5cm x 5cm square. What is the length of the Hilbert curve of order 15?

먼저 규칙을 찾아보자.

 

빨간색으로 표시한 부분처럼, 각 단계를 H(n)이라 한다면,

H(2)는 H(1)의 1/2 축소형이 4개가 반복되는데 3개의 링크가 있는 구조이고

H(3)는 H(2)의 1/2 축소형이 4개가 반복되는데 3개의 링크가 있는 구조이다.

 

그리고 링크는 1/2씩 줄어든다.

H(2)의 링크는 5/2^2이고, H(3)의 링크는 5/2^3이므로, H(n)의 링크는 5/2^n이다.

 

결국 H(n)의 길이는 H(n-1)*0.5*4 + 3*5/2^n = 2*H(n-1) + 15/2^n이다.

이제 이걸 C코드로 작성한다.

#include <stdio.h>
#include <math.h> // pow 사용을 위해 추가

int main() {
    double curve = 0;
    for (int i=1; i<=15; i++) {
        curve = 2*curve + 15/pow(2, i); // pow는 제곱
        printf("The curve of the order %d is %fcm.\n", i, curve);
    }
}

 

그러면 다음과 같은 결과가 나온다.

The curve of the order 1 is 7.500000cm.
The curve of the order 2 is 18.750000cm.
The curve of the order 3 is 39.375000cm.
The curve of the order 4 is 79.687500cm.
The curve of the order 5 is 159.843750cm.
The curve of the order 6 is 319.921875cm.
The curve of the order 7 is 639.960938cm.
The curve of the order 8 is 1279.980469cm.
The curve of the order 9 is 2559.990234cm.
The curve of the order 10 is 5119.995117cm.
The curve of the order 11 is 10239.997559cm.
The curve of the order 12 is 20479.998779cm.
The curve of the order 13 is 40959.999390cm.
The curve of the order 14 is 81919.999695cm.
The curve of the order 15 is 163839.999847cm.

 

 

Task 1.2

Consider the following sorting algorithms for answering the questions below. Assume the algorithms are used to sort an array A with n elements. For the analysis we only consider operations that compare array elements and operations that move array elements.

일단 문제를 풀기에 앞서 세 정렬의 런타임을 정리해보자.

  Best Case Average Case Worst Case
Bubble Sort O(n^2) O(n^2) O(n^2)
Selection Sort O(n^2) O(n^2) O(n^2)
Insertion Sort O(n) O(n^2) O(n^2)

 

(1) The best case runtime of BubbleSort is linear to n: FALSE

비교횟수를 살펴보자.

A[j] < A[j-1]이 비교하는 부분에 해당한다. 여기는 j=2부터 i까지 실행되고, i는 n부터 2까지 실행된다.

따라서 i가 n일 때는 2부터 n까지 n-1회,

i = n-1일 때는 2부터 n-1까지 n-2회,

i = 2일 때는 2부터 2까지 1회 실행되므로 총 비교횟수는 (n-1)+(n-2)+ ... +1 = n(n-1)/2이다.

따라서 런타임은 n이 아닌 n^2에 비례한다.

 

(2) Whether an array is sorted or not does not impact the runtime of SelectionSort. : TRUE

비교횟수를 살펴보자.

A[j] < A[j-1]이 비교하는 부분에 해당한다. 여기는 j=i+1부터 n까지 실행되고, i는 1부터 n-1까지 실행된다.

따라서 i가 1일 때는 2부터 n까지 n-1회,

i = 2일 때는 3부터 n까지 n-2회,

i = n일 때는 n부터 n까지 1회 실행되므로 총 비교횟수는 (n-1)+(n-2)+ ... +1 = n(n-1)/2이다.

 

이어서 교환횟수를 살펴보자.

exchange A[i] and A[k]가 교환하는 부분에 해당한다. 여기는 i가 1부터 n-1까지 실행된다.

따라서 정렬순서와 상관없이 n-1회이다.

 

(3) SelectionSort has the same best, average and worst case runtime.: TRUE

위에서 봤듯이 정렬여부와는 상관이 없다.

 

(4) InsertionSort achieves its best runtime if the input array is sorted in any order.: FALSE

비교횟수를 살펴보자.

먼저 오름차순 정렬되어 있는 경우, 1번씩만 비교하면 되므로 n-1번 비교한다.

반면 내림차순 정렬되어 있는 경우, i = 2일 때는 1번, i = 3일 때는 2번, ... i = n일 때 n-1번 비교하므로 n(n-1)/2번 비교한다.

 

 

Task 1.3

Consider the following sorting algorithm XSort:

Assume the array A = (4, 8, 8, 7, 7, 3, 5, 0, 5) is sorted with XSort. Which of the following arrays shows the state of array A after the second completion of the outermost loop?

 

1회 시뮬레이션을 돌려보자.

l = 1; r = 9;

j = 9일 때: A[9](=5) > A[8](=0)이므로 그대로 둔다. => 488773505

j = 8일 때: A[8](=0) < A[7](=5)이므로 둘을 바꾼다. 그리고 m = 8이 된다. => 488773055

j = 7일 때: A[7](=0) < A[6](=3)이므로 둘을 바꾼다. 그리고 m = 7이 된다. => 488770355

이렇게 j = 2까지 실행하면, m = 2가 되고 A = (0,4,8,8,7,7,3,5,5)가 된다.

 

루프를 나와서 l = 2가 된다.

j = 2일 때: A[2](=4) < A[3](=8)이므로 그대로 둔다. => 048877355

j = 3일 때: A[3](=8) = A[5)(=8)이므로 그대로 둔다. => 048877355

j = 4일 때: A[4](=8) > A[5](=7)이므로 둘을 바꾼다. 그리고 m = 4가 된다. => 048787355

이렇게 j = 8까지 실행하면, m = 8이 되고 A = (0,4,7,8,7,3,5,5,8)이 된다.

 

결국 이 알고리즘은 가장 작은 숫자 -> 가장 큰 숫자 -> 두 번째 작은 숫자 -> 두 번째 큰 숫자 ... 를 차례대로 정렬해나가는 것이다.

따라서 가장 외곽 루프를 1번 실행하면 A = (0,4,7,8,7,3,5,5,8)이고, 2번 실행하면 A = (0,3,4,7,7,5,5,8,8)이 된다.

 

이렇게 오래 걸렸는데 이제 겨우 Task 1 끝냈다...

 

 

Task 2

Write a C program that takes four integer numbers as input values on the command line. The four numbers are the values that shall be used to populate a 2 × 2 matrix. Compute the square of the matrix and print the original and the squared matrix side by side on the terminal.
The input handling is specific for exactly four values and does not have to be generalized. The matrix multiplication and the printing shall be general for n × n matrices.
Hint: Use sscanf to process command line arguments

 

*참고: sscanf(where the data comes from, in which forma the data is stored in the source, where the data should go to)이다.

 

matrix는 행렬이고, Compute the squre of the matrix는 행렬곱을 하라는 말이다. 라는 것을 몰라서 처음에는 문제를 이해하지 못했다...

그렇다면 행렬곱은 무엇인가.

 

출처:https://www.nagwa.com/en/explainers/432180315293/

 

그러므로 m[2][2]라는 행렬을 제곱한 o[2][2]는 아래와 같다.

o[0][0] = m[0][0] * m[0][0] + m[0][1] * m[1][0]

o[0][1] = m[0][0] * m[0][1] + m[0][1] * m[1][1]

o[1][0] = m[1][0] * m[0][0] + m[1][1] * m[1][0]

o[1][1] = m[1][0] * m[0][1] + m[1][1] * m[1][1]

 

색칠한 부분은 변하지 않는 부분이다. 그리고 색이 칠해지지 않은 곳은 기존 행렬에 근거한다. 

다시 말해 o[i][j] = m[i][0] * m[0][j] + m[i][1] * m[1][j] 이다.

그런데 여기서 하늘색 부분이 각각 0, 1이라는 것을 제외하면 밑줄 그은 두 부분은 반복되는 느낌이 있다.

즉, 저 0, 1을 k로 표시한다면 m[i][k] * m[k][j]로 표시할 수 있는 것이다.

 

그러면 이걸 코드로 적어보자.

#include <stdio.h>
#define N 2
/* Initialize matrices*/
int m[N][N];
int o[N][N];

/* Take input integers from terminal and save them in matrix */
int main(int argc, char **argv) {
  int i, j, k;

  sscanf(argv[1], "%d", &m[0][0]);
  sscanf(argv[2], "%d", &m[0][1]);
  sscanf(argv[3], "%d", &m[1][0]);
  sscanf(argv[4], "%d", &m[1][1]);

/* Compute square of matrix */
  for (i=0; i<N; i++) {
    for (j=0; j<N; j++) {
      o[i][j] = 0;
      for (k=0; k<N; k++) {
        o[i][j] = o[i][j]+m[i][k]*m[k][j];
      }
    }
  }

/* Print the output */
  printf(" input    output \n");
  for (i=0; i<N; i++) {
    for (j=0; j<N; j++) {
      printf("%3d",m[i][j]); // %3d는 자리수를 맞추기 위해 3자리의 정수로 출력하라는 것
    }
    printf("    ");
    for (j=0; j<N; j++) {
      printf("%3d",o[i][j]);
    }
    printf("\n");
  }
}

 

예를 들어 (2, 5, 3, 4)의 행렬을 입력하면 다음과 같은 결과가 나온다.

 input    output 
  2  5     19 30
  3  4     18 31

 

 

Task 3

Assume an array A with n integer elements and an integer c. The goal is to develop an algorithm that checks if there exists a pair of elements in A such that the sum of the two elements is equal to c.

 

3.1. Develop and implement an algorithm pairSum that solves the problem in C.

bool pairSum(int A[], int n, int c) {
  for (int i=0; i<n; i++) {
    for (int j=i+1; j<n; j++) {
      if (A[i] + A[j] == c) {
        return true;
      }
    }
  }
  return false;
}

 

3.2. Assume array A is sorted in non-decreasing order. Develop an algorithm pairSumSorted that exploits the sortedness and solves the problem faster than algorithm pairSum.

bool pairSumSorted(int A[], int n, int c) {
  int i=0;
  int j=n-1;
  while (i < j) {
    if (A[i] + A[j] == c) {
      return true;
    } else if (A[i] + A[j] < c) {
      i++;
    } else {
      j--;
    }
  }
  return false;
}

 

3.3. Measure and report the worst case runtime of algorithms pairSum and pairSumSorted for an array with half a million elements.

일단 pairSum의 시간복잡도는 O(n^2)이고 pairSumSorted의 시간복잡도는 O(n)이다.

실제 C를 돌려보면 약 10배 정도의 차이가 난다.

반응형

'Master in Data Science > Informatics 2' 카테고리의 다른 글

[Algorithm/알고리즘] Exercise 3: Algorithm Analysis(알고리즘 분석)  (0) 2023.04.01
[Algorithm/알고리즘] Algorithm Analysis(알고리즘 분석)  (0) 2023.03.28
[Algorithm/알고리즘] Exercise 2: Recursion(재귀)  (0) 2023.03.28
[Algorithm/알고리즘] 정렬(Sorting)과 재귀(Recursion)  (0) 2023.03.21
[Algorithms/알고리즘] 알고리즘이란?  (1) 2023.03.17
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기
Master in Data Science/Informatics 2 관련 글
글 더보기

티스토리툴바