정렬은 컴퓨터 과학에서 핵심적인 작업 중 하나로, 데이터의 순서를 재조정하는 과정입니다.
이는 다양한 분야에서 중요한 역할을 수행하며, 데이터 처리와 탐색에 필수적입니다.
정렬 알고리즘은 데이터 크기, 구현 제약사항, 사용 가능한 메모리 용량 등에 따라 효율적으로 선택되어야 합니다.
이 글에서는 데이터 크기, 구현 제약사항, 메모리 사용 등을 고려하여 상황에 맞는 최적의 정렬 알고리즘을 선택하는 방법에 대해 다루고자 합니다.
작은 데이터 크기
작은 데이터에 대해서는 삽입 정렬(Insertion Sort)이 효율적입니다. 추가적인 메모리 사용 없이 구현이 간단하며, 데이터 크기에 민감하지 않습니다.
Insertion Sort 시간 복잡도 :
- 최선의 경우 : O(n)
- 평균 및 최악의 경우: O(n^2)
예시 코드
public void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
대부분의 상황:
병합 정렬(Merge Sort)은 대부분의 상황에서 효율적입니다. 안정적인 정렬을 보장하며, 추가적인 메모리 사용에 큰 제약이 없습니다. 데이터 크기에 민감하지 않아 일반적인 정렬 작업에 적합합니다.
Merge Srot 시간 복잡도 :
- 최선, 평균, 최악의 경우: O(n log n)
예시 코드
public class MergeSort {
public static void main(String[] args) {
int[] array = {5, 2, 8, 6, 1, 9, 3, 7, 4};
System.out.println("Before sorting : " + Arrays.toString(array));
mergeSort(array);
System.out.println("After sorting: " + Arrays.toString(array));
}
static void mergeSort(int[] array) {
if (array == null || array.length <= 1) {
return; // 배열이 비어있거나 원소가 하나 이하인 경우 정렬할 필요가 없으므로 종료
}
int[] tempArray = new int[array.length];
mergeSort(array, tempArray, 0, array.length - 1);
}
static void mergeSort(int[] array, int[] tempArray, int left, int right) {
if (left < right) {
int mid = (left + right) / 2; // 중간 인덱스 계산
mergeSort(array, tempArray, left, mid); // 왼쪽 부분 배열 정렬
mergeSort(array, tempArray, mid + 1, right); // 오른쪽 부분 배열 정렬
merge(array, tempArray, left, mid, right); // 정렬된 두 부분 배열 병합
}
}
static void merge(int[] array, int[] tempArray, int left, int mid, int right) {
// 두 부분 배열의 시작 인덱스 설정
int leftStart = left;
int rightStart = mid + 1;
int tempIndex = left; // 임시 배열의 인덱스
// 두 부분 배여을 비교하여 적은 값을 임시 배열에 병함
while (leftStart <= mid && rightStart <= right) {
if (array[leftStart] <= array[rightStart]) {
tempArray[tempIndex] = array[leftStart];
leftStart++;
} else {
tempArray[tempIndex] = array[rightStart];
rightStart++;
}
tempIndex++;
}
// 왼쪽 부분 배열의 나머지 원소를 임시 배열에 복사
while (leftStart <= mid) {
tempArray[tempIndex] = array[leftStart];
leftStart++;
tempIndex++;
}
// 오른쪽 부분 배열의 나머지 원소를 임시 배열에 복사
while (rightStart <= right) {
tempArray[tempIndex] = array[rightStart];
rightStart++;
tempIndex++;
}
// 임시 배열의 내용을 원래 배열에 복사
for (int i = left; i <= right; i++) {
array[i] = tempArray[i];
}
}
}
빠른 정렬 속도가 요구되는 경우:
퀵 정렬(Quick Sort)은 평균적으로 매우 빠른 실행 속도를 가지는 알고리즘입니다. 추가적인 메모리 사용이 가능하다면 효율적으로 동작하며, 정렬 속도가 중요한 상황에서 선택할 수 있습니다.
Quick Sort 시간 복잡도 :
- 평균 및 최선의 경우: O(n log n)
- 최악의 경우: O(n^2) - 피벗 선택에 따라 달라질 수 있으며, 최악의 경우에는 피벗이 항상 최솟값이나 최댓값으로 선택될 때 발생합니다.
예시 코드
public class QuickSort {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] numbers = new int[N];
for (int i = 0; i < N; i++) {
int num = Integer.parseInt(br.readLine());
if (!contains(numbers, i, num)) {
numbers[i] = num;
}
}
br.close();
numbers = Arrays.copyOf(numbers, N); // 중복을 제거한 배열의 크기로 재조정
quickSort(numbers, 0, numbers.length - 1);
for (int num : numbers) {
if (num != 0) {
System.out.println(num);
}
}
}
private static boolean contains(int[] arr, int length, int target) {
for (int i = 0; i < length; i++) {
if (arr[i] == target) {
return true;
}
}
return false;
}
private static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
메모리 사용 제약이 있는 경우:
메모리 사용이 제한된 상황에서는 힙 정렬(Heap Sort)을 고려할 수 있습니다. 추가적인 메모리 사용을 최소화하며, 안정적인 정렬을 보장합니다.
Heap Sort 시간 복잡도:
- 최선, 평균, 최악의 경우: O(n log n)
예시 코드
public void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
public void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
특정한 상황에 따른 최적화:
데이터가 특정한 형태로 표현되어 있는 경우에는 기수 정렬(Radix Sort)이 효율적일 수 있습니다. 데이터 크기에 민감하지 않고, 비교 연산을 사용하지 않으며 정렬을 수행합니다.
Radix Sort :
- 최선, 평균, 최악의 경우 : O(d*(n+k))
(d: 최대 자릿수, n: 데이터 개수, k : 각 자릿수의 가능한 값의 개수)
예시 코드
public void radixSort(int[] arr) {
int max = getMax(arr);
int digitPlace = 1;
int n = arr.length;
int[] sortedArray = new int[n];
while (max / digitPlace > 0) {
int[] count = new int[10];
for (int i = 0; i < n; i++)
count[(arr[i] / digitPlace) % 10]++;
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
sortedArray[count[(arr[i] / digitPlace) % 10] - 1] = arr[i];
count[(arr[i] / digitPlace) % 10]--;
}
System.arraycopy(sortedArray, 0, arr, 0, n);
digitPlace *= 10;
}
}
public int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
결론:
정렬 알고리즘의 선택은 데이터 크기, 구현 제약사항, 사용 가능한 메모리 용량 등 다양한 요소를 고려해야 합니다. 작은 데이터 크기에는 삽입 정렬을, 대부분의 상황에는 병합 정렬을, 빠른 정렬 속도가 요구되는 경우에는 퀵 정렬을, 메모리 사용 제약이 있는 상황에는 힙 정렬을 고려할 수 있습니다. 또한 데이터의 형태나 특성에 따라 기수 정렬을 최적화로 고려할 수 있습니다. 정확한 정렬 알고리즘 선택을 위해서는 상황에 맞게 적합한 알고리즘을 선택하는 것이 중요합니다.
'Algorithm' 카테고리의 다른 글
| 백준 2751번 수 정렬하기 2 (0) | 2023.06.26 |
|---|---|
| [알고리즘] Backtracking(백트래킹) (0) | 2023.06.23 |
| 알파벳 전체를 포함하는 String[] 배열 만들기 - 자바(JAVA) (0) | 2023.06.16 |
| 백준 1157 번 (단어공부) - 자바(JAVA) (0) | 2023.06.15 |
| 백준 9095 문제 (순열을 이용한 풀이 및 dp 풀이) - 자바(JAVA) (0) | 2023.06.14 |