JArchive 프로그래밍 일기

전제: 배열의 데이터는 정렬된 상태이다.

<순서> 

1. 배열의 중앙(mid)에 찾는 값(target)이 저장되어 있는지 확인한다.

2. 대소 결과 탐색의 대상을 반으로 줄인다.

3. 1과 2를 반복한다.

#include <stdio.h>

int BSearch(int *arr, int len, int target)
{
	int first = 0;			//탐색 시작 인덱스
	int last = len - 1;		//탐색 마지막 인덱스 
	int mid;			

	while (first <= last)    
	{
		mid = (first + last) / 2;		//mid: 중앙인덱스 
		if (target == arr[mid])
		{
			return mid;		//찾은 경우 인덱스 mid를 리턴(탐색 완료)
		}
		else  //아니라면, 탐색 대상을 반으로 줄인다 
		{
			if (target > arr[mid])
			{
				first = mid + 1;	//타겟이 더 크면 first의 위치를 옮김
			}
			else
			{
				last = mid - 1;		//타겟이 더 작으면 last의 위치를 옮김
			}
		}
	}
	return -1;	//탐색 실패한 경우 
}

int main()
{
	int arr[] = { 1, 4, 5, 7, 9, 14 };		//정렬되어 있는 배열임을 전제.
	int len = sizeof(arr) / sizeof(int);
	int index;

	index = BSearch(arr, len, 9);	//'9'를 찾아본다 
	if (index == -1)
		printf("탐색실패!\n");
	else
		printf("target의 인덱스: %d\n", index);

	return 0;
}

순차 탐색 알고리즘은 배열에 순차적으로 접근해서 target값과 비교하여 탐색한다.

#include <stdio.h>
int LSearch(int arr[], int len, int target)
{
	int i;
	for (i = 0; i < len; i++)
	{
		if (target == arr[i])
			return i;	//찾은 경우 
	}
	return -1;	//찾지 못한 경우 
}

int main()
{
	int arr[] = { 3, 5, 2, 4, 9 };
	int index;

	index = LSearch(arr, sizeof(arr) / sizeof(int), 4);
	if (index == -1)
		printf("찾기 실패");
	else
		printf("%d \n", index);


	return 0;
}

버블정렬(Bubble Sort)은 인접한 숫자를 비교하여 자기보다 큰 수가 나오면 교환하는 정렬 알고리즘이다. 

시간복잡도는 O(n^2)로 상당히 느리지만 구현히 쉽고 안정적이다. 

메모리 사용 공간 : n개의 원소에 대하여 n개의 메모리를 사용한다. 

다음은 '오름차순'으로 정렬하는 코드다.

#include <stdio.h>
#include <stdlib.h>
#define SWAP(a,b) {int t=a; a=b; b=t; };

int BubbleSort(int *dataArray, int length)
{
	int i, j;
	for (i = 0; i < length - 1; i++)
	{
		for (j = 0; j < length - i -1; j++)
		{
			if (dataArray[j]>dataArray[j + 1])    //앞의 수가 더 클 경우 자리교환 ! 
			{
				SWAP(dataArray[j], dataArray[j + 1]);
			}
		}
	}
}

int main()
{
	int *dataArray;
	int length=0;
	int i = 0;

	printf("배열의 크기를 입력하세요:");
	scanf("%d", &length);
	dataArray = (int*)malloc(sizeof(int)*length);
	//입력 
	printf("크기 %d배열의 원소를 입력하세요: ", length);
	for (i = 0; i < length; i++)
	{
		scanf("%d", &dataArray[i]);
	}

	BubbleSort(dataArray, length);
	//출력
	for (i = 0; i < length; i++)
		printf("%d ", dataArray[i]);

	return 0;
}