JAVA One Pass Algorithm using Dutch national flag problem/3 way Partition


  • 0
    T

    The algorithm indexes three locations, the bottom of the top group, the top of the bottom group, and the top of the middle group. Elements that are yet to be sorted fall between the middle and the top group. At each step, examine the element just above the middle. If it belongs to the top group, swap it with the element just below the top. If it belongs in the bottom, swap it with the element just above the bottom. If it is in the middle, leave it.

    class Solution {
    // Swap Numbers    
        void swap(int[] nums, int i,int j)
        {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        public void sortColors(int[] nums) {
            int lo =0;
            int mid =0;
            int hi = nums.length-1;
            int median =1; // Medium element is 1 for this problem. 
            while(mid <= hi)
            {
                if(nums[mid]< median)
                {
                    swap(nums,lo,mid);
                    lo++;
                    mid++;
                }else if(nums[mid] > median)
                {
                    swap(nums,mid,hi);
                        hi--;
                }else
                {
                    mid++;
                }
                
            }
            
        }
    }
    

Log in to reply
 

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