버블정렬이란?
거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법입니다.
시간 복잡도가 $$O(n^2)$$ 로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용사용됩니다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름입니다.
버블정렬 동작 과정
버블정렬 소스코드
BubbleSort.java
public class BubbleSort{
public void sort(int[] arr) {
/*
마지막 인덱스(arr.length)는 실행할 필요가 없기 때문에 -1을 해줍니다.
(9번째 index까지 정렬이 되면 마지막은 당연히 정렬이 됐기 때문에)
*/
for(int i = 0; i<arr.length-1; i++) {
/*
위의 경우와 달리 -1을 해주지 않으면 Runtime Exception이 발생합니다.
arr.length = 10
int i = 0일 경우: if(arr[9] > arr[10])
하지만 arr[10]은 존재 하지 않기 때문에 ArrayIndexOutOfBoundsException이 발생합니다.
*/
for(int j =0; j<arr.length-1-i;j++) {
//해당 값이 다음 값보다 크면, 해당 값과 다음 값을 바꿔줍니다. Swap
if(arr[j]> arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}
BubbleSortLauncher.java
public class BubbleSortLauncher {
public static void main(String[] args) {
int a[] = {7,10,1,8,3,5,2,9,4,6};
BubbleSort bSort = new BubbleSort();
bSort.sort(a);
for(int x : a)
System.out.print(x + " ");
}
}출력
1 2 3 4 5 6 7 8 9 10
글에 오류가 있으면 알려주세요. 감사합니다.
