[Algorithm] 정렬 - Bubble Sort (거품 정렬)

Bubble Sort

• 첫번째와 두번째 원소를 비교하여 정렬, 두번째와 세번째 , ... , n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 첫번째와 두번째, ... , n-2번째와 n-1번째 ... 이를 반복하는 방식이다.
• Selection Sort와 마찬가지로 O(n^2)이다.

• 

동작

Step1

Step2 부터 j가 이동하면서 swap하지않고 그냥 지나가는 것은 생략한다.

Step2 

Step3

Step4

Step5

Step6

코드 (Java)

public class Sort {

	public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = arr[index1];
    }
    
    public void bubbleSort(int[] arr) {
    	for(int i = arr.length - 1; i >= 0; i--) {
        	for(int j = 0; j < i; j++) {
            	if(arr[j] > arr[j+1]) {
                	swap(arr, j, j+1);
                }
            }
        }
    }
}