'binary search'에 해당되는 글 1건

  1. 2008.03.16 선택 정렬과 이진탐색, 순열

자료구조 1주차 시험이었다...

선택정렬 : 정렬되지 않은 정수들 중에서 가장 작은 값을 찾아서 정렬된 리스트 다음 자리에 놓는다.
이진탐색 : 이미 정렬되어있는 리스트를 가정한다. 찾는 숫자와 중간값을 비교하여 범위를 줄여나간다.
               recursion 으로 구현한 소스 코드도 있다.
순열 : 순열은 재귀적으로 구현되었는데 사실 이해를 잘 못하였다;


/************************************************************************/
/* 작성일 : 2008. 03. 11.            */
/* 작성자 : 박상현                                                      */
/* 내 용 : 1장 연습              */
/************************************************************************/

#include "stdio.h"

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

void selectionSort(int [], int);
int compare(int, int);
int binSearch(int [], int, int, int);
int binSearchRec(int [], int, int, int);
void perm(char*, int, int);

void main()
{
 int i;
 int list[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
 char clist[10] = { 'a', 'b', 'c', 'd' };

 selectionSort(list, 10);
 for(i = 0 ; i < 10 ; i++)
 {
  printf("%d\n", list[i]);
 }
 printf("%d\n", list[binSearch(list, 5, 0, 9)]);   // 5 를 이진 탐색
 printf("%d\n", list[binSearchRec(list, 5, 0, 9)]);  // 5 를 재귀적으로 이진 탐색
 
 perm(clist, 0, 3);

}

/************************************************************************/
/* 함수명 : selectionSort                                               */
/* 내 용 : 숫자로 된 n 크기의 a[] 배열을 선택정렬한다.     */
/************************************************************************/
void selectionSort(int a[], int n)
{
 int i, j, min, minIndex, tmp;

 for(i = 0 ; i < n - 1 ; i++)
 {
  minIndex = i;
  min = a[i];
  for(j = i + 1 ; j < n ; j++)
  {
   if(min > a[j])
   {
    min = a[j];
    minIndex = j;
    SWAP(a[minIndex], a[i], tmp);
   }
  }
 }
}

/************************************************************************/
/* 함수명 : compare                                                     */
/* 내 용 : 두 가지 수의 대소를 비교한다.        */
/*     C 언어의 라이브러리 함수가 취하고 있는 방법을 따른다.  */
/*         첫 번째 값이 작은 경우 -1 리턴,        */
/*         두 값이 같은 경우 0  리턴,         */
/*         두 번째 값이 작은 경우 1 리턴.        */
/************************************************************************/
int compare(int x, int y)
{
 if(x < y) return -1;
 else if(x == y) return 0;
 else return 1;
}

/************************************************************************/
/* 함수명 : binSearch                                                   */
/* 내 용 : 이미 정렬되어 있는 배열 리스트에서 값을 탐색한다.   */
/************************************************************************/
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;
}

/************************************************************************/
/* 함수명 : binSearchRec                                                */
/* 내 용 : recursive 방식의 이진탐색         */
/************************************************************************/
int binSearchRec(int list[], int searchNum, int left, int right)
{
 int middle;
 if(left <= right)
 {
  middle = (left + right) / 2;
  switch(compare(list[middle], searchNum))
  {
  case -1 : return binSearchRec(list, searchNum, middle + 1, right); // 오른쪽이 더 클 경우
  case 0 : return middle;            // ==
  case 1: return binSearchRec(list, searchNum, left, middle - 1);  // 왼쪽이 더 클 경구
  }
 }
 return -1;

}

/************************************************************************/
/* 함수명 : perm                                                        */
/* 내 용 : list[i] 에서 list[n] 까지의 모든 순열을 생성     */
/************************************************************************/
void perm(char *list, int i, int n)
{
 int j, temp;
 if(i == n)
 {
  for(j = 0 ; j <=n ; j++)
  {
   printf("%c, ", list[j]);
   
  }
  printf(" ");
 }
 else
 {
  for(j = i ; j <= n ; j++)
  {
   SWAP(list[i], list[j], temp);
   perm(list, i + 1, n);
   SWAP(list[i], list[j], temp);
  }
 }
}

Posted by 행복한 프로그래머 궁금쟁이박

댓글을 달아 주세요