1. 버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 원소를 비교해 교환하며 정렬하는 알고리즘이다. 가장 큰 원소가 반복적으로 뒤로 이동하는 특성이 있다.

  • 시간 복잡도: O(n^2) (평균, 최악)
  • 장점: 구현이 간단하고, 정렬된 경우 비교 횟수가 줄어든다.

  • 단점: 데이터가 많을 경우 비효율적이다.

  • 예시: 5, 2, 9, 1을 버블 정렬로 정렬할 때, 첫 번째 패스에서 5와 2, 9와 1이 교환된다.

  • C++ 코드 예시: 
    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])  
                swap(arr[j], arr[j + 1]);  
}

2. 선택 정렬 (Selection Sort)

선택 정렬은 리스트에서 가장 작은 값을 찾아 맨 앞에 있는 값과 교환하는 작업을 반복해 정렬한다.

  • 시간 복잡도: O(n^2) (평균, 최악)
  • 장점: 코드가 단순하고 메모리 사용이 적다.

  • 단점: 성능이 느려 큰 데이터에서는 비효율적이다.

  • 예시: 4, 2, 9, 1을 선택 정렬할 때, 첫 번째 반복에서 1이 가장 작기 때문에 맨 앞으로 이동한다.

  • C++ 코드 예시: 
    void selectionSort(int arr[], int n) {  
    for (int i = 0; i < n - 1; i++) {  
        int minIdx = i;  
        for (int j = i + 1; j < n; j++)  
            if (arr[j] < arr[minIdx])  
                minIdx = j;  
        swap(arr[i], arr[minIdx]);  
    }  
}

3. 삽입 정렬 (Insertion Sort)

삽입 정렬은 정렬된 부분에 다음 원소를 삽입하며 정렬을 진행한다.

  • 시간 복잡도: O(n^2) (평균, 최악)
  • 장점: 대부분 정렬된 배열에 빠르게 작동한다.

  • 단점: 성능이 느려 큰 데이터에 비효율적이다.

  • 예시: 5, 2, 9, 1을 삽입 정렬할 때, 첫 번째 원소 5는 이미 정렬된 상태로 두고, 2를 삽입하여 재배열한다.

  • C++ 코드 예시: 
    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;  
    }  
}

4. 병합 정렬 (Merge Sort)

병합 정렬은 배열을 반으로 나누어 재귀적으로 정렬한 뒤 병합하는 방식이다.

  • 시간 복잡도: O(n log n) (최악)
  • 장점: 데이터 크기에 관계없이 안정적이다.
  • 단점: 추가 메모리를 사용해야 한다.

병합 정렬(Merge Sort)은 분할 정복 기법을 이용하여 정렬을 수행하는 알고리즘이다. 이 알고리즘은 다음과 같은 단계를 거쳐 진행된다.

  1. 분할(Divide): 주어진 배열을 반으로 나누어 두 개의 하위 배열을 만든다. 이 과정을 재귀적으로 수행하여 하위 배열이 더 이상 나눌 수 없을 때까지 계속 진행한다.

  2. 정복(Conquer): 각 하위 배열이 정렬된 상태에서 두 개의 하위 배열을 병합하여 하나의 정렬된 배열로 만든다.

  3. 결합(Combine): 두 개의 정렬된 하위 배열을 하나의 정렬된 배열로 합친다.

예시

주어진 배열이 [38, 27, 43, 3, 9, 82, 10]일 때, 병합 정렬의 흐름은 다음과 같다.

  1. 분할 단계:
    • [38, 27, 43, 3, 9, 82, 10] → [38, 27, 43]와 [3, 9, 82, 10]으로 나눈다.
    • [38, 27, 43] → [38]와 [27, 43]으로 나눈다.
    • [27, 43] → [27]와 [43]으로 나눈다.
    • [3, 9, 82, 10] → [3, 9]와 [82, 10]으로 나눈다.
    • [3, 9] → [3]와 [9]으로 나눈다.
    • [82, 10] → [82]와 [10]으로 나눈다.
  2. 정복 및 결합 단계:
    • [27]과 [43]을 병합하여 [27, 43]을 만든다.
    • [38]와 [27, 43]을 병합하여 [27, 38, 43]을 만든다.
    • [3]과 [9]을 병합하여 [3, 9]을 만든다.
    • [82]와 [10]을 병합하여 [10, 82]을 만든다.
    • [3, 9]과 [10, 82]을 병합하여 [3, 9, 10, 82]을 만든다.
    • 마지막으로, [27, 38, 43]와 [3, 9, 10, 82]을 병합하여 [3, 9, 10, 27, 38, 43, 82]을 만든다.

  • C++ 코드 예시:

    void merge(int arr[], int left, int mid, int right) {  
    int n1 = mid - left + 1, n2 = right - mid;  
    int L[n1], R[n2];  
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];  
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];  
    int i = 0, j = 0, k = left;  
    while (i < n1 && j < n2) arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];  
    while (i < n1) arr[k++] = L[i++];  
    while (j < n2) arr[k++] = R[j++];  
}  
void mergeSort(int arr[], int left, int right) {  
    if (left >= right) return;  
    int mid = left + (right - left) / 2;  
    mergeSort(arr, left, mid);  
    mergeSort(arr, mid + 1, right);  
    merge(arr, left, mid, right);  
}

5. 퀵 정렬 (Quick Sort)

퀵 정렬은 피벗을 기준으로 작은 값과 큰 값으로 나누어 재귀적으로 정렬하는 방식이다.

  • 시간 복잡도: O(n log n) (평균), O(n^2) (최악)
  • 장점: 평균적으로 빠르며 추가 메모리가 필요하지 않다.
  • 단점: 최악의 경우 비효율적이다.

퀵 정렬(Quick Sort)은 분할 정복 기법을 사용하는 효율적인 정렬 알고리즘이다. 이 알고리즘은 다음과 같은 단계를 거쳐 진행된다.

  1. 피벗 선택(Pivot Selection): 주어진 배열에서 피벗이라고 불리는 요소 하나를 선택한다. 피벗은 배열의 요소 중 하나로, 정렬 과정에서 기준점 역할을 한다.

  2. 분할(Partitioning): 배열의 요소들을 피벗을 기준으로 두 개의 하위 배열로 나눈다. 피벗보다 작은 요소들은 왼쪽 배열로, 큰 요소들은 오른쪽 배열로 이동한다.

  3. 재귀 호출(Recursive Calls): 왼쪽과 오른쪽의 하위 배열에 대해 재귀적으로 퀵 정렬을 수행한다.

  4. 결합(Combining): 모든 재귀 호출이 완료되면, 정렬된 배열이 생성된다.

예시

주어진 배열이 [38, 27, 43, 3, 9, 82, 10]일 때, 퀵 정렬의 흐름은 다음과 같다.

  1. 피벗 선택:
    • 배열의 첫 번째 요소인 38을 피벗으로 선택한다.
  2. 분할:
    • 38보다 작은 요소는 [27, 3, 9, 10]이고, 큰 요소는 [43, 82]이다.
    • 분할된 결과는 [27, 3, 9, 10] (피벗보다 작은 부분) + [38] (피벗) + [43, 82] (피벗보다 큰 부분)이다.
  3. 재귀 호출:
    • 왼쪽 배열 [27, 3, 9, 10]에 대해 퀵 정렬을 수행한다. 여기서 27을 피벗으로 선택하고, 다시 분할한다.
      • 27보다 작은 요소는 [3, 9, 10], 큰 요소는 없다.
    • 분할된 결과는 [3, 9, 10] + [27]이다.
    • [3, 9, 10]에 대해 퀵 정렬을 수행하면, 3을 피벗으로 선택하고 다시 분할한다.
      • 3보다 작은 요소는 없고, 큰 요소는 [9, 10]이다.
    • 결과는 [3] + [9, 10]이다.
    • [9, 10]에 대해 퀵 정렬을 수행하면, 9을 피벗으로 선택하고 결과는 [9] + [10]이 된다.
    • 최종적으로 왼쪽 배열은 [3, 9, 10, 27]이 된다.
  4. 오른쪽 배열 정렬:
    • 오른쪽 배열 [43, 82]는 피벗 43으로 분할되어 [43] + [82]로 결과가 정렬된다.

모든 재귀 호출이 완료된 후, 최종적으로 정렬된 배열은 [3, 9, 10, 27, 38, 43, 82]이다.

  • C++ 코드 예시: 
    int partition(int arr[], int low, int high) {  
    int pivot = arr[high];  
    int i = (low - 1);  
    for (int j = low; j <= high - 1; j++) {  
        if (arr[j] <= pivot) swap(arr[++i], arr[j]);  
    }  
    swap(arr[i + 1], arr[high]);  
    return (i + 1);  
}  
void quickSort(int arr[], int low, int high) {  
    if (low < high) {  
        int pi = partition(arr, low, high);  
        quickSort(arr, low, pi - 1);  
        quickSort(arr, pi + 1, high);  
    }  
}

6. 힙 정렬 (Heap Sort)

힙 정렬은 최대 힙이나 최소 힙을 구성한 뒤, 루트 값을 제거하면서 정렬한다.

  • 시간 복잡도: O(n log n) (평균, 최악)
  • 장점: 추가 메모리가 필요하지 않다.
  • 단점: 힙 구성에 시간이 걸린다.

힙 정렬(Heap Sort)은 완전 이진 트리 형태인 힙(Heap) 자료구조를 이용하여 정렬을 수행하는 알고리즘이다. 이 알고리즘은 다음과 같은 단계를 거쳐 진행된다.

  1. 힙 구성(Build Heap): 주어진 배열을 힙 구조로 변환한다. 일반적으로 최대 힙(Max Heap)을 사용하며, 최대 힙은 부모 노드가 자식 노드보다 크거나 같은 구조를 가진다.

  2. 최대 원소 추출(Remove Max): 배열의 첫 번째 원소(최대 원소)를 추출하고 배열의 마지막 원소와 교환한 후, 나머지 원소에 대해 힙 구조를 유지한다.

  3. 재구성(Heapify): 교환 후 남은 원소에 대해 힙을 재구성하여 다시 최대 힙 구조를 유지하도록 한다.

  4. 반복: 이 과정을 남아 있는 원소가 없을 때까지 반복하여 정렬된 배열을 얻는다.

예시

주어진 배열이 [38, 27, 43, 3, 9, 82, 10]일 때, 힙 정렬의 흐름은 다음과 같다.

  1. 힙 구성:
    • 주어진 배열을 최대 힙으로 변환한다.
    • 결과적인 최대 힙은 다음과 같다: 
            82
    /    \
  38      43
 /  \    /  \
3    9  10   27
    • 이때, 배열 표현은 [82, 38, 43, 3, 9, 10, 27]이다.
  2. 최대 원소 추출:
    • 최대 원소인 82를 배열의 마지막 원소와 교환한다.
    • 교환 후 배열은 [27, 38, 43, 3, 9, 10, 82]가 된다.
  3. 재구성(Heapify):
    • 남아 있는 원소들에 대해 최대 힙을 재구성한다.
    • 결과적으로 [43, 38, 27, 3, 9, 10] 형태의 최대 힙이 된다.
  4. 반복:
    • 최대 원소 43을 추출하여 [10, 38, 27, 3, 9, 43, 82]로 만들고, 다시 힙 재구성하여 [38, 10, 27, 3, 9]이 된다.
    • 계속해서 38, 27, 10, 9, 3을 차례로 추출하여 정렬한다.

모든 과정을 마친 후, 정렬된 배열은 [3, 9, 10, 27, 38, 43, 82]가 된다.

  • C++ 코드 예시: 
    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) {  
        swap(arr[i], arr[largest]);  
        heapify(arr, n, largest);  
    }  
}  
void heapSort(int arr[], int n) {  
    for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);  
    for (int i = n - 1; i > 0; i--) {  
        swap(arr[0], arr[i]);  
        heapify(arr, i, 0);  
    }  
}

7. 기수 정렬 (Radix Sort)

기수 정렬은 자릿수를 기준으로 정렬하여 큰 숫자도 처리할 수 있는 알고리즘이다.

  • 시간 복잡도: O(d*(n + k)) (d는 자릿수, k는 자릿수 범위)
  • 장점: 특정 데이터 집합에서 빠르다.
  • 단점: 자릿수 처리에 제약이 있다.

기수 정렬(Radix Sort)은 숫자를 자릿수 단위로 분리하여 정렬하는 알고리즘이다. 주로 정수나 문자열과 같은 고정된 길이의 데이터를 정렬하는 데 사용된다. 기수 정렬은 안정적인 정렬 알고리즘으로, 다음과 같은 단계를 거쳐 진행된다.

  1. 최대 자릿수 계산: 주어진 배열에서 가장 큰 숫자를 찾아 그 숫자의 자릿수를 계산한다.

  2. 자릿수별 정렬: 각 자릿수(1의 자리, 10의 자리 등)에 대해 개별적으로 정렬을 수행한다. 일반적으로 가장 낮은 자릿수부터 시작하여 높은 자릿수로 진행한다. 이때 계수 정렬(Counting Sort)을 사용하여 각 자릿수를 정렬한다.

  3. 반복: 모든 자릿수에 대해 정렬을 완료할 때까지 반복한다.

예시

주어진 배열이 [170, 45, 75, 90, 802, 24, 2]일 때, 기수 정렬의 흐름은 다음과 같다.

  1. 최대 자릿수 계산:
    • 주어진 배열에서 최대값은 802이며, 이 숫자는 3자리이다. 따라서 1의 자리, 10의 자리, 100의 자리 순으로 정렬한다.
  2. 자릿수별 정렬:
    • 1의 자리 정렬:
      • 배열을 1의 자리 기준으로 정렬하면 [170, 90, 802, 24, 45, 75, 2]가 된다.
    • 10의 자리 정렬:
      • 배열을 10의 자리 기준으로 정렬하면 [170, 802, 24, 45, 2, 75, 90]가 된다.
    • 100의 자리 정렬:
      • 배열을 100의 자리 기준으로 정렬하면 [2, 24, 45, 75, 90, 170, 802]가 된다.
  3. 최종 결과: 모든 자릿수 정렬이 완료된 후, 최종적으로 정렬된 배열은 [2, 24, 45, 75, 90, 170, 802]가 된다.

  • C++ 코드 예시:

    void countingSort(int arr[], int n, int exp) {  
    int output[n], count[10] = {0};  
    for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;  
    for (int i = 1; i < 10; i++) count[i] += count[i - 1];  
    for (int i = n - 1; i >= 0; i--) {  
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];  
        count[(arr[i] / exp) % 10]--;  
    }  
    for (int i = 0; i < n; i++) arr[i] = output[i];  
}  
void radixSort(int arr[], int n) {  
    int max = *max_element(arr, arr + n);  
    for (int exp = 1; max / exp > 0; exp *= 10)  
        countingSort(arr, n, exp);  
}

이와 같은 정렬 알고리즘들은 각각 장단점과 다양한 시간 복잡도를 가지고 있다. 데이터의 성질과 크기에 따라 적합한 알고리즘을 선택하는 것이 중요하다.