버블 정렬 - Java

알고리즘 개념

• 인접한 2개의 레코드를 비교하며 정렬
  • 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환
• 1회전이 돌때 마다 정렬이 완료된 레코드가 가장 오른쪽에 1개씩 추가됨

 

코드 - Java

	// buble sort
	for(int i = N-1; i >=0 ; i--) {
		int chage = 0;
		for(int j=0; j<i; j++) {
			if(arr[j]> arr[j+1]) {
				chage++;
				int tem = arr[j];
				arr[j] = arr[j+1];
				arr[j+1]= tem;
			}
		}
		if(chage == 0) break;
 	}

 

 

시간 복잡도 분석

비교 횟수

• (n-1) + (n-2) .. 2 + 1 = (n * (n+1)) / 2
• 시간 복잡도: O(n^2)
• 최선, 평균, 최악 모두 같다.

이동 횟수

• 최악의 경우, 인접한 레코드가 계속 교환되기 때문에 마찬가지로 O(n^2)
• 이때 교환은 3번의 이동을 포함하기 때문에 실제 횟수는 3을 곱한 값이다.

1. • 시간 복잡도: O(n^2)이동 횟수

   최악	평균	최선
   O(n^2)	O(n^2)/2	0

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

 

단점

• 특정 요소가 최종 정렬 위치에 있는 경우에도 교환이 일어날 수 있다.
• 하나의 요소가 가장 오른쪽에서 왼쪽으로 이동하기 위해서는 모든 요소와 비교, 교환 작업이 일어난다.
• 일반적으로 자료의 교환작업이 이동 작업보다 복잡하기 때문에 버블정렬을 거의 쓰이지 않는다.