버블,선형,삽입,2진탐색,최대값,c로알고리즘함수구현

소개글

버블,선형,삽입,2진탐색,최대값,c로알고리즘함수구현에 대한 보고서 자료입니다.

목차

1. 최대값을 찿는 알고리즘(maximum algorithm)

2. 선형 탐색 알고리즘(linear search algorithm)

3. 삽입정렬(insertion sorting algorithm)

4. 버블 정렬 알고리즘(bubble sorting algorithm)

5. 2진탐색 알고리즘(binary search algorithm)
(문제기술
분석
코딩
프로그램
결과
개선방향)
순으로 각 항목 기술..

본문내용

비교해서 어느 쪽에 존재하는가를 판정하는 식의 방법을 사용하는 것을 2진 탐색이라고 한다.
이 방법을 사용하면 자료의 개수가 많아짐에 따라서 순차탐색에 비해 사용되는 시간이 현저하게 절약된다.이 방법은 앞의 순차 탐색에 비해 다소 복잡해지는 면이 있으나, 그다지 어렵지는 않다. 구현 방법으로는 원하는 값이 존재할 것으로 보이는 영역의 왼쪽 위치와 오른쪽 위치를 중간값과 원하는 값의 비교결과에 따라 변화 시킴으로써 이루어진다.
이진 탐색(binary search)은 레코드의 키 값에 따라 정렬된 파일을 두 부분으로 나누어 검색하고자 하는 키가 어느 부분에 속하는가를 결정하여 해당 부분에 대하여 순환적으로 검색을 수행한다. 즉, 이진 검색은 레코드의 키 값에 다라 정렬된 파일의 중앙인 n/2번째 레코드의 키 값 Km과 탐색하기 위한 키 값 K를 비교하여, 세 가지 결과인 K = Km, K > Km, K < Km에 따라 해당 부분에 대해 순환적인 검색을 한다.
★코딩 방법★
1.현재 서브 트리의 루트와 키값을 비교한다.
2.루트의 키값과 검색 키가 같으면 동일 키를 가진 노드가 존재하는 것이므로 삽입이 불가능하다.
3.루트이 키보다 검색 키가 작으면 왼쪽 서브 트리를 검사한다.
4.루트의 키보다 검색 키가 크면 오른쪽 서브 트리르 검사한다.
5.더이상 검사할 노드가 없을 때, 즉 말단 노드에 도달한 경우 그 위치가 삽입할 위치이다.
현재 삽입위치에 있는 노드의 키값과 새로운 키를 비교한다.
삽입위치 노드의 키값이 새로운 키값보다 크면 새로운 노드는 left child가 된다.
삽입위치 노드의 키값이 새로운 키값보다 작으면 새로운 노드는 right child 가 된다.
<2진 탐색 알고리즘>
int binsearch(int data[], int n, int key)
{
int low, high;
int mid;
low=0;
high=n-1;
while(low <=high) {
mid=(low+high)/2;
if(key ==data[mid])
return mid;
if(key < data[mid])
high=mid-1;
else
low=mid+1;
}
return -1;
}
주어진 while 루핑을 빠져 나오는 경우는 left_item의 값이 right_item 값이나 mid_item의 값과 같아질 경우이다. 따라서, 그 아래에 나오는 if 문에서는 어느 값을
사용하여 비교하여도 상관없지만, mid_item 값을 사용하면 문제가 발생할 수 있다. 즉, last_item이 0이어서 루핑을 거치지 않는 경우에는 mid_item 값이 설정되어 있지 않으므로 주의해야 한다.
★프로그램 리스트★
#include < stdio.h >
#define MAX 40
unsigned long int next = 1;
/* rand: return pseudo-random integer on 0..1000 */
int rand(void)
{
next = next * 1103513245 + 12345;
return (unsigned int)(next/65536) % 1000;
}
/* srand: set seed for rand() */
void srand(unsigned int seed)
{
next = seed;
}
void bubble_sort(int [], int);
int binsearch(int [], int, int);
void main()
{
int i, temp, b;
int arr[MAX];
srand( 49 ); /* set a seed number */
printf("\n정렬 전 배열 : ");
for(i=0; i arr[i] = rand();
printf("%d ", arr[i]);
}
bubble_sort(arr, MAX);
printf("\n\n버블소트 후 배열 : ");
for(i=0; i printf("%d ", arr[i]);
printf("\n\n탐색할 숫자를 입력하세요 : ");
scanf("%d", &temp);
b = binsearch(arr, MAX, temp);
if(b == -1)
printf("\n%d가 배열안에 없습니다.\n", temp);
else
printf("\n%d는 배열 %d번째에 있습니다.\n", temp, b+1);
}
void bubble_sort(int data[], int n)
{
int i;
int j;
int temp;
for(i=n-1;i>=1;i--)
for(j=0;j if(data[j]>data[j+1]) {
temp=data[j];
data[j]=data[j+1];
data[j+1]=temp;
}
}
int binsearch(int data[], int n, int key)
{
int low, high;
int mid;
low=0;
high=n-1;
while(low <=high) {
mid=(low+high)/2;
if(key ==data[mid])
return mid;
if(key < data[mid])
high=mid-1;
else
low=mid+1;
}
return -1;
}
★결과★
<찾으려는값 x가 주어진 집합의 요소인경우>
(set 1)
(set 2)
(set 3)
(set 4)
(set 5)
<찾으려는값 x가 주어진 집합의 요소가 아닌경우>
(set 1)
(set 2)
(set 3)
(set 4)
(set 5)
★느낀점 및 개선방향★
이진 탐색 트리에는 새로운 노드들이 무작위로 삽입/삭제된다. 이진탐색에서의 문제점은 이때 다음 그림과 같이 탐색 트리가 한 방향으로 기울어질 수 있다는 것이다.
이진 탐색 트리가 한 방향으로 기울어지면 비교횟수가 평균 n/2회로 증가하여 선형 탐색을 하는 경우처럼 된다. 위의 그림을 살펴보면 91을 찾기 위해서는 3에서 14로, 다시 27로, 다시 91로 일일이 탐색해가야 하는데 마치 Linked List처럼 되어 버린 것을 알 수 있다. (혹은 Left, Right Skewed Tree) 이러한 문제를 해결하기 위해 균형 탐색 트리(balanced search tree)가 사용된다

키워드

알고리즘,   자료구조,   정렬,   최대값,   선형탐색,   버블,   2진탐색,   버블정렬