728x90
버블 정렬은 배열의 0번 인덱스와 1번 인덱스를 비교하고 1번 인덱스와 2번 인덱스를 비교하는 과정을 처음부터 마지막 인덱스까지 반복하여 진행한다. 즉 인접 인덱스를 비교하면서 정렬하는 방식이다. 1회전을 수행하고 나면 제일 큰 숫자가 맨 뒤에 위치하게 된다. 따라서 다음 회전에서는 마지막 인덱스-1까지만 고려한다.
버블 정렬의 성능 분석 공식은 S(n) + S(n-1) + … + S(2) = (n-1) + (n-2) + (n-3) + … + 3 + 2 + 1 가 된다. 여기서의 S(n)은 인덱스 비교하는 시간 = 교환하는 시간이라고 한다. 식을 정리하면 O(n^2) 임을 알 수 있다.
위의 이미지에서는 5 3 1 4 2 의 자료를 정렬하는 과정을 보여주고 있다. 이를 자바 소스 코드로 작성하면 다음과 같다.
public class Main {
public static void bubbleSort(int[] a){
int N = a.length;
for (int i = 0; i < N-1; i++) {//총 회전수
for (int j = 0; j < N-1-i; j++) {//한 회전당 비교 횟수
if(a[j] > a[j+1]){//현재 인덱스와 다음 인덱스를 비교
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;//swap
}
}
}
}
public static void main(String[] args) {
int[] a= {8,31,48,73,3,65,20,29,11,15};
bubbleSort(a);
for(int i:a){
System.out.printf("%d ",i);
}
}
}
버블 정렬하는데 걸린 시간을 직접 측정해보자. 임의의 데이터 10000개로 실험한다. CodeChef의 경우에는 시간 소모가 길어지면 에러가 뜨는 경향이 있어서 위 실험은 Geeksforgeeks에서 실행하였다. 앞으로 정렬들 시간을 동일한 조건에서 비교할 예정이다.
버블 정렬은 2.654초가 걸렸다.
728x90
