day04) 알고리즘-버블정렬을 이용한 이진탐색

버블정렬

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘. 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환한다

문제

1. 정수입력: 10(10이하 입력)
   10개의 데이터 저장
   범위 10~99(중복xxx)
2.  오름차순 정렬
    (버블정렬)
3.  이진탐색
    데이터검색

public class Test04TotalAlgo {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Random rand = new Random();

		System.out.print("배열 길이 입력: ");
		int num;
		while(true) {
			num=sc.nextInt();
			if(num<5||num>20) {
				System.out.println("5~20 사이값을 입력하세요");
				continue;}
			break;
		}
		int[] data = new int[num];//배열 생성
		int i=0;


		//========중복값 제거===========
		while(i<data.length) {
			data[i]=rand.nextInt(90)+10;//i에 들어갈 숫자 랜덤생성 10~99;
			boolean flag=false;//중복여부 확인을 위한 flag
			for (int j = 0; j < i; j++) {//배열 i-1번방까지 중복확인
				if(data[i]==data[j]) {
					flag=true;
					break;
				}
			}
			if(flag) {
				continue;
				//중복이 있을 시 randNum 재설정
			}
			i++;//중복이 없을시 다음 배열의 방으로 이동
		}
		System.out.print("[");
		for(int v:data) {
			System.out.print(v+" ");
		}
		System.out.println("]");

		//==============버블 정렬============
		for (int a = 0; a < data.length-1; a++) {//맨 왼쪽 값은 [1]값이 정해지면 자동적으로 정해지므로 data.length-1
			for (int j = 0; j < data.length-1; j++) {//두개씩 정렬하므로 length-1
				if(data[j]>data[j+1]) {
					int tmp=data[j];
					data[j]=data[j+1];
					data[j+1]=tmp;
				}
			} // 1회전 정렬:오른쪽끝부터 자기자리를 찾아감

		} // 데이터개수-1 번 해줘~~~

		System.out.print("[");
		for(int v:data) {
			System.out.print(v+" ");
		}
		System.out.println("]");

		//===========이진탐색==========
		System.out.print("정답입력: ");
		int ans=sc.nextInt();
		int l=0;
		int h=data.length-1;//이진탐색을 위한 low값과 high값 초기화

		boolean flag=true;//cross 판별을 위한 flag
		while(h>=l) {
			int m=(l+h)/2;//중간값
			if(data[m]==ans) {
				System.out.println("["+m+"]에 "+ans+"데이터가 존재합니다.");
				flag=false;
				break;
			}else if(data[m]>ans) {
				h=m-1;
			}else {
				l=m+1;
			}
		}
		if(flag) {
			System.out.println(ans+"데이터가 존재하지 않습니다");
		}
	}
}