[c++] 큐정렬

12 Dec 2023

큐 정렬은 큐 자료 구조를 사용하여 정렬하는 알고리즘입니다. 큐는 FIFO(First In First Out) 구조로 데이터를 저장하고, 정렬을 위해 적합한 알고리즘이 아닙니다. 하지만 큐를 사용하여 정렬하는 것은 다른 정렬 알고리즘을 통해 큐를 구현하는 방식을 이해하는 데 도움이 됩니다.

큐 정렬 알고리즘

큐에 저장된 데이터 중 최솟값을 찾습니다.
해당 최솟값을 큐에서 제거하고, 다른 큐에 추가합니다.
이러한 과정을 반복하여 최종적으로 오름차순으로 정렬된 큐를 얻습니다.

#include <iostream>
#include <queue>
#include <algorithm>

void queueSort(std::queue<int>& q) {
    int n = q.size();
    for (int i = 0; i < n; i++) {
        int min_element = INT_MAX;
        for (int j = 0; j < n - i; j++) {
            int front_element = q.front();
            q.pop();
            min_element = std::min(min_element, front_element);
            q.push(front_element);
        }
        for (int j = 0; j < n - i; j++) {
            int front_element = q.front();
            q.pop();
            if (front_element != min_element) {
                q.push(front_element);
            }
        }
        q.push(min_element);
    }
}

int main() {
    std::queue<int> q;
    q.push(5);
    q.push(3);
    q.push(8);
    q.push(1);
    q.push(2);

    queueSort(q);

    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }

    return 0;
}

큐 정렬의 시간 복잡도

최악의 경우: O(n^2)
평균적으로: O(n^2)
최선의 경우: O(n^2)

결론

큐 정렬은 정렬 알고리즘 중에서 효율적이지 않은 알고리즘입니다. 따라서 실제로 사용되는 정렬 알고리즘으로는 병합 정렬, 퀵 정렬, 힙 정렬 등이 있으며, 큐를 사용한 정렬은 학습 목적으로 이해하는 데 적합합니다.

예시 코드 출처: GeeksforGeeks