검색 알고리즘

package search [ 검색에 사용될 기본 페킷 ]

class _Set_Search [ 데이터를 산출하는 클래스 ] /*** * _Set_Search( int Data_su ) // 정수형의 크기만큼 배열을 생성한다. * _Data_Init() // 배열에 랜덤값을 넣는다. * _Data_Sort() // 퀵정렬을 이용 데이터를 정렬한다. * _Set_Key() // 검색할 값을 입력받는다. *_Show_Data() // 배열의 값을 화면에 보여 준다. ***/ import java.util.Scanner; public class _Set_Search extends java.util.Random { public int Data_len ; public int[] nDate ; public int Height ; public int nKey ; public _Set_Search( int Data_su ){ Data_len = Data_su ; nDate = new int[ Data_su+1 ]; // 동적 배열 Height = Data_su ; } // 중복없이 데이터를 입력한다. public void _Data_Init(){ int temp=0 ; for( int i =1 ; i<=Data_len ; ){ temp = nextInt(100)+1 ; for( int j = 1 ; j <= i ; j++ ){ if( temp == nDate[j] ){ temp = 0 ; //데이터가 중복일경우 0을 데입 } } if( temp != 0 ){ nDate[i] =temp ; temp = 0 ; i++; } } } //데이터를 정렬한다. public void _Data_Sort(){ _Quic_Sort2 opQsort = new _Quic_Sort2(); opQsort.quick_sort( nDate ,1 , Data_len ); } // 배열의 데이터를 출력한다. public void _Show_Data() { for( int i=1 ; i<=Data_len ; i++ ){ System.out.print(" " + nDate[i]); if( i % 10 == 0 ){ System.out.println(" "); } } System.out.println(" " ); } //찾을 값을 입력 받는다. public void _Set_Key(){ Scanner sIput = new Scanner(System.in); System.out.print(" 찾을 key 값을 입력하시오: "); nKey = sIput.nextInt(); //정수를 입력받은 } } class _Quic_Sort2 [ 퀵 알고리즘 ] /*** * partition(int date[], int left, int right) * quick_sort(int date[], int left, int right) ***/ class _Quic_Sort2 { _Swap opSwap = new _Swap(); public int partition(int date[], int left, int right) { int pivot, temp; int low,high; low = left; high = right+1; pivot = date[left]; /* 피벗 설정 */ do { do{ low++; /* 왼쪽 리스트에서 피벗보다 큰 레코드 선택 */ }while(low<=right &&date[low]<pivot); do{ high--; /* 오른쪽 리스트에서 피벗보다 작은 레코드 선택 */ }while( high>=left && date[high]> pivot); if(low<high){ opSwap._swap(date, date, low, high ) ; } } while(low<high); /* 인덱스 i,j가 엇갈리지 않는 한 반복 */ opSwap._swap(date , date , left ,high ); /* 인텍스 j가 가리키는 레코드와 피벗 교환 */ return high; } void quick_sort(int date[], int left, int right) { if(left<right){ /* 리스트에 2개 이상의 레코드가 있을 경우 */ int q=partition(date, left, right); quick_sort(date, left, q-1); /* 왼쪽 부분리스트를 퀵정렬 */ quick_sort(date, q+1, right); /* 오른쪽 부분리스트를 퀵정렬 */ } } } class _swap[ 값을 교환한다. ] /*** * _swap(int[] a , int [] b , int x , int y ) * // 데이터를 교환할 배열을 각각 받고 교환될 위치 정보를 받아 데이터를 교환 ***/ public void _swap(int[] a , int [] b , int x , int y ){ //두 수의 위치 변경 int temp; temp = a[ x ] ; a[ x ] = b[ y ] ; b[ y ] = temp ; } } class _Linear_Search [ 이분 검색 ] /*** * void _Search( int[] nDate , int Height , int nKey) ***/ public class _Linear_Search {s int Little = 1 ; int Middle ; // 검색 public void _Search( int[] nDate , int Height , int nKey){ while(true){ if( Little > Height ){ System.out.println(" 데이터가 존제하지 않음 "); break; }else{ Middle = (int)( ( Little + Height ) / 2 ) ; //가운데 값을 찾는다 . if( nKey == nDate[Middle] ){ System.out.println(" 데이터가 존제 합니다. "); System.out.println("데이터 위치는 nDate 배열에 " + Middle +"번째 입니다 "); break; } else{ if( nKey < nDate[Middle] ){ Height = Middle - 1 ; }else{ Little = Middle + 1 ; } } } }//while } } class _Fibonacci_search [ 피보나치 검색 ] /*** * _Set_Min( int max ) * _Search( int[ ] nDate , int key ) ***/ package search; public class _Fibonacci_search { int nMin = 1 ; int nKey ; int f1 =1 , f2=1 ; int nTemp = 1 ; // key 값에서 가장 가까운 피보나치 수열의 값을 nMin 값으로 지정 public void _Set_Min( int max ){ while( max > nTemp ){ // 키 값보다 작을때 까지 피보나치 수열을 구함 nTemp = f1 + f2 ; if( max > nTemp ){ // 키 값보다 작은 피보나치 수을 구한다. nMin = nTemp; f1 = f2 ; f2 = nMin ; } } f2 = nMin - f1 ; // f2의 값을 설정한다. /* * 1 1 2 3 5 8 * f2 f1 nMin */ } // 피보나치 수열 public void _Search( int[ ] nDate , int key ){ nKey = key ; while( true ){ if( nDate[nMin] == nKey ){ System.out.println("데이터 찾음 "); System.out.println("데이터가 저장된 위치는 nDate 배열에 "+ nMin +"번째 입니다. "); break; } else if( nDate[nMin] > nKey ){ //피보나치 값보다 작을 경우 nMin -= f2 ; nTemp = f1 - f2 ; f1 = f2 ; f2 = nTemp ; }else{//피보나치 값보다 클경우 경우 nMin += f2 ; f1 -= f2 ; f2 -= f1; }//else // f1의 값이 0 일때 데이터가 존재 하지 않음 if( f1 == 0 ){ System.out.println("데이터 존재 하지 않음 "); break; } }//while } }

class Linear_Search [ 이분 검색 ]

import search._Linear_Search; // 이분검색 알고리즘 import search._Set_Search; // 소트를 위한 기본 페킷정보 class Linear_Search [ 이분검색 main ] /*** * 각각의 오브젝트를 호출 데이터를 정렬한다. ***/ public class Linear_Search { public static void main(String[] args) { System.out.println(" 이분 검색 "); int Mex = 20 ; //데이터의 크기 _Set_Search op_Date = new _Set_Search( Mex ); // 객체를 생성한다. _Linear_Search op_Select = new _Linear_Search(); // 객체를 생성한다. op_Date._Data_Init(); //데이터를 생성한다. op_Date._Data_Sort(); // 데이터를 정렬한다. op_Date._Show_Data(); // 데이터를 출력 한다. op_Date._Set_Key() ; // 검색할 키를 입력받는다. op_Select._Search(op_Date.nDate , op_Date.Data_len ,op_Date.nKey ); // 이분검색을 실행한다. } }

class Fibonacci_Search [ 피보나치 검색 ]

import search._Linear_Search; // 이분검색 알고리즘 import search._Set_Search; // 소트를 위한 기본 페킷정보 class Fibonacci_Search [ 피보나치 검색 main ] /*** * 각각의 오브젝트를 호출 데이터를 정렬한다. ***/ public class Fibonacci_Search { public static void main(String[] args) { System.out.println(" 피보나치 검색 "); int Mex = 20 ; _Fibonacci_search op_select = new _Fibonacci_search(); _Set_Search op_date = new _Set_Search(Mex); op_date._Data_Init(); // 임이의 데이터를 입력받음 op_date._Data_Sort(); // 데이터 정렬 op_date._Show_Data(); // 데이터를 화면에 보여줌 op_date._Set_Key(); // 찾고하 하는 값을 입력받음 op_select._Set_Min( Mex ); // 피보나치 수열을 구한다. op_select._Search( op_date.nDate , op_date.nKey ); // 데이터를 찾는다. [출처] 검색( 이분검색 , 피보나치 ) (프로그램을 놀아가며) |작성자 odotolio