[LeetCode] 912. Sort an Array

https://leetcode.com/problems/sort-an-array/description/

leetcode - Sort an Array

문제 유형 : 정렬, 투포인터

문제 난이도 : Medium

 

문제

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

 

정수 배열 nums가 주어진다. 오름차순으로 순서를 정렬하고 반환하시오.

아무런 built-in 함수도 사용하면 안되고, O(nlog(n))의 복잡도로 끝내시오. 공간도 최소한으로 사용하시오.

 

풀이

in-place의 공간을 사용하는 퀵 정렬을 구현해보았다.

left와 right를 처음에 각각 0과 n-1로 하고,

재귀적으로 다음을 수행한다:

중앙에 있는 값을 pivot으로 정한다. 

 

i는 left부터 시작하는데, nums[i]가 pivot보다 작은동안 i를 증가시킨다.

j는 right부터 시작하는데, nums[j]가 pivot보다 큰 동안 j를 감소시킨다.

이제 nums[i]와 nums[j]는 pivot보다 각각 크거나 같거나, 작거나 같은데,
만약 i가 j보다 작거나 같으면, nums[i]와 nums[j]를 교환하고 인덱스를 각각 1씩 증가 및 감소시키면 된다.

이를 i <= j인동안 반복하면 된다.

 

이제 left ~ j는 pivot보다 작은 수들의 범위, i ~ right은 pivot보다 큰 수의 범위가 된다.

이 범위들로 각각 재귀호출하여 일부분만 정렬해주면 된다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    void quicksort(vector<int>& nums, int left, int right) {
        if(left >= right) return;
        int mid = (left + right)/2;
        int pivot = nums[mid];
        int i = left;
        int j = right;

        while(i <= j) {
            while(nums[i] < pivot) i++;
            while(nums[j] > pivot) j--;
            if(i <= j) {
                swap(nums[i], nums[j]);
                i++;
                j--;
            }
        }

        quicksort(nums, left, j);
        quicksort(nums, i, right);
    }

    vector<int> sortArray(vector<int>& nums) {
        quicksort(nums, 0, nums.size()-1);
        return nums;
    }
};