[자료구조] 1. Selection Sort, Binary Search

1. Selection Sort (선택 정렬)

 

선택 정렬(selection sort)은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다. (오름차순)

 

다음과 같이 배열이 있다고 하자

​

먼저 index 0을 기준으로 나머지 index에 저장되어 있는 값 중 가장 작은 값을 찾아서 index 0에 저장되어 있는 값과 바꾼다.

 

위의 배열의 경우 index 1에 저장된 값인 5가 가장 작은 값이기 때문에 둘을 바꾸어준다.

 

결과

마찬가지로 index 1에 저장된 값을 기준으로 나머지 index에 저장되어져 있는 값을 비교해서 제일 작은 값의 위치와 바꾸어 준다.

 

결과

이와 같은 방법을 반복하면

 

다음과 같이 오름차순 정렬이 완성된다.

​

​

소스 코드는 다음과 같다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void sort(int[], int);

int main(void)
{
	int list[10] = { 10,5,8,17,6,9,30,25,20,19 };

	printf("before sort: ");
	
	for (int i = 0; i < 10; i++) {
		printf("%d ", list[i]);
	}
	printf("\n");

	sort(list, 10);

	printf("after sort:  ");

	for (int i = 0; i < 10; i++) {
		printf("%d ", list[i]);
	}

	printf("\n");
}

void sort(int list[], int size)
{
	int i, j, index, temp;
	
	for (i = 0; i < size; i++) {
		index = i; //기준 index

		for (j = i; j < size; j++) {
			if (list[j] < list[index]) //기준 index에 저장된 값과 비교 index에 저장된 값을 비교
				index = j; // 작으면 'index'에 비교 index 저장

		}
		
        // 바꾸기
		temp = list[i];
		list[i] = list[index];
		list[index] = temp;
	}
}

 

 

 

 

2. Binary Search (이진 탐색)

 

이진 탐색(binary search)은 정렬된 데이터 집합을 이분화하면서 탐색하는 방법이다.

이 알고리즘은 정렬된 데이터가 아니면 적용이 불가능하다.

 

먼저 중간 index를 찾는다.

​

중간 index = (Left + Right) /2

​

위의 경우 index 값은 (0+9)/2 = 4가 된다.

​

중간 index에 저장되어 있는 값과 찾고자 하는 값을 비교해서 전자가 크면 뒷쪽을, 후자가 크면 앞쪽을 떨구어 낸다.

​

위의 경우 중간 index인 4에 저장되어 있는 값(10)이 찾고자 하는 값(20)보다 작기 때문에 앞쪽을 떨구어 낸다.

 

 

위와 같은 방법을 반복하면 찾고자 하는 값의 index를 찾아낼 수 있다.

​

​

이진탐색은 두 가지 방법으로 구현할 수 있다.

Iterative(반복)하게 구현하는 방법과 Recursive(재귀)하게 구현하는 방법이다.

​

​

​

아래 소스코드에는 두 가지 다 구현을 해보았다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int iterative_bin(int[], int, int, int);
int recursive_bin(int[], int, int, int);

int main(void)
{
	int list[10] = { 5,6,8,9,10,17,19,20,25,30 };
	
	int iterative_result = iterative_bin(list, 30, 0, 9);
	int recursive_result = recursive_bin(list, 30, 0, 9);

	if (iterative_result == -1)
		printf("do not exist");

	else
		printf("iterative: %d\n", list[iterative_result]);

	if (recursive_result == -1)
		printf("do not exist");

	
	printf("recursive: %d\n", list[recursive_result]);
}

int iterative_bin(int list[], int target, int left, int right)
{
	int mid;

	while (left <= right) {
		mid = (left + right) / 2;
		
		if (list[mid] < target)
		{
			left = mid + 1;
		}

		else if (list[mid] == target)
			return mid;

		else 
		{
			right = mid - 1;
		}
	}

	return -1;
	
}

int recursive_bin(int list[], int target, int left, int right)
{
	int mid;
	
	if (left > right)
		return -1;
	
	mid = (left + right) / 2;

	if (list[mid] == target)
		return mid;

	else if (list[mid] < target)
		recursive_bin(list, target, mid + 1, right);

	else if (list[mid] > target)
		recursive_bin(list, target, left, mid - 1);
}