버블 정렬 (Bubble Sort)
버블 정렬 (Bubble Sort)
- 가장 단순한 정렬 알고리즘
- 인접한 요소와 정렬 기준(오름차순, 내림차순)대로 교환
- 안정 정렬 (stable sort)
: 정렬 후에도 같은 값들 끼리의 순서가 보장됨을 의미 - 제자리 정렬 (in-place sort)
: 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미 - 정렬한 데이터의 개수가 적을때는 나쁘지 않은 속도를 보임
버블 정렬 방법 (오름차순 기준)
- 첫 번째 사이클이 끝나면 맨 마지막 값이 정렬되고, 두 번째 사이클이 끝나면 뒤에서 두 번째의 값이 정렬된다. 이같은 과정을 계속 반복하면 최종적으로 정렬이 된다.
버블 정렬의 성능
- 시간복잡도
최악의 경우 : O(n^2)
최선의 경우 : O(n) - 최악의 경우 : 모든 데이터가 역순인 경우 (5, 4, 3, 2, 1)
5를 정렬하기 위해서는 n-1번 비교 및 교환해야하고, 4를 정렬하기 위해서는 n-2번 비교 및 교환해야 한다.
즉, 5를 정렬할 때 4번, 4를 정렬할 때 3번, 3을 정렬할 때 2번, 1과 2를 정렬할 때 1번의 비교 및 교환을 거치게 되므로 비교 횟수는 4 + 3 + 2 + 1회가 된다.
따라서, 데이터가 n개일 때 총 비교횟수는 (n-1) + (n-2) + (n-3) + ... + 2 + 1 이 되므로 등차수열의 합에 따라 1/2n(n-1)이 되며 빅-오는 최고차항을 가지기 때문에 O(n^2)이 된다. - 최선의 경우 : 모든 데이터가 이미 정렬된 경우 (1, 2, 3, 4, 5)
한 번도 교환이 이루어지지 않았다면 이미 정렬된 상태이므로 n번 비교 후 반환되어 O(n) 이 된다.
기본 구현
- 기본 int형 배열 정렬 구현
[BubbleBasic.java]
package Sort.Bubble; /** * 단순히 int형 배열만 오름차순 또는 내림차순으로 정렬하는 경우 */ public class BubbleBasic { private boolean isDescending = false; /** * @param arr int형 배열 * @param isDescending 내림차순 및 오름차순 선택 */ public static void sort(int[] arr, boolean isDescending) { // 이미 정렬이 되어있는지 확인하기 위한 변수 boolean isAlreadySorted = true; int n = arr.length; // 정렬할 값을 선택하는 반복문 for(int i=0; i<n-1; i++) { // 정렬할 값과 나머지 값들을 비교하기 위한 반복문 // 이미 정렬이 완료된 데이터는 비교대상에서 제외해야 하므로 n-i-1 for(int j=0; j<n-i-1; j++) { // 정렬되지 않았다면 if (!isSortTwoElements(arr[j], arr[j + 1], isDescending)) { // 데이터를 교환한다. swap(arr, j, j + 1); // 스왑을 했다면 초기 배열 상태가 정렬되지 않았다는 것이므로 false로 변경 isAlreadySorted = false; } } // 한 번도 교환이 발생하지 않았다면 이미 정렬된 데이터이므로 반복문을 빠져나온다. if (isAlreadySorted) { break; } } } /** * * @param arr 데이터 배열 * @param idx1 교환할 인덱스 * @param idx2 교환할 인덱스 */ private static void swap(int[] arr, int idx1, int idx2) { int tmp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = tmp; } /** * * @param cmp1 비교할 값 * @param cmp2 비교할 값 * @param isDescending 내림차순 및 오름차순 선택 * @return 내림차순의 경우 cmp1이 작을 경우 false, 그렇지 않으면 true * 오름차순의 경우 cmp1이 작을 경우 true, 그렇지 않으면 false */ private static boolean isSortTwoElements(int cmp1, int cmp2, boolean isDescending) { // 내림차순일 경우 if (isDescending) { if (cmp1 < cmp2) { return false; } else { return true; } } // 오름차순일 경우 else { if (cmp1 < cmp2) { return true; } else { return false; } } } } - BubbleBasic.java 테스트 및 실행시간 측정
package Sort.Bubble; public class BubbleBasicMain { private static final int MAX_COUNT = 10; public static void main(String[] args) { int[] arr = new int[MAX_COUNT]; for(int i=0; i<MAX_COUNT; i++) { // 0 ~ MAX_COUNT 범위내의 난수를 생성 arr[i] = (int)(Math.random() * MAX_COUNT); } // 배열은 참조형 이므로 arr을 넘길 경우 arr값이 변경되기 때문에 복사본을 생성한 후 테스트 int[] ascArrTest = arr.clone(); System.out.println("정렬 전 데이터"); for(int i : ascArrTest) { System.out.println(i); } System.out.println(); BubbleBasic.sort(ascArrTest, false); System.out.println("오름차순 정렬 후 데이터"); for(int i : ascArrTest) { System.out.println(i); } System.out.println(); int[] descArrTest = arr.clone(); BubbleBasic.sort(descArrTest, true); System.out.println("내림차순 정렬 후 데이터"); for(int i : descArrTest) { System.out.println(i); } // 시간복잡도 측정 (오름차순 기준) long start = 0; long end = 0; int[] bestTimeComplexityArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; start = System.nanoTime(); BubbleBasic.sort(bestTimeComplexityArray, false); end = System.nanoTime(); System.out.println("최선의 경우 오름차순 시간 : " + (end - start) + "ns"); int[] worstTimeComplexityArray = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; start = System.nanoTime(); BubbleBasic.sort(worstTimeComplexityArray, false); end = System.nanoTime(); System.out.println("최악의 경우 오름차순 시간 : " + (end - start) + "ns"); } } - 결과
정렬 전 데이터
2
6
1
7
7
6
0
6
1
0
오름차순 정렬 후 데이터
0
0
1
1
2
6
6
6
7
7
내림차순 정렬 후 데이터
7
7
6
6
6
2
1
1
0
0
최선의 경우 오름차순 시간 : 3805ns
최악의 경우 오름차순 시간 : 18532ns
클래스 비교를 위한 구현
- 클래스의 특정 값을 이용한 정렬 코드 구현
[BubbleAdvanced.java]
package Sort.Bubble; import java.util.Comparator; public class BubbleAdvanced { public static <T> void sort(T[] arr) { Comparable<? super T> comp; boolean isAlreadySorted = true; int n = arr.length; for(int i=0; i<n-1; i++) { for(int j=0; j<n-i-1; j++) { comp = (Comparable<? super T>)arr[j]; if (comp.compareTo(arr[j + 1]) > 0) { swap(arr, j, j + 1); isAlreadySorted = false; } } if (isAlreadySorted){ break; } } } /** * * @param arr 데이터 배열 * @param idx1 교환할 인덱스 * @param idx2 교환할 인덱스 */ private static <T> void swap(T[] arr, int idx1, int idx2) { T tmp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = tmp; } public static <T> void sort(T[] arr, Comparator<? super T> comparator) { boolean isAlreadySorted = true; int n = arr.length; for(int i=0; i<n-1; i++) { for(int j=0; j<n-i-1; j++) { if (comparator.compare(arr[j], arr[j + 1]) > 0) { swap(arr, j, j + 1); isAlreadySorted = false; } } if (isAlreadySorted){ break; } } } } - BubbleAdvanced 테스트
package Sort.Bubble; import java.util.Comparator; public class BubbleAdvancedMain { private static final int MAX_COUNT = 10; public static void main(String[] args) { Integer[] arr = new Integer[MAX_COUNT]; for (int i = 0; i < MAX_COUNT; i++) { // 0 ~ MAX_COUNT 범위내의 난수를 생성 arr[i] = (int) (Math.random() * MAX_COUNT); } // 배열은 참조형 이므로 arr을 넘길 경우 arr값이 변경되기 때문에 복사본을 생성한 후 테스트 Integer[] ascArrTest = arr.clone(); System.out.println("정렬 전 데이터"); for (int i : ascArrTest) { System.out.println(i); } System.out.println(); BubbleAdvanced.sort(ascArrTest); System.out.println("오름차순 정렬 후 데이터"); for (int i : ascArrTest) { System.out.println(i); } System.out.println(); Integer[] descArrTest = arr.clone(); System.out.println("내림차순 정렬 후 데이터"); BubbleAdvanced.sort(descArrTest, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { if (o1 < o2) { return 1; } else if (o1 == o2) { return 0; } else { return -1; } } }); for (int i : descArrTest) { System.out.println(i); } System.out.println(); // 클래스의 특정값을 이용한 정렬 가능 class Student { String name; int age; public Student(String name, int age) { this.name = name; this.age = age; } @Override public String toString() { return "name='" + name + '\'' + ", age=" + age; } } System.out.println("클래스 정렬 전 데이터"); Student[] students = new Student[5]; students[0] = new Student("아이언맨", 11); students[1] = new Student("헐크", 4); students[2] = new Student("토르", 15); students[3] = new Student("블랙위도우", 13); students[4] = new Student("캡틴", 4); for(Student student : students) { System.out.println(student.toString()); } System.out.println(); System.out.println("클래스 정렬 후 데이터"); BubbleAdvanced.sort(students, new Comparator<Student>() { @Override public int compare(Student o1, Student o2) { if (o1.age < o2.age) { return -1; } else if (o1.age == o2.age) { return 0; } else { return 1; } } }); for(Student student : students) { System.out.println(student.toString()); } } } - 결과
정렬 전 데이터
7
0
0
9
4
4
6
0
5
0
오름차순 정렬 후 데이터
0
0
0
0
4
4
5
6
7
9
내림차순 정렬 후 데이터
9
7
6
5
4
4
0
0
0
0
클래스 정렬 전 데이터
name='아이언맨', age=11
name='헐크', age=4
name='토르', age=15
name='블랙위도우', age=13
name='캡틴', age=4
클래스 정렬 후 데이터
name='헐크', age=4
name='캡틴', age=4
name='아이언맨', age=11
name='블랙위도우', age=13
name='토르', age=15
'0x20. 알고리즘 > 0x21. 이론' 카테고리의 다른 글
| [JAVA] 삽입 정렬 (Insertion Sort) (0) | 2021.11.04 |
|---|---|
| [JAVA] 선택 정렬 (Selection Sort) (0) | 2021.11.03 |
| 깊이 우선 탐색 (DFS, Depth-First Search) (0) | 2021.10.08 |
| 순열(Permutation) 구하기 (0) | 2021.10.06 |
| 그리디(Greedy) 알고리즘 (탐욕 알고리즘) (0) | 2021.10.05 |
