[Algorithm] Basic Sort Algorithm - Bubble Sort (버블 정렬)

서로 이웃한 데이터들을 비교하여 가장 큰 데이터를 가장 뒤에 보내며 정렬하는 방식

가장 큰 값을 마지막으로 보내는 개념은 selection sort와 유사

 

Bubble Sort

public void bubbleSort(int[] arr) {
	if (arr.length == 0) {
		return;
	}
	
	System.out.print("[정렬할 원소] ");
	print(arr);
	
    	// 뒤에서부터 정렬하므로 last pointer는 정렬된 데이터 앞을 가리킴
	for (int last=arr.length-1; last>=0; last--) {	 // 1
		for (int i = 0; i <= last-1; i++) {	 // 2
			if (arr[i] > arr[i+1]) {
				swap(arr, i, i+1);	 // 3
			}
		}
		
		System.out.print(arr.length - last + "단계 : ");
		print(arr);
	}
}

 

실행시간

1번의 for 루프는 n-1번 반복

2번의 for 루프는 각각 n-1, n-2, ..., 2, 1번 반복

3번의 교환은 상수 시간 작업

 

시간복잡도:  T(n) = (n-1)+(n-2)+...+2+1 = O(n^2)

 

 

 

 

 

Ref. https://www.youtube.com/watch?v=0dG7xTt5IfQ