버블 정렬 , 선택 정렬 , 삽입 정렬

이한수·2022년 5월 23일

버블 정렬 삽입 정렬 선택 정렬 알고리즘

알고리즘

목록 보기

2/5

1.버블 정렬(Bubble Sort)

인접한 두 원소를 비교하여 정렬하는 알고리즘 이다.
반복을 진행하면서 매 회차마다 큰 수를 뒤쪽에 위치 시킨다.

ex)
13 20,15,30,50,2 라는 숫자 배열이 있다고 가정해 보자.
오름차순을 경우로 정렬을 진행.

java

public static void main(String args[]){
	int [] arr = {13,20,15,30,50,2};
    
    
        for(int i=0 ; i < arr.length ; i++){
        
            for(int j=1 ; j<arr.length-i ; j++){
            
                if(arr[j-1] > arr[j]) {
                    int tmp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = tmp;
                }
                
            }
            
        }
}

안쪽 for문으로 접어들 때 마다 ,바깥 for문으로 부터 들어오는 i의 값은 1씩 증가할 것이다. 이를 이용하여, arr.length-i 매 회차 맨 뒤쪽에 자리 잡는 제일 큰 숫자를 비교 대상에서 제외 시켜 준다.

시간 복잡도 : O(n^2)

장점

구현하기 간단 하다.

단점

비교 횟수가 많다.
교환 횟수가 많다. -> 즉 , 데이터의 이동이 많다.

2.선택 정렬

-버블 정렬과 반대로 매 회차마다 정렬할 대상에서 최솟값을 맨 앞에 부터 위치 시킨다.

ex)

java

public static void main(String args[]){
	int [] arr = {13,20,15,30,50,2};
    
    
    
       for(int i=0 ; i<arr.length ; i++){
       
           int idx = i;
           int tmp = 0;

          	 for(int j=i+1 ; j<arr.length ; j++){
               	if(arr[idx] > arr[j]) idx = j;
           	}

           tmp = arr[idx];
           arr[idx] = arr[i];
           arr[i] = tmp;
       }
     
}

안쪽 for문으로 접어들 때 마다 ,증가한 i값을 이용하여 안쪽 for문의 시작 값 j를
서서히 증가 시켜 앞쪽에 자리 잡은 최솟값들을 비교 대상으로 부터 제외 시켜준다.

또한 두번째 for문의 if문에서 arr[idx]로 설정해주는 것이 핵심이다.

시간 복잡도 : O(n^2)

장점

구현하기 간단 하다.

단점

비교 횟수가 많다.

3.삽입 정렬

-앞쪽에 정렬되어 있는 배열에 삽입할 데이터를 비교하여 해당 데이터의 적절한 위치를 찾는 방식이다.

버블 정렬의 비효율적인 면인 비교횟수를 효율적으로 줄이기 위해 고안된 방식이다

ex)

public static void main(String args[]){
	 int [] arr = {13,20,15,30,50,2};	
     int j;
        
       for(int i=1 ; i<arr.length ; i++){
           int idx = arr[i];
           
           for(j=i-1; j>=0 ; j--){
           
                if(arr[j] > idx) arr[j+1] = arr[j];
                else break;
                
           }
           
           arr[j+1] = idx;
       }