0319 선택정렬, 이진탐색

선택정렬(Selection Sort)

if 오름차순일 때,
1회전: 첫 번째 수와 2~n 번째 수를 비교해서 가장 작은 수를 첫 번째 자리에 위치시킨다.
2회전: 두 번째 수와 3~n 번째 수를 비교해서 가장 작은 수를 두 번째 자리에 위치시킨다.
n-1회전: n-1번째 수와 n번째 수를 비교해서 가장 작은 수를 n-1 번째 자리에 위치시킨다.

for문이 2중: 시간복잡도는 O(n^2)

package prac;

public class SelectionSort {

	public static void main(String[] args) {

		int[] arr = {3, 2, 5, 1, 4};
		int min;
		
		for(int i=0; i<arr.length; i++) {
			System.out.print("i: "+i+"  | ");
			for(int j=i+1; j<arr.length; j++) {
				System.out.print("j: "+j+" ");
				if(arr[i]>arr[j]) {
					min=arr[j];
					arr[j]=arr[i];
					arr[i]=min;
				}
			}
			System.out.println("");
		}
		
		System.out.print("선택정렬 결과: ");
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
	}
}

이진 탐색(Binary Search)

int[] arr = {1, 2, 3, 4, 5, 6, 7} 일 때, 8이 있는지 찾으면 없다.
*배열은 정렬되어 있어야 함!!
n을 찾을 때, arr의 중간 값인 4보다 큰지 비교한다. x반복

이진탐색의 시간복잡도: O(logN)

		int[] arr = {1,2,3,4,5,6,7};
		int searchNum = 8;
		int left = 0;
		int right = arr.length - 1;
		int mid;
		boolean find=false;

		while (left <= right) {
			mid = (left + right) / 2;
			if(arr[mid] < searchNum) left = mid + 1;
			else if(arr[mid] > searchNum) right = mid - 1;
			else {
				find=true;
				System.out.println(mid+"번째에 있습니다.");
				break;
			}
		}
		
		if(find==false)
			System.out.println("그 숫자는 없습니다.");