Leetcode - 912. Sort an Array

문제

주어진 배열을 정렬하라. 단 내장 정렬함수는 사용할 수 없다.

아이디어

merge sort와 quick sort는 구조적으로 유사한 부분이 있다. 머지소트는 핵심로직인 merge()를 두 재귀함수가 호출된 뒤 마지막에하고, quick sort는 핵심 로직인 partitioning을 두 재귀함수가 호출하기 직전에 수행한다.

mergesort() :
	mergesort() <- 재귀
    mergesort() <- 재귀
    merge()

quicksort()
	partition()
    quicksort() <- 재귀
    quicksort() <- 재귀

merge sort와 quick sort는 코드를 외우자

해결 merge sort

merge sort는 절반으로 계속해서 나누는 재귀함수 파트

그리고 다시 merge하는 동작 두가지로 나뉘어있다.

merge 동작은 합치면서 정렬( 작은값부터 배열에 넣으면) 된다. 합치기 전의 배열은 이미 정렬되어있는 상태이기 때문에, 앞에서부터 비교하며 정렬된 배열로 합칠 수 있다.

merge 동작
8  1   5  3   6  7   9  4
  |     |       |      |
[1,8]  [3,5]  [6,7]  [4,9]
      |             |
 [1,3,8,5]      [4,6,7,9]
             |
      [1,3,4,5,6,7,8,9]

class Solution {

    void merge(vector<int> &nums, int left, int right, int mid) {
        vector<int> sorted(right - left + 1, 0);
        int l = left;
        int r = mid + 1;
        int i = 0;

        while (l <= mid && r <= right)
            sorted[i++] = (nums[l] < nums[r]) ? nums[l++] : nums[r++];
        // push all right remeins
        while (r <= right)
            sorted[i++] = nums[r++];
        // push all left remeins
        while (l <= mid)
            sorted[i++] = nums[l++];
        for (auto it: sorted) {
            nums[left++] = it;
        }
    }


    void mergesort(vector<int> &nums, int left, int right) {
        if (left >= right)
            return;
        int mid = left + (right - left) / 2;
        mergesort(nums, left, mid);
        mergesort(nums,  mid + 1, right);
        merge(nums, left, right, mid);
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        mergesort(nums, 0, nums.size() - 1);
        return nums;
    }
};

해결 quick sort

퀵소트의 partition() 알고리즘은 여러개가 될 수 있는데, 결론적으로 나는 아래의 알고리즘이 외우기 쉽고 구현이 까다롭지 않아서 앞으로 사용하려고 한다. 참고로 주의할 사항은 재귀함수 호출할 때 left right인자로 (left, pivot - 1) 그리고 (pivot, right) 를 전달해야한다는 사실이다. (이걸 잘못 구현해서 디버깅하느라 고생함)

class Solution {
public:
    int partition(vector<int> &nums, int left, int right) {
        int pv = nums[left + (right - left) / 2];
        while (left <= right) { // if left and right crossed, the roop will be terminated.
            // find swap target from left & right index
            while (nums[left] < pv) left++; 
            while (nums[right] > pv) right--;
            // at this point, left and right can be swaped
            if (left <= right)
                std::swap(nums[left++], nums[right--]);
        }
        return left; // the return value will be the first index of the right side
    }
    void quick_sort(vector<int>& nums, int left, int right) {
        /* base case */
        if (left >= right) 
            return;

        int pivot = partition(nums, left, right);
        /* recursion */
        // the ranges must be (left,pivot-1) and (pivot, right)
        quick_sort(nums, left, pivot - 1); // ~ pivot-1
        quick_sort(nums,  pivot, right);  // pivot ~
    }
    vector<int> sortArray(vector<int>& nums) {
       quick_sort(nums, 0, nums.size() - 1);
       return nums; 
    }
};

또다른 파티셔닝 알고리즘으로는 아래와 같은 코드가 있다. 비교 대상 요소를 배열의 맨앞으로 놓고 파티셔닝 진행후 위치를 복귀하는 방식. (그런데 TLE)

class Solution {
public:
    void swap(vector<int> &nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }

    int partition_2(vector<int> &nums, int left, int right) {
        int pivot = left;
        swap(nums, left, left + (right - left) / 2);
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < nums[left])
                swap(nums, ++pivot, i);
        }
        swap(nums, left, pivot);
        return pivot;
    }

    void quick_sort(vector<int> &nums, int left, int right) {
        if (left >= right)
            return;
        int pivot = partition_2(nums, left, right);
        quick_sort(nums, left, pivot-1);
        quick_sort(nums, pivot+1, right);
    }
    vector<int> sortArray(vector<int>& nums) {
        quick_sort(nums, 0, nums.size() - 1);
        return nums;
    }
};