C++에서 배열을 오름차순으로 정렬하는 방법

정수로 이루어진 배열이 주어졌을 때, 이를 오름차순으로 정렬하는 것이 목표입니다. 예를 들어 배열이 [5,2,3,1]이라면, 정렬 후 결과는 [1,2,3,5]가 되어야 합니다.

이 문제는 대표적인 분할 정복(divide and conquer) 알고리즘인 퀵 정렬(Quick Sort)을 사용하면 효율적으로 해결할 수 있습니다. 퀵 정렬은 하나의 기준값인 피벗(pivot)을 정한 뒤, 그보다 작은 값들은 왼쪽에 큰 값들은 오른쪽에 배치하고, 나뉜 각 영역을 재귀적으로 정렬하는 방식으로 동작합니다.

문제 해결 절차

다음 단계를 따라 구현할 수 있습니다.

배열과 low, high 인덱스를 매개변수로 받는 partition() 메서드를 작성합니다.
pivot 값을 low로 설정합니다.
i가 low부터 high − 1까지 순회하면서 다음을 검사합니다.
- 만약 nums[i] < nums[high]라면, nums[i]와 nums[pivot]을 교환(swap)하고 pivot을 1 증가시킵니다.
순회가 끝나면 nums[pivot]과 nums[high]를 교환합니다. 이때 pivot 위치의 요소는 자신의 최종 정렬 위치에 확정됩니다.
마찬가지로 배열과 low, high를 받는 sortArr() 메서드를 정의합니다.
low >= high라면 정렬할 요소가 남아 있지 않으므로 함수를 종료(return)합니다.
partitionIndex := partition(nums, low, high)를 호출해 피벗의 최종 위치를 구합니다.
sortArr(nums, low, partitionIndex − 1)로 피벗 왼쪽 영역을 재귀적으로 정렬합니다.
sortArr(nums, partitionIndex + 1, high)로 피벗 오른쪽 영역을 재귀적으로 정렬합니다.
main 메서드에서 sortArr()를 호출할 때 low에는 0, high에는 (배열 크기 − 1)을 전달하여 전체 배열을 정렬합니다.

아래 예제 코드를 통해 실제 동작 과정을 더 잘 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<string> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    int partition(vector <int>& nums, int low, int high){
       int pivot = low;
       for(int i = low; i < high; i++){
          if(nums[i] < nums[high]){
             swap(nums[i], nums[pivot]);
             pivot++;
          }
       }
       swap(nums[pivot], nums[high]);
       return pivot;
    }
    void sortArr(vector <int>& nums, int low, int high){
       if(low >= high) return;
       int partitionIndex = partition(nums, low, high);
       sortArr(nums, low, partitionIndex - 1);
       sortArr(nums, partitionIndex + 1, high);
    }
    vector<int> sortArray(vector<int>& nums) {
       sortArr(nums, 0, nums.size() - 1);
       return nums;
    }
};
main(){
    vector<int> v1 = {5,2,3,1};
    Solution ob;
    print_vector(ob.sortArray(v1));
}

입력

[5,2,3,1]

출력

[1,2,3,5]

시간 복잡도와 특징

위 코드는 Lomuto 파티션 방식을 사용한 퀵 정렬입니다. 평균 시간 복잡도는 O(n log n)으로 매우 빠르지만, 이미 정렬되어 있는 배열처럼 피벗 선택이 불균형해지는 경우에는 최악의 성능인 O(n²)까지 저하될 수 있습니다. 또한 재귀 호출 스택을 사용하기 때문에 평균적인 추가 공간 복잡도는 O(log n)입니다.

C++에서 배열을 오름차순으로 정렬하는 방법 — 퀵 정렬(Quick Sort) 구현

문제 해결 절차

예제 코드

입력

출력

시간 복잡도와 특징