Share classic three way sort algorithm


  • 0
    Y
    class Solution { 
    public:
        // classic three way sort algorithm
        void threeWaySort(vector<int>& nums, int lo, int hi) {
            if(hi <= lo)
                return;
            int loe = lo;
            int hie = hi;
            int low_val = nums[lo];
            int i = lo;
            while(i <= hie) {
                if(nums[i] < low_val) {
                    exchange(nums, i, loe);
                    i++;
                    loe++;
                }
                else if(nums[i] > low_val) {
                    exchange(nums, i, hie);
                    hie--;
                }
                else {
                    i++;
                }
            }
            threeWaySort(nums, lo, loe - 1);
            threeWaySort(nums, hie + 1, hi);
        }
        
        void exchange(vector<int>& nums, int a, int b) {
            int tmp = nums[a];
            nums[a] = nums[b];
            nums[b] = tmp;
        }
        
        void sortColors(vector<int>& nums) {
            threeWaySort(nums, 0, nums.size() - 1);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.