'Algorithm&DataStructures'에 해당되는 글 38건

이진검색 - 루프사용(Binary Searching using loop)

- 가운데 요소들을 기준으로 양쪽으로 나누어 검색한다

- 찾는 요소와 가운데 요소의 크고 작음에 따라 방향이 결정된다

- 분할과 정복 기술 사용

- 빠르면 O(1) 최악이면 O(logn)의 성능을 갖는다

- 그러나 기존에 배열을 정렬 시킨 후 사용해야 한다

1. 구현

public class BinaryUsingLoop { public int binary(int arry[], int key){ int start = 0; int end = arry.length - 1; int mid; while(end >= start){ mid = (start + end)/2; if(arry[mid] == key){ return mid; } if(arry[mid] < key){ start = mid+1; }else{ end = mid-1; } } return -1; } public static void main(String[]args){ BinaryUsingLoop search = new BinaryUsingLoop(); int arry[] = {1,2,3,4,5,6,7,8,9}; System.out.println(search.binary(arry, 9)); } } <textarea> <br /></span></b></p>

- 중요한 점은 start와 end 부분을 설정 할때 +1, -1 을 함으로써 배열의 크기와 상관없이 검색 할 수 있도록 설정

단순 연속 검색 혹은 일직선 검색(Linear Searching, Sequential Searching)

- 배열안의 요소를 찾기위해 처음부터 하나씩 체크 한다

- 만약 요소가 없는 경우 최악의 성능을 제공한다. (배열을 처음부터 다 돌아야함)

1. 구현

public class LinearSearching { public int Linear(int a[], int key){ int size = a.length; for(int i = 0; i<size; i++){ if(a[i] == key){ return i; } } return -1; } public static void main(String[]args){ LinearSearching search = new LinearSearching(); int arry[] = {10,98,1,2}; System.out.println(search.Linear(arry, 2)); } }

- 실행 결과로 key에 해당하는 index 값을 반환한다

2. 결론

- 권장하지 않는다

퀵 정렬  - Quick Sorting

- 다른 정렬 알고리즘에 비해 빠르다

- 분할, 정렬 알고리즘 사용(divide and conquer)

- pivot 이라는 요소를 지정하고 나누어 각각 리스트를 비교한 후 합친다

- 재귀함수 호출 사용

- 다른 알고리즘에 비해 복잡하게 느껴진다(me too...)

1. QuickSorting.class

1) 초기화

private int[] arry; private int length;

- 배열, 배열 크기를 정의

2) sort()

public void sort(int[] arry){ this.arry = arry; this.length = arry.length; quickSort(0, length-1); }  

- 생성자 함수와 같이 값을 초기화 한다

- 퀵 정렬 호출

3) quickSort()

private void quickSort(int lowIndex, int highIndex){ int pivot = arry[(lowIndex+(highIndex - lowIndex)/2)]; int low = lowIndex; int high = highIndex; //pivot을 기준으로 리스트를 분할 한다 while(low <= high){ //pivot 보다 작은 값이라면 계속진행, 크다면 멈추고 low에 값이 저장된다 while(pivot > arry[low]){ low++; } //pivot 보다 큰 값 while(pivot < arry[high]){ high--; } //만약 low가 high 보다 크다면, 그것은 pivot을 기준으로 양쪽 값이 잘 정렬됬다는 것을 뜻 한다, 위치 바꿀 필요없음 if(low <= high){ //위에서 멈춘 위치의 값들을 서로 교환한다 exchange(low,high); //교환했다면 다시 진행을 위해 증가/감소 한다 low++; high--; } } print(); if(lowIndex < high){ quickSort(lowIndex, high); } if(low < highIndex){ quickSort(low, highIndex); } }  

4) exchange(), print()

public void exchange(int low, int high){ int temp = arry[low]; arry[low] = arry[high]; arry[high] = temp; } public void print(){ for(int i = 0; i< length; i++){ System.out.print(arry[i]+" "); } System.out.println(); }  

- 값 교환하는 부분과 상태를 표시

5) main()

public static void main(String[]args){ QuickSorting aa = new QuickSorting(); int bb[] = {10,2,3,99,1,7,-1,100}; for(int a: bb){ System.out.print(a+" "); } System.out.println(); aa.sort(bb); }  

인서트정렬 - Insertion sorting

- 작은 양에 데이터를 비교할 때 적합하다

- 간결하고 효율적이다

1. InsertionSorting.class

1) insert(int[] arry)

public void insert(int[] arry){ print(arry); //배열의 크기의 -1 만큼 회전 for(int i = 1; i<arry.length; i++){ //i의 값에 따라 값 비교를 시작 하기 때문에 --로 진행 for(int j = i; j>0; j--){ if(arry[j] < arry[j-1]){ swap(arry,j); } } System.out.print("-"+i+" "); print(arry); } }

- 배열의 크기 -1만큼 회전한다

- 한번 회전 할때 마다 처음 회전 횟수를 기준으로 비교

(i = 1 이면 한번 비교, i = 2 요소 값 3개 두번 비교 i =3 이면 요소값 네개 세번 비교....)

- 버블 정렬과 비슷해보이지만 버블 정렬은 1회전에 모든 값을 돌면서 비교 하지만 인서트는 회전 할 때마다 비교값이 제한 되어있다

2) swap(int[] arry,  int j), print(int[] arry)

public void swap(int[] arry, int j){ int temp = 0; temp = arry[j]; arry[j] = arry[j-1]; arry[j-1] = temp; } public void print(int[] arry){ for(int b : arry){ System.out.print(b+" "); } System.out.println(); }  

- 값의 위치를 변경 해주는 함수와 상태 값 출력

3) main()    

public static void main(String[] args){ InsertionSorting aa = new InsertionSorting(); int[] bb= {1,10,5,2,30,0,-5}; aa.insert(bb); }