버블 정렬 (Bubble Sort)

버블 정렬 (Bubble Sort)

• 레코드가 순서대로 되어 있지 않으면 인접한 항목 교환

버블 정렬 과정

• a[0]과 a[1]을 비교하여 정렬 순서에 맞도록 교환
• a[1]과 a[2]을 비교하여 정렬 순서에 맞도록 교환
• …
• a[n-2] 와 a[n-1]을 비교하여 정렬 순서에 맞도록 교환
• 제일 큰 원소가 배열의 n-1 위치로 이동 (1라운드)
• 배열의 처음부터 다시 비교 정렬

버블 정렬 비교 횟수

• 항목의 개수 N이면 (N-1) + (N-2) + … + 1
• 수학 공식 : N(N-1) / 2

버블 정렬 구현 예시

package sort;

public class BubbleSortEx {

	public static void main(String[] args) {
		int[] arr = {5, 2, 8, 3, 1};
		bubbleSort(arr);
		
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
	static void bubbleSort(int[] arr) {
		//인접한 2개 요소를 교환
		// 2개의 값을 교환할 경우 변수에 값을 저장하는 순간 이전 값은 없어짐
		// 이전 값을 보존하기 위해 임시 장소 필요
		int temp;
		//총 라운드 : 배열크기 - 1번 진행
		for(int i=1; i<arr.length; i++) {
			// 각 라운드별 비교횟수 : 배열크기-라운드 횟수
			for(int j=0; j<arr.length-i; j++) {
				if(arr[j] > arr[j+1]) {
					temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
	}
}