1-3강 - Algorithm specification (1) 선택 정렬, 이진 탐색

1. Algorithm

정확한 정의는 아직 없다. 하지만 우리가 서로 공통적으로 이해하고 있는 부분이 있다.

1) algorithm 정의

명령들의 유한 집합이며 이들을 따라가면 특정 업무를 수행할 수 있다.

2) algorithm 정의의 기준

1> input (없을 수도 있고 많을 수도 있다.)

2> output (적어도 하나의 결과)

3> Definiteness (각각의 명령은 명확하고 올바르게 정의되어야 한다.)

4> Finiteness

- 운영체제의 경우 무한히 수행되기도 한다.

- 어떤 학자들은 무한한 것을 algorithm이라 하지 않고 procedure이라고 하기도 함

5> Effectiveness

(물론 5가지 모든 조건을 만족하지 않을 수 있다.)

 

2. Selection Sort

1> 정렬 증명: loop invariant

 

1) 기본

1> 정의: 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

2> 제자리 정렬 (in-place sorting) -> 다른 추가 메모리를 요구하지 않음

2) 구체적인 과정

1> 1st task: 주어진 array 전체(0~MAX)에서 가장 작은 원소를 찾는다. 

2> 2nd task: '그 작은 원소'와 'array에서 0번째 원소'를 교체한다.

3> 1>~2>를 1번째 원소부터 마지막 원소까지의 범위에서 시행

4> 이를 하나의 원소만 남을 때까지 반복

 

3) 구현

0> pseudo code

for (int i = 0; i < n; i++)
{
	// 1) Examine list[i] to list[n-1] and suppose that the smallest one is at list[min]
	// 2) Interchange list[i] and list[min]
}

1> 기본 구현

#include <stdio.h>
#define MAX 100

int main()
{
	int N;
	scanf("%d", &N);
	int list[MAX];
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &list[i]);
	}

	int min, idx, temp;

	for (int i = 0; i < N; i++)
	{
		min = 9999; // 추후 들어올 수 있는 원소들보다 큰 값으로 min을 설정
		for (int j = i; j < N; j++)
		{
			if (min > list[j])
			{
				min = list[j];
				idx = j;
			}
		}
		temp = list[i];
		list[i] = list[idx];
		list[idx] = temp;
	}
	for (int i = 0; i < N; i++)
	{
		printf("%d\n", list[i]);
	}

}

2> swap function

oid swap(int *x, int *y)
{
	int temp = *x;
	*x = *y;
	*y = temp;
}

void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

3> macro version of swap

#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t))

4> macro를 이용한 selection sort

void sort(int list[], int n)
{
	int min, temp;
	for (int i = 0; i < n - 1; i++)
	{
		min = i; // 시작점 i를 최소로 먼저 초기화한다.
		for (int j = i + 1; j < n; j++)
		{
			if (list[j] < list[min])
			{
				min = j;
			}
			SWAP(list[i], list[min], temp);
		}
	}
}

결론은 함수나 매크로를 정의해두면 필요할 때마다 쓸 수 있어서 편하다.

 

3. Binary Search

1) 기본

1> 정의:

- 가정: 이미 n개의 숫자가 정렬되어 있을 때, 

- 찾는 숫자가 이 배열 안에 있는지 확인한다. 

- 있다면 그 위치의 배열의 index를 return하고, 없다면 -1을 return

 

2) 구체적인 과정

0> 초기 설정

- list: 정렬할 배열

- searchNum: 찾고자 하는 수

- left, right: 배열의 시작, 끝

(middle은 left와 right가 계산되고서 연산한다. -> 그래서 while문 내부에 넣는다.)

- middle = (left + right)/2: 우리가 찾고자하는 searchNum과 비교한다.

1> 1st task: searchNum이 있는지 확인한다.

(어떻게 확인할 것인가?)

(middle은 left와 right가 계산되고서 연산한다. -> 그래서 while문 내부에 넣는다.)

- middle = (left + right)/2: 우리가 찾고자하는 searchNum과 비교한다.

2> 2nd task: middle과 searchNum과 비교한다.

- searchNum = middle : searchNum을 찾았으니

=> middle을 return

- searchNum < middle : searchNum이 존재할 경우, list[left] ~ list[middle-1] 사이에 있으니

=> right에 middle-1을 대입

- searchNum > middle: searchNum이 존재할 경우, list[middle+1] ~ list[right] 사이에 있으니

=> left에 middle+1을 대입

 

cf> searchNum이 list 안에 있는지 확인하는 방법

binary search를 진행하는 동안에 searchNum이 없다면 left와 right가 교차하게 된다.

따라서 left와 right의 크기를 비교하는 task를 선행하고 middle과 searchNum을 비교한다.

 

3) 구현

0> pseudo code

int BinarySearch(int list[], int left, int right, int searchNum)
{
	// 0> 초깃값들은 paramter에서 제공받는다.
    while (left <= right) // 1st task-1: searchNum이 list 내부에 있는지
	{
		// 1st task-2: middle은 left와 right이 계산되고서 구할 수 있다.
        
		// 2nd task: searchNum과 middle과의 대소비교로 searchNum의 위치 찾기
        // 2-1, 2-2, 2-3 (searchNum과 middle이 같거나 더 크거나 작거나에 따라)
}

1> 기본 구현

int BinarySearch(int list[], int left, int right, int searchNum)
{
	while (left <= right)
	{
		int middle = (left + right) / 2;
		if (searchNum == middle)
		{
			return middle;
		}
		else if (searchNum < middle)
		{
			right = middle - 1;
		}
		else
		{
			left = middle + 1;
		}
	}
}

 2> compare function 

- 대소 관계에 따라 -1, 0, 1이 나오게 할 것이다. 

int compare(int x, int y)
{
	if (x < y) return - 1;
	else if (x == y) return 0;
	else return 1;
}

3> macro version of compare

#define COMPARE(x, y) (((x) < (y))? -1:((x)==(y))? 0: 1)

4> macro를 이용한 binary search

int binsearch (int list[], int searchnum, int left, int right)
{
	int middle;
	while (left <= right) {
		middle = (left + right) / 2;
		switch (COMPARE(list[middle],searchnum))
		{
			case -1: left = middle + 1;
			break;
			case 0: return middle;
			case 1: right = middle + 1;
		}
	}
	return -1;
}