[leet_code] 915. 랜덤피벗과 호어분할을 이용한 퀵정렬(quick sort) 개선

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

Sort an Array - LeetCode

 

NLogN의 시간복잡도를 가지는 여러 정렬 알고리즘을 테스트할 수 있는 문제이다.이 중 퀵소트를 테스트하는 도중 시간제한에 걸려 실패하는 케이스를 경험하였다.편향된 분할이 발생할 경우 N^2까지 시간복잡도가 떨어지는 케이스가 존재하기 때문인데 이를 보완하기 위해서는 추가적인 코드가 필요하다.

 

아래는 처음 작성한 정석적인 퀵 소트 코드이다.

auto quick_sort(int32_t start_idx, int32_t end_idx, arr_t& arr) -> void
{
	if (end_idx <= start_idx) { return; }

	int32_t key = arr[start_idx];
	int32_t i = start_idx + 1;	// index for find integer smaller than the key value
	int32_t j = end_idx;		// index for find integer bigger the key value 

	while (true)
	{
		while (i <= end_idx && arr[i] <= key) ++i;
        while (j > start_idx && arr[j] >= key) --j;

		if (i > j) break; // 엇갈리면 멈춘다.

		std::swap(arr[i], arr[j]);
		++i;
		--j;
	}
	// 피벗과 BIGGER(j)를 바꾼다.
	// 왼쪽은 다 피벗보다 작은값이라는 대전제때문에 i는 안된다.
	std::swap(arr[start_idx], arr[j]); // 피벗과 BIGGER(j)를 바꾼다.
	
	// divde and conquer
	quick_sort(start_idx, j - 1, arr);
	quick_sort(j + 1, end_idx, arr);
}

 

일반적으로 퀵소트를 처음 배울때 피벗은 시작위치에 고정하거나 끝 위치에 고정해서 시작하도록 배운다.

하지만 위와 같이 코드를 작성할 경우 편향된 분할이 발생할 가능성이 있다. 이를 해결 하기 위해 아래 코드와 같이

1. 랜덤 피벗

  - rand 함수를 통해 임의의 인덱스를 골라 피벗으로 삼음

2. 호어 분할

   - 루프에서 피벗원소를 제외하지않고 포함시켜 루프 이후 j를 바로 반환. 불필요한 메모리 접근과 스왑연산을 줄인다.
   - <= 비교연산을 제외해 중복원소가 많은 데이터에 대해 편향 분할을 방지한다.

 

두 가지 개념을 적용해 워스트 케이스를 개선하였다.

class Solution {
public:
    void quick_sort(int start_idx, int end_idx, vector<int>& list)
    {
        if(end_idx <= start_idx) return;
        
        int32_t random_pivot_idx = start_idx + (std::rand() % (end_idx - start_idx + 1));
        std::swap(list[start_idx], list[random_pivot_idx]);

        int key = list[start_idx];

        // 호어 분할을 위해 포인터를 구간 밖에서 시작합니다.
        int left = start_idx - 1;
        int right = end_idx + 1;
        
        // pivot과 같은 값을 만나도 멈춰야한다. (스왑을 해야 분할되기 때문에)
        while(true)
        {
            do { ++left; } while (list[left] < key);
            do { --right; } while (list[right] > key);
            
            if (left >= right) break;
            
            std::swap(list[left], list[right]);
        }

        quick_sort(start_idx, right, list);
        quick_sort(right + 1, end_idx, list);

        return;
    }

    vector<int> sortArray(vector<int>& nums) {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        int size = nums.size();
        quick_sort(0, nums.size()-1, nums);

        return nums;
    }
};

 

비교 연산전에 무조건 포인터를 한칸씩 옮기는 조건이 되어야 무한루프를 막을 수 있기 때문에, do while문이 추가되었다.