이진검색 & 정렬 정리

 

---

1. 이진검색 for

---

 

package test;

import java.util.Arrays;

public class 이진검색 {
	static int[] arr;
	public static void main(String[] args) {
		
		arr = new int[] {5,3,1,2,4};
		
		//이진검색은 반드시 정렬된 상태여야 한다.
		Arrays.sort(arr); //1 2 3 4 5
		
		System.out.println(binarySearch(3));
	}
	
	public static int binarySearch(int key) {
		int start = 0;
		int end = arr.length-1;
		System.out.println(Arrays.toString(arr));
		while(start <= end) {
			int mid = (start+end)/2;
			
			if(arr[mid]==key) return mid;
			//키값보다 arr[mid]값이 크다면, 탐색을 왼쪽 부분을 해준다.
			else if(arr[mid]>key) end=mid-1;
			
			//키값보다 arr[mid]값이 작다면, 탐색을 오른쪽 부분을 해준다.
			else if(arr[mid]<key) start=mid+1;
		}
		return -1;
	}

}

 

---

2. 이진검색 재귀

---

 

package test;

import java.util.Arrays;

public class 이진검색_재귀 {
	static int[] arr;
	static int key=5;
	public static void main(String[] args) {
		
		arr = new int[] {5,3,1,2,4};
		
		//이진검색은 반드시 정렬된 상태여야 한다.
		Arrays.sort(arr); //1 2 3 4 5
		
		System.out.println(binarySearch(0,arr.length-1));
		
	}
	
	public static int binarySearch(int start, int end) {
		
		if(start>end) return -1;
		
			int mid = (start+end)/2;
			
			if(arr[mid]==key) return mid;
			else if(arr[mid]>key)return binarySearch(start, mid-1);
			else return binarySearch(mid+1,end);

	}

}

 

---

3. merge Sort - 병합정렬

---

 

- 자료를 최소 단위의 문제까지 나눈 후 차례대로 정렬하여 최종 결과를 얻어낸다.

- 안정정렬이다. 왜냐하면 최악의 경우든, 평균의 경우든 빅오는 O(n log n)이기 때문이다.

 

package test;

import java.util.Arrays;

public class 병합정렬2 {
	static int[] arr;
	static int[] copy;
	public static void main(String[] args) {
		arr = new int[] {3,5,1,2,4};
		copy= new int[] {3,5,1,2,4};
		
		mergesort(0, arr.length-1);
		System.out.println(Arrays.toString(arr));
		
	}
	
	//분할과정 
	static public void mergesort(int start, int end) {
		if(start==end) return;
		
		int mid = (start+end)/2;
		mergesort(start, mid);
		mergesort(mid+1, end);
		merge(start, mid, end);
	}
	
	//병합과정 
	static public void merge(int start, int mid, int end) {
		int leftS=start;
		int rightS=mid+1;
		int idx = start;
		
		while(leftS<=mid && rightS<=end) {
			if(arr[leftS]<arr[rightS]) {
				copy[idx++]=arr[leftS++];
			}
			else {
				copy[idx++]=arr[rightS++];
			}
		}
		
		while(leftS<=mid) {
			copy[idx++]=arr[leftS++];
		}
		
		while(rightS<=end) {
			copy[idx++]=arr[rightS++];
		}
		
		for(int i=start;i<=end;i++) {
			arr[i]=copy[i];
		}
		
	}

}

 

 

---

4. quick Sort - 퀵 정렬

---

 

- 주어진 배열을 2개로 분할하고 각각을 정렬한다.

- 병합은 정확히 중간 지점을 나눠 정렬하지만 퀵정렬은 기준 아이템인 pivot을 기준으로 이보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 둔다.

 

pivot 값을 정하는 방법은 2가지로 호어와 로무토 방법이 있다.

 

 

1) 호어 방법

package test;

import java.util.Arrays;

public class 퀵정렬_호어2 {
	static int[] arr;

	public static void main(String[] args) {
		arr = new int[] { 10, 6, 3, 2, 4, 5, 8, 7, 1, 9 };
		quicksort(0, arr.length-1);
		System.out.println(Arrays.toString(arr));
	}

	static public void quicksort(int start, int end) {

		if (start < end) {

			int pivot = partitioning(start, end);

			// pivot은 이미 정렬된 상태
			quicksort(start, pivot - 1);
			quicksort(pivot + 1, end);
		}
	}

	//호어 방법
	private static int partitioning(int start, int end) {
		int pivot = start;
		int left = start + 1;
		int right = end;

		while (left <= right) {
			while (left <= right && arr[left] <= arr[pivot])
				left++;
			while (arr[right] > arr[pivot])
				right--;

			if (left < right)
				swap(left, right);
		}

		swap(pivot, right);

		return right;// right값에 pivot값이 왔기 때문이다.
	}

	private static void swap(int left, int right) {
		int temp = arr[left];
		arr[left] = arr[right];
		arr[right] = temp;

	}

}

 

2) 로무토 방법

package test;

import java.util.Arrays;

public class 퀵정렬_로무토2 {
    static int[] arr;
    public static void main(String[] args){
        arr=new int[] {10,6,7,8,3,4,6,5,1,2,9};
        quicksort(0, arr.length-1);
        
        System.out.println(Arrays.toString(arr));
    }
    static public void quicksort(int start, int end) {
    	if(start<end) {
    		int pivot = partitioning(start, end);
    		quicksort(start, pivot-1);
    		quicksort(pivot+1, end);
    	}
    }
    
    //로무토 방법
	private static int partitioning(int start, int end) {
		int pivot = end;
		int idx = start - 1;
		int left = start;
		
		for(int i=left;i<end;i++) {
			if(arr[i]<=arr[pivot]) {
				idx++;
				swap(idx,i);
			}
		}
		swap(idx+1,pivot);
		
		return idx+1;
	}
	private static void swap(int a, int b) {
		int temp=arr[a];
		arr[a]=arr[b];
		arr[b]=temp;
	}
}

 

 

 

 

---

끝