<선택 정렬 및 이진 탐색 알고리즘> #Selection sort #Binary search

# 선택 정렬 [Selection sort] // 소스코드는 최하단에 첨부되어 있습니다. (게시글 복붙, 드래그 불가)

---

 만약 우리가 1보다 크거나 같은 모든 정수에 대하여 크기 순으로 정렬하는 프로그램을 작성한다고 가정해보자. 그 때 생각할 수 있는 기본 아이디어는 배열을 사용하는 것이고, 둘째로 가장 작은 수를 찾아 배열의 가장 왼쪽 (index 0)으로 이동시키는 작업이다. 

/*************************************************
 ** Selection sort program example
*************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// 배열의 최대크기 제한
#define MAX_SIZE 101

// 항상 매크로를 사용할 때는 오류발생가능성을 최소화 하기 위해 괄호를 사용
// 매크로의 장점은 자료형에 국한되지 않고 사용할 수 있다는 것
#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t))

void sort(int[], int);

void main(void)
{
	int i, n;
	int arr[MAX_SIZE];
	printf("Enter the number of numbers to generate: ");
	scanf("%d", &n);

	if (n < 1 || n > MAX_SIZE) { // 배열의 크기는 최소 1이상 되어야 한다.
		fprintf(stderr, "Improper value of n\n");
		exit(EXIT_FAILURE); // defined in stdlib.h
	}

	for (i = 0; i < n; i++) { // randomly generate numbers 0~0x7fff (= 0~32767)
		arr[i] = rand() % 1000; // generate numbers between 0 and 999
		printf("%d ", arr[i]);
	}

	sort(arr, n);
	printf("\n Sorted array:\n ");

	for (i = 0; i < n; i++)
		printf("%d ", arr[i]);

	printf("\n");
}

void sort(int arr[], int n)
{
	int i, j, min, temp;

	for (i = 0; i < n - 1; i++) {
		min = i;
		for (j = i + 1; j < n; j++)
			if (arr[j] < arr[min])
				min = j;
		SWAP(arr[i], arr[min], temp);
	}
}

/*************************************************
 ** End Line
*************************************************/

 두 개의 for문을 사용하여 선택정렬을 시행했다. 바깥의 for문으로 기준점을 바꿔가며 각 기준점 + 1 index값부터 탐색을 시작한다. 결국 min은 갱신을 계속하여 최소값이 들어 있는 인덱스 값을 가진다. 따라서, 마지막에는 기준점 인덱스의 값과 찾아낸 인덱스(min) 값을 SWAP 매크로를 이용하여 바꿔주기만 하면 된다.

 SWAP은 별도의 함수 swap( )으로 제작할 수 있지만, 매크로를 쓴 이유는 자료형의 유연성을 보장하기 위해서다. C++과 같은 객체지향에서는 제네릭 프로그래밍이라는 개념과 template 등이 등장하지만, C에서는 아쉽게도 동일한 이름의 함수로 여러 자료형을 받고 처리하는 함수를 제작할 수 없다. 함수의 이름을 제각기 다르게 해서 모든 자료형을 받을 수 있게 하는 건 C에서 너무 번거로운 작업이기에 매크로를 사용한  것이다.

이진 탐색 [Binary search]

---

 이진 탐색은 탐색의 방법 중 하나다. 배열에서 원하는 수를 찾는 상황을 생각해보자.

 먼저 우리는 n개의 정수(integers)를 가지고 있는 배열 arr(배열의 이름)가 있다고 가정한다(n >= 1). 또한, 배열 arr는 이미 크기 순으로 정렬되어 있다고 가정한다. 만약 우리가 찾는 수가 있다면 해당 값이 들어 있는 배열의 인덱스(index)를 리턴하고, 탐색에 실패했다면 -1을 리턴한다고 해보자.

 이미 인덱스가 증가하는 방향에 따라 작은수부터 큰 수까지 정렬되어 있는 배열을 사용하기 때문에 아래와 같은 방법을 사용해보자. // 여기서부터 이진 탐색의 개념이 등장한다.

 변수 left 와 right 를 각각 배열의 끝으로 설정해둔다. 배열의 최소 인덱스는 0이고, 배열의 크기가 n일 때 최대 인덱스는 n-1이므로 left = 0, right = n-1로 각각 초기화 시킨다. 그리고 변수 middle을 하나 둔 후 배열 arr의 중앙인덱스를 그 값으로 준다. middle = (left + right) / 2로 초기화 시킨다. 

/* left + write의 값이 홀수라면 나눈 결과에 소숫점이 등장할텐데, 정수 자료형(integer)의 특성상 소숫점은 버려지게 된다. 가령, (3 + 4) / 2 = 3 이다. */ 

 그런 후에 우리가 찾는 수 searchNum과 배열의 중앙에 위치한 값 arr[middle] 값을 비교한다. 비교했을 때 나올 수 있는 상황은 3가지가 있다.

• searchNum < arr[middle]. 우리가 원하는 수를 찾지는 못했지만, 적어도 배열의 처음부터 중간부분 사이에 존재한다는 사실은 발견할 것이란 가정은 할 수 있다. 즉, 0부터 middle-1 사이에는 존재할 수 있다는 뜻이다. 따라서 여기서 원활한 탐색을 위해 배열의 최대인덱스를 의미했던 변수 right의 값을 middle - 1로 설정해준다.
  /* 수사망을 좁혀간다고 생각해보면 이해가 빠를 것이다. */
  
  
• searchNum = arr[middle]. 우리가 원하는 수가 배열의 middle 위치에 존재하는 것이 확인됐다. 인덱스 middle을 리턴해면 된다.
  
  
• searchNum > arr[middle]. 원하는 수를 발견하진 못했지만, 적어도 배열의 middle + 1부터 배열의 끝 (n - 1) 사이에는 존재할 수 있다고 가정할 수는 있다. 위와 동일한 원리로 변수 left의 값을 middle + 1로 설정해준다.

 원하는 수를 발견하면 다행이지만, 발견하지 못할 경우 어떤 일이 발생할까? 값을 찾지 못할 때마다 left 혹은 right의 값이 변동이된다. left의 경우는 계속해서 증가할 것이고, right의 경우는 계속해서 감소할 것이다. 한 쪽이 증가나 감소를 계속할 경우 결국 교차(cross) 상황이 발생한다. 분명 우리는 배열의 최소 인덱스(index)를 left로 설정했는데, left가 right를 추월할 수 있다는 뜻이다.

 위에서 정리한 내용들을 바탕으로 이진탐색 알고리즘이 아래 C언어로 작성되어 있다. 반복버전의 이진 탐색 알고리즘이다. 그 아래 단락에는 순환버전의 이진 탐색 알고리즘을 작성하고자 한다.

/*************************************************
 ** 이진 탐색 알고리즘 (binary search) 반복 버전
*************************************************/

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

int binarySearch(int arr[], int searchNum, int left, int right)
{
	int middle;
	while (left <= right) { // left > right 가 되는 순간 이진 탐색 종료
		middle = (left + right) / 2;

		switch (COMPARE(arr[middle], searchNum)) {
		// arr[middle]이 saerchNum 보다 작을 경우 -1, 같을 경우 0, 클 경우 1
		case -1: left = middle + 1;	break;
		case 0: return middle; // 원하는 수를 찾았을 경우 리턴한다.
		case 1: right = middle - 1;
		}
	}
	return -1; // 여기까지 왔다는 건, 탐색에 실패했다는 뜻이다.
}

/*************************************************
 ** End Line
*************************************************/

 매크로가 정의되어 있다. 삼항연산자를 2개나 써서 표현되어 있어 이해하는 데 어려움을 겪을 수 있다. 별도의 함수로 만들지 않은 것은 자료형에 국한되지 않는 제네릭 프로그래밍을 지향하기 때문이다.

 아래는 순환버전의 이진 탐색 알고리즘이다.

/*************************************************
 ** 이진 탐색 알고리즘 (binary search) 순환 버전
*************************************************/

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

int binarySearch(int arr[], int searchNum, int left, int right)
{
	int middle;
	if (left <= right) { // left > right 가 되는 순간 이진 탐색 종료
		middle = (left + right) / 2;

		switch (COMPARE(arr[middle], searchNum)) {
			// arr[middle]이 saerchNum 보다 작을 경우 -1, 같을 경우 0, 클 경우 1
		case -1: binarySearch(arr, searchNum, middle + 1, right); break;
		case 0: return middle; // 원하는 수를 찾았을 경우 리턴한다.
		case 1: binarySearch(arr, searchNum, left, middle - 1); break;
		}
	}
	return -1; // 여기까지 왔다는 건, 탐색에 실패했다는 뜻이다.
}

/*************************************************
 ** End Line
*************************************************/

Selection sort.c

binary search.c