22.1. 프로그램언어 C++에서의 정렬 알고리즘

by

프로그램언어 C++의 버블 정렬

C++의 버블 정렬은 인접한 두 원소를 비교하여 정렬하는 간단한 정렬 알고리즘입니다. 이 알고리즘은 원소들을 서로 교환하면서 정렬을 수행하며, 가장 큰(또는 작은) 원소가 배열의 가장 끝으로 이동하는 방식으로 동작합니다.

아래는 C++로 구현된 버블 정렬의 예제 코드입니다. 이 코드는 정수형 배열을 버블 정렬하여 오름차순으로 정렬하는 기능을 수행합니다. 


#include <iostream>

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;
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    bubbleSort(arr, n);
    
    std::cout << "정렬된 배열: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    
    return 0;
}

프로그램언어 C++의 선택 정렬

선택 정렬(Selection Sort)은 가장 작은(또는 큰) 원소를 선택하여 정렬하는 알고리즘입니다. 이 알고리즘은 간단하고 이해하기 쉽지만, 효율성 면에서는 다른 정렬 알고리즘에 비해 느린 편에 속합니다.

선택 정렬의 동작 방식은 다음과 같습니다. 주어진 배열에서 가장 작은 원소를 찾아 첫 번째 위치와 교환합니다. 그 다음으로 두 번째로 작은 원소를 찾아 두 번째 위치와 교환하는 과정을 반복하여 정렬을 완성합니다.

아래는 C++로 구현된 선택 정렬의 예제 코드입니다. 


#include <iostream>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIndex = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 가장 작은 원소와 현재 위치의 원소 교환
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    selectionSort(arr, n);
    
    std::cout << "정렬된 배열: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    
    return 0;
}

프로그램언어 C++의 삽입 정렐

C++의 삽입 정렬은 간단하면서도 효율적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 배열을 정렬할 때 사용되며, 각 원소를 이미 정렬된 부분 배열에 삽입하는 방식으로 동작합니다. 삽입 정렬은 원소의 개수가 적을 때 효율적이며, 이미 정렬된 상태에서는 빠르게 동작합니다.

삽입 정렬의 동작 방식은 다음과 같습니다:

  1. 첫 번째 원소는 이미 정렬된 것으로 간주합니다.
  2. 두 번째 원소부터 시작하여, 해당 원소를 이미 정렬된 부분 배열의 올바른 위치에 삽입합니다.
  3. 정렬된 부분 배열의 크기를 늘려가며 모든 원소가 정렬될 때까지 반복합니다.

아래는 C++로 구현된 삽입 정렬의 예제 코드입니다:


#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

프로그램언어 C++의 퀵 정렬

퀵 정렬(Quick Sort)은 프로그램언어 C++에서 사용되는 효율적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 분할 정복(Divide and Conquer) 방법을 사용하여 배열을 정렬합니다. 퀵 정렬은 평균적으로 매우 빠른 속도를 보이며, 많은 정렬 알고리즘 중에서도 성능이 우수한 편에 속합니다.

퀵 정렬은 다음과 같은 단계로 진행됩니다:

  1. 리스트에서 하나의 원소를 선택하여 pivot으로 정합니다.
  2. 피벗을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 분할합니다.
  3. 분할된 부분 리스트에 대해 재귀적으로 퀵 정렬을 수행합니다.
  4. 부분 리스트의 크기가 1 이하가 될 때까지 반복합니다.

아래는 C++로 구현된 퀵 정렬의 예제 코드입니다:


#include <iostream>
#include <vector>

void quickSort(std::vector& arr, int left, int right) {
    if (left >= right) {
        return;
    }
    
    int pivot = arr[(left + right) / 2];
    int i = left, j = right;
    
    while (i <= j) {
        while (arr[i] < pivot) {
            i++;
        }
        while (arr[j] > pivot) {
            j--;
        }
        if (i <= j) {
            std::swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
    
    quickSort(arr, left, j);
    quickSort(arr, i, right);
}

int main() {
    std::vector arr = {5, 2, 9, 3, 7, 6, 1, 8, 4};
    
    quickSort(arr, 0, arr.size() - 1);
    
    for (int num : arr) {
        std::cout << num << " ";
    }
    
    return 0;
}

프로그램언어 C++의 병합 정렬

병합 정렬(merge sort)은 분할 정복(divide and conquer) 알고리즘 중 하나로, 리스트를 반으로 나눈 뒤 각각을 재귀적으로 정렬하고 다시 합치는 방식으로 동작합니다. 이를 통해 리스트를 정렬하는 효율적인 방법 중 하나입니다.

아래는 C++로 구현된 병합 정렬의 예제 코드입니다. 코드에서는 리스트를 반으로 나누고, 각각을 정렬한 뒤 병합하는 과정을 보여줍니다. 


#include <iostream>
#include <vector>

void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    std::vector<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) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    int arrSize = arr.size();

    mergeSort(arr, 0, arrSize - 1);

    for (int num : arr) {
        std::cout << num << " ";
    }

    return 0;
}

Leave a Comment