[C++로 배우는 알고리즘과 자료구조] Day 16: 버블 정렬과 선택 정렬

버블 정렬 (Bubble Sort)

버블 정렬은 가장 간단한 정렬 알고리즘 중 하나로, 인접한 두 요소를 비교하여 필요에 따라 자리를 바꾸면서 배열을 정렬합니다. 배열의 끝까지 이 과정을 반복하면 가장 큰 값이 맨 끝에 위치하게 됩니다. 이 과정을 여러 번 반복하여 배열이 정렬될 때까지 진행합니다.

버블 정렬의 시간 복잡도:

• 최선의 경우: (O(n))
• 평균의 경우: (O(n^2))
• 최악의 경우: (O(n^2))

버블 정렬 구현

#include <iostream>
#include <vector>

// 버블 정렬 함수
void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]); // 인접한 두 요소 교환
            }
        }
    }
}

int main() {
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};

    std::cout << "정렬 전 배열: ";
    for (int value : arr) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    bubbleSort(arr);

    std::cout << "정렬 후 배열: ";
    for (int value : arr) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

선택 정렬 (Selection Sort)

선택 정렬은 배열에서 가장 작은 요소를 찾아 첫 번째 위치와 교환하는 과정을 반복하여 배열을 정렬합니다. 이 과정을 배열의 모든 요소에 대해 반복하여 정렬을 완료합니다.

선택 정렬의 시간 복잡도:

• 최선의 경우: (O(n^2))
• 평균의 경우: (O(n^2))
• 최악의 경우: (O(n^2))

선택 정렬 구현

#include <iostream>
#include <vector>

// 선택 정렬 함수
void selectionSort(std::vector<int>& arr) {
    int n = arr.size();
    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; // 가장 작은 요소의 인덱스 찾기
            }
        }
        std::swap(arr[i], arr[minIndex]); // 가장 작은 요소를 첫 번째 위치로 이동
    }
}

int main() {
    std::vector<int> arr = {64, 25, 12, 22, 11};

    std::cout << "정렬 전 배열: ";
    for (int value : arr) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    selectionSort(arr);

    std::cout << "정렬 후 배열: ";
    for (int value : arr) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    return 0;
}

설명

1. 버블 정렬 (Bubble Sort):
   • 인접한 두 요소를 비교하여 정렬합니다.
   • 최선의 경우 시간 복잡도는 (O(n))이고, 평균 및 최악의 경우 시간 복잡도는 (O(n^2))입니다.
2. 선택 정렬 (Selection Sort):
   • 리스트에서 가장 작은 요소를 찾아 첫 번째 위치와 교환하는 과정을 반복합니다.
   • 모든 경우에 시간 복잡도는 (O(n^2))입니다.

버블 정렬과 선택 정렬의 기본 개념과 구현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 정렬 알고리즘과 다양한 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 17: 삽입 정렬과 쉘 정렬"에 대해 학습하겠습니다.