1. 버블 정렬
두 인접한 데이터의 크기를 비교하여 정렬.
간단한 구조, 느린 속도. 시간복잡도 : O(n^2)
int[] n = {5,4,3,2,1,1,2,3,4,5};
// 버블 정렬 for (int i = 0; i < n.length; i++) { for (int j = 0; j < n.length - 1; j++) { if (n[j] > n[j+1]) { int temp = n[j]; n[j] = n[j+1]; n[j+1] = temp; } } }
결과 : [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
인접한 데이터끼리 자리교체가 이루어지기 때문에 맨 마지막 부터 정렬되기 시작한다 -> 길이를 줄여나간다.
더 이상 자리교체가 이루어지지 않는다면 while문을 종료한다.
이를 통해 약간의 성능 개선이 가능...
boolean swap = true; int length = n.length; while (swap) { swap = false; for (int i = 0; i < length - 1; i++) { if (n[i] > n[i+1]) { int temp = n[i]; n[i] = n[i+1]; n[i+1] = temp; swap = true; } } length--; }
2. 선택 정렬
최소 또는 최댓값을 찾고 남은 데이터와 비교하여 자리 교체를 하는 알고리즘.
구현 방법이 약간 복잡. 속도 느림. 시간복잡도 : O(n^2)
for (int i = 0; i < n.length; i++) { int min = i; for (int j = i + 1; j < n.length; j++) { if (n[j] < n[min]) { min = j; } } if (n[i] > n[min]) { int temp = n[i]; n[i] = n[min]; n[min] = temp; } }
가장 낮은 숫자의 index 번호를 min으로 설정.
i번째 n이 min번째 n보다 크다면 자리 교체
3. 삽입 정렬
정렬된 데이터 범위 내에서 정렬되지 않은 선택된 데이터를 적절하게 삽입해야하는 알고리즘.
시간 복잡도는 O(n^2)
for (int i = 0; i < n.length; i++) { int insert_index = i; int insert_value = n[i]; for (int j = i - 1; j >= 0; j--) { if (n[j] < insert_value) { insert_index = j + 1; break; } if (j == 0) { insert_index = 0; } } for (int j = i; j > insert_index; j--) { n[j] = n[j-1]; } n[insert_index] = insert_value; }
4. 퀵 정렬
pivot (기준값)을 선정하여 pivot의 왼쪽과 오른쪽을 분할과 정복해 나가며, pivot 값보다 작은값과 큰 값을 분류하여 정렬하는 알고리즘.
pivot을 잘 선택해야한다. pivot값에 따라 시간 복잡도가 느려지거나 빨라진ㅈ다. 평균 시간 복잡도는 O(nlogn)
quickSort(n, 0, n.length-1);
public static void quickSort(int[] n, int left, int right) { if (left < right) { int pivot = partition(n, left, right); quickSort(n, left, pivot - 1); quickSort(n, pivot + 1, right); } } public static int partition(int[] n, int left, int right) { int pivot = n[right]; int i = left - 1; for (int j = left; j < right; j++) { if (n[j] < pivot) { i++; swap(n, i, j); } } swap(n, i + 1, right); return i + 1; } private static void swap(int[] n, int i, int j) { int temp = n[i]; n[i] = n[j]; n[j] = temp; }
5. 병합 정렬
분할 정복 방식을 사용해 정렬하는 알고리즘. 평균 시간복잡도는 O(nlogn)
mergeSort(n);
public static void mergeSort(int[] n) { if (n.length < 2) { return; } int mid = n.length / 2; int[] left_n = new int[mid]; int[] right_n = new int[n.length - mid]; for (int i = 0; i < mid; i++) { left_n[i] = n[i]; } for (int i = mid; i < n.length; i++) { right_n[i - mid] = n[i]; } mergeSort(left_n); mergeSort(right_n); merge(n, left_n, right_n); } private static void merge(int[] n, int[] left_n, int[] right_n) { int i = 0, j = 0, k = 0; while (i < left_n.length && j < right_n.length) { if (left_n[i] <= right_n[j]) { n[k++] = left_n[i++]; } else { n[k++] = right_n[j++]; } } while (i < left_n.length) { n[k++] = left_n[i++]; } while (j < right_n.length) { n[k++] = right_n[j++]; } }
6. 기수 정렬
0-9 까지의 값을 놓고 자릿수에 따라 값을 비교하여 정렬
945와 623을 비교한다면, 1의 자리부터 5와 3, 10의 자리 4와 2, 100의 자리 9와 6을 비교.
int[] n = {331, 75, 65, 90, 802, 524, 2, 66};
radixSort(n);
public static void radixSort(int[] n) { int max = getMax(n); for (int exp = 1; max / exp > 0; exp *= 10) { countSort(n, exp); } } private static void countSort(int[] n, int exp) { int[] output = new int[n.length]; int[] count = new int[10]; for (int i = 0; i < n.length; i++) { count[(n[i] / exp) % 10]++; } for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; } for (int i = n.length - 1; i >= 0; i--) { output[count[(n[i] / exp) % 10] - 1] = n[i]; count[(n[i] / exp) % 10]--; } for (int i = 0; i < n.length; i++) { n[i] = output[i]; } } private static int getMax(int[] n) { int max = n[0]; for (int i = 1; i < n.length; i++) { if (n[i] > max) { max = n[i]; } } return max; }
결과 : [2, 65, 66, 75, 90, 331, 524, 802]
'Java' 카테고리의 다른 글
[JAVA] Arrays.sort() (0) | 2023.05.17 |
---|---|
[JAVA] 디자인 패턴 (0) | 2023.03.07 |