[알고리즘] JAVA - Bubble 정렬

 

 

 

- 인접한 요소를 정렬기준(오름차순, 내림차순)대로 교환한다.

- 안정 정렬이다.(stable sort) => 정렬 후에도 같은 값들 끼리의 순서가 보장된다.

-  제자리 정렬(in-place sort) => 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미한다.

- 정렬한 데이터의 개수가 적을때는 나쁘지 않은 속도를 보인다.

 

 

과정

 

1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교한다.

2. 현재 원소가 다음 원소보다 크면 원소를 교환한다.

3. 다음 원소로 이동하여 해당 원소와 그 다음원소를 비교한다.

 

JAVA 코드로 보면

 

만약 {3,5,2}가 주어질 경우

 

1번 반복
for(int index=0;index < 3 - 1;index++){
	boolean swap = false;
    for(int index2 = 0;index2 < 3 - 1 - 0;index2++){
    	if( 3 > 5){
        	//false라 수행 안함	
            }
            //두번째 for문에 index2일때
            //if(5>2) 이기 때문에 여기서 swap이 일어나고 true값이 들어간다.
        }
        if(swap == false){
        		//값이 변경되고 탈출은 안함
        }
    }
  
  1번 반복했을때 배열 값은 {3,2,5}
        
    
 2번 반복
 for(int index=1;index<2;index++){
 	for(int index2 = 0;index2<3 - 1 - 1;index2++){
    	if(3 > 2){
        	//swap이 일어나고 true 값이 들어간다.
        }	//두번쨰 if는 if(3>5) 이기에 수행하지 않음
    }
    if(swap==false){
    		//값이 한 번 변경되어 수행되지 않음
    }
        
}

이렇게 결과는 {2,3,5}로 정렬된다.

여기서 for문은

for(index; index < arr.length - 1 ; index++){
	for( index2 ; index2 < arr.length - 1 - index ; index2){
    	//생략
    }
}

이런 형식인데 여기서 중요한 것은 안에  for문은 a.length- 1 - index이다. 이렇게 index(외부 for문에 index)를 뺀 이유는 이미 뒤에 요소들은 오름차순으로 정렬되었기에 정렬할 필요가 없기에 빼는 것이다.

 

 

참고

-https://st-lab.tistory.com/195

자바 [JAVA] - 거품 정렬 (Bubble Sort)

- https://banjjak1.tistory.com/46