JAVA_정렬(Bubble-Sort, Selection-Sort / Sequential search, Binary search)

 

Bubble-Sort  (오름차순)

 

  : 두 인접한 원소를 비교하여 정렬하는 방법 속도는 느리지만 코드가 단순

 

[예시]

int[] array= {45,7,12,82,25};
	
	for (int k =1; k<array.length ; k++) {
		for(int i =0; i<array.length-k; i++) 
		{ if(array[i]<array[i+1]) {
				int temp = array[i];
				array[i] = array [i+1];
				array [i+1] = temp;
	}
	}
	}
	System.out.println(Arrays.toString(array));

 

Selection-Sort 

 

1. 내림차순 방법

: 가장 큰 원소 또는 작은 원소를 찾아 주어진 위치(리스트 처음~끝)를 교체해 나가는 정렬 방법

 

 

[예시]

       int[] array = {7,98,13,70,24};
			
	//1. 가장 큰 수 찾기 
		
		int maxIndex =0;
		if(array[maxIndex]<array[1]) { // 비교하기
			maxIndex = 1;
		}
	     int temp = array[maxIndex];   // 자리변경하기
		 array[maxIndex] = array[0];
		 array[0] = temp;
		
		if(array[maxIndex]<array[2]) {
			maxIndex = 2;
		}
		     temp = array[maxIndex];   // 자리변경하기
		  array[maxIndex] = array[1];
		  array[1] = temp;
		  
		if(array[maxIndex]<array[3]) {
			maxIndex = 3;
		}
		    temp = array[maxIndex];   // 자리변경하기
		  array[maxIndex] = array[2];
		  array[2] = temp;
		
		if(array[maxIndex]<array[4]) {
			maxIndex = 4;
		}
		    temp = array[maxIndex];   // 자리변경하기
		  array[maxIndex] = array[3];
		  array[3] = temp;


		//1-1. 숫자비교 for문으로 정리 
		int maxIndex =0;
		for(int i=1; i<array.length; i++) {
		if(array[maxIndex]<array[i]) {
			maxIndex = i;
		  }
		}
		   int temp = array[maxIndex];  
		    array[maxIndex] = array[0];
		    array[0] = temp;
	
    
		// 1-2 자리변경 for문 정리 
		    
		    for(int k=0; k<array.length-1; k++) {
		    int maxIndex =k;
			for(int i=maxindex+1; i<array.length; i++) {
			if(array[maxIndex]<array[i]) {
				maxIndex = i;
			  }
			}
			   int temp = array[maxIndex];  
			    array[maxIndex] = array[k];
			    array[k] = temp;
		    }
	   System.out.println(Arrays.toString(array));

 

---

Sequential search

 

: 가장 단순한 검색 방법으로 원소의 정렬이 필요 없다. 하지만 리스트 길이가 길면 비효율적

      int[] array = {13,35,15,11,26,72,78,13,61,90};
		
	//1. 찾고자 하는 숫자 설정
		int searchData = 78;
		
	//2. 하나씩 비교하기 
		int index = 0 ;
		for(int i = 0; i<array.length; i++) {
		if(searchData == array[i]) {
			index =i;
			break ;
		  }			
		}
       System.out.println(searchData+"는"+index+"번째 숫자 입니다.");

 

Binary search

 

: 리스트의 중간 값을 정해 크고 작음을 비교해 검색하는 알고리즘 정렬된 리스트에 사용 할 수 있다.

 

 

 

 

        int[] array = {1,7,16,25,30,33,41,66,78,90};
		
		int searchData = 78;
		
		int li = 0;
		int hi = array.length-1;
		int mi = (li+hi)/2;
		
		
	// 1.규칙 확인하기
    
		if(searchData==array[mi]) {
			System.out.println("찾았다"+mi);
		}else if(searchData >array[mi]) {
			li = mi+1;
		
		}else if(searchData<array[mi]) {
			hi = mi-1;
		}
	
	// 2. 반복해주기
		
		while(true) {		
	       mi = (li+hi)/2; // 반복해줄때마다 middle index는 변경되어야 한다.	    
		if(searchData==array[mi]) {
			System.out.println("찾았다"+mi);
			break;
		}else if(searchData >array[mi]) {
			li = mi+1;
		
		}else if(searchData<array[mi]) {
			hi = mi-1;
		}	
		
		if(li>hi) {
		  System.out.println("찾는 데이터가 없습니다.");
		  break; 			
		}

 

출처:스마트인재개발원