[c++] 배열과 포인터를 사용한 정렬 알고리즘의 시간 복잡도

14 Dec 2023

배열과 포인터를 사용한 정렬 알고리즘은 데이터를 효율적으로 정렬하는 데에 사용됩니다. 정렬 알고리즘의 시간 복잡도는 알고리즘의 성능을 이해하는 데 중요한 요소입니다. 아래에서는 배열과 포인터를 사용한 일부 정렬 알고리즘의 시간 복잡도에 대해 설명하겠습니다.

버블 정렬 (Bubble Sort)

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

시간 복잡도: O(n^2)

선택 정렬 (Selection Sort)

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_index = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min_index];
        arr[min_index] = temp;
    }
}

시간 복잡도: O(n^2)

삽입 정렬 (Insertion Sort)

void insertionSort(int arr[], int n) {
    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--;
        }
        arr[j+1] = key;
    }
}

시간 복잡도: O(n^2)

요약

배열과 포인터를 사용한 정렬 알고리즘의 시간 복잡도는 주로 O(n^2)입니다. 이는 데이터 크기가 커질수록 알고리즘의 실행 시간이 크게 증가할 수 있음을 의미합니다. 그러나 정렬 알고리즘의 선택은 애플리케이션의 요구에 따라 달라지며, 정확한 사용 사례에 맞는 알고리즘을 선택하는 것이 중요합니다.

참고 문헌

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.