[알고리즘] 버블정렬 & 이진탐색

 

이번 포스팅에서는 버블정렬과 정렬된 배열을 이용하여 이진탐색하는 법을 정리하였다.

 

---

 

1. 버블정렬

 

1) 개념

: 버블정렬이란 오름차순의 경우 시작 인덱스부터 종료 인덱스까지 반복하며, 왼쪽의 값보다 오른쪽의 값이 더 크다면 교환 알고리즘을 통해 값을 교환하는 방식이다. 배열의 길이까지 1회 반복하게 되면 무조건 가장 큰 값은 제자리(마지막인덱스)에 위치하게 된다. 즉, 정렬이 완료될때까지 이와같은 인덱스간의 값교환을 반복하는 정렬 방법이다.

 

 

 

---

 

2) 구현

 

for(int i=0;i<data.length-1;i++) { //교환은 무조건 배열의 길이-1만큼의 반복이면 종료된다.
         for(int j=0;j<data.length-1;j++) { //10개의 배열이라면 교환은 9번만 반복하기 때문.
            if(data[j] > data[j+1]) {
               int tmp=data[j];
               data[j]=data[j+1];
               data[j+1]=tmp;
            }
         }
      }

      for(int v:data) { //for each문으로 배열값 조회
         System.out.print(v+" ");
      }

 

주석의 설명을 참고하여 반복할 횟수를 먼저 지정하고, 오름차순인지 내림차순인지를 결정한다.

오름차순의 경우 [비교할 인덱스의 값] > [그 다음 인덱스의 값] 이라면 교환!

내림차순의 경우 [비교할 인덱스의 값] < [그 다음 인덱스의 값] 이라면 교환이다.

반복문이 종료되면 정렬된 데이터를 확인해볼 수 있다.

 

 

---

 

 

3. 이진탐색

 

1) 개념과 이론

 

이진탐색은 가장 작은 값의 인덱스와 가장 큰 값의 인덱스, 기준이 될 중간의 인덱스에 각각 기준점을 설정하고 m에 존재하는 값과 찾을 데이터가 일치하다면 종료된다. 따라서 이진탐색은 정렬된 배열을 조건으로 한다. 필기 내용으로 설명하자면 아래를 참고할 수 있다.

 

[ 1 2 3 4 5 6 7 8 9 10]
  L        M            H

L=data[0]
H=data[9]
찾을데이터: 3

(1) 가운데를 설정한다.
M=data[4]

(2) M에 존재하는 값 > 찾을데이터
H=M-1 로 재조정
H=data[3]으로 설정된다.

(3) 다시 가운데를 설정한다.
M=data[1]

(4) M에 존재하는 값 < 찾을데이터
L=M+1 로 재조정
L=data[2]로 설정된다.

(5) 가운데를 설정한다.
M=data[2]

(6) M에 존재하는 값 == 찾을데이터
찾았다!!!!!
[2]에 3 데이터가 존재합니다.

 

 

---

 

 

2) 구현

 

	int L=0; //기준점 설정
      int H=data.length-1; //기준점 설정
      Scanner sc=new Scanner(System.in);
      System.out.print("찾을데이터 입력: ");
      int user=sc.nextInt();
      
      boolean flag=true;
      while(L<=H) { // L>H : cross발생시, 종료됨!
         int M=(L+H)/2; //M의 값은 항상 변동되므로 반복문 안에 선언
               
         if(data[M]==user) { //반복문의 종료조건 : 값을 찾았을때
            System.out.println("["+M+"]에 "+user+"데이터가 존재합니다.");
            flag=false;
            break;
         }
         else if(data[M] > user) {
            H=M-1;
         }
         else {
            L=M+1;
         }
      }

      if(flag) {
         System.out.println(user+"데이터는 존재하지않습니다."); //사용자가 잘못입력시
      }

 

boolean flag를 이용하여, 사용자가 제대로 된 값을 입력하지 않았을때 "존재하지 않는다" 안내를 주고 반복문에 진입하지 않는다. 제대로 입력했다면 flag=false이므로 종료된다.