[Algorithm]정렬 알고리즘의 성능과 선택 기준: 상황에 맞는 최적의 선택

정렬은 컴퓨터 과학에서 핵심적인 작업 중 하나로, 데이터의 순서를 재조정하는 과정입니다.

이는 다양한 분야에서 중요한 역할을 수행하며, 데이터 처리와 탐색에 필수적입니다.

정렬 알고리즘은 데이터 크기, 구현 제약사항, 사용 가능한 메모리 용량 등에 따라 효율적으로 선택되어야 합니다.

이 글에서는 데이터 크기, 구현 제약사항, 메모리 사용 등을 고려하여 상황에 맞는 최적의 정렬 알고리즘을 선택하는 방법에 대해 다루고자 합니다.

 

 

 

작은 데이터 크기

---

작은 데이터에 대해서는 삽입 정렬(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;
}

 

결론:

---

정렬 알고리즘의 선택은 데이터 크기, 구현 제약사항, 사용 가능한 메모리 용량 등 다양한 요소를 고려해야 합니다. 작은 데이터 크기에는 삽입 정렬을, 대부분의 상황에는 병합 정렬을, 빠른 정렬 속도가 요구되는 경우에는 퀵 정렬을, 메모리 사용 제약이 있는 상황에는 힙 정렬을 고려할 수 있습니다. 또한 데이터의 형태나 특성에 따라 기수 정렬을 최적화로 고려할 수 있습니다. 정확한 정렬 알고리즘 선택을 위해서는 상황에 맞게 적합한 알고리즘을 선택하는 것이 중요합니다.