버블 정렬은 배열의 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초가 걸렸다.
버블 정렬은 배열의 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초가 걸렸다.
