Algorithm: Partition, NetherLandParition and Quick Sort

Partition

Given an array and a number, make all the array elements smaller or equal than number to the left, move all array elements bigger than the number to right of array.

public class Partition {
     private static void partition(int[] arr, int num) {
        int l = -1, r = arr.length;
        while (l + 1 < r) {
            if (arr[l + 1] < num) {
                l++;
            } else {
                swap(arr, l + 1, --r);
            }
        }
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

NetherlandFlag

Given an array arr, and index.

move all elements smaller than arr[index] to the left part of array,
move all elements equal to arr[index] to the middle part of array,
move all elements bigger than arr[index] to the right part of array.

public class NetherLandFlag {
    public static void netherland(int[] arr, int index) {
        // move the index number to the right part
        swap(arr, index, arr.length - 1);
        // prepare 3 pointers to mark
        // right boundary of smaller area
        // left boundary of bigger area
        // iter pointer
        int l = -1, r = arr.length - 1, i = 0;
        
        while (i < r) {
            if (arr[i] < arr[arr.length - 1]) {
                swap(arr, i++, ++l);
            } else if (arr[i] == arr[arr.length - 1]) {
                i++;
            } else {
                swap(arr, i, --r);
            }
        }
        
        swap(arr, r, arr.length - 1);
        
        
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

QuickSort

Quick Sort is implemented based on either Partition problem or Netherland problem.

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int[] res = partition(arr, left, right);
        quickSort(arr, left, res[0] - 1);
        quickSort(arr, res[1] + 1, right);
    }

    public static int[] partition(int[] arr, int left, int right) {
        int l = left - 1, r = right, mid = (left + right) / 2, i = left;
        swap(arr, mid, right);

        while (i < r) {
            if (arr[i] < arr[right]) {
                swap(arr, ++l, i++);
            } else if (arr[i] == arr[right]) {
                i++;
            } else {
                swap(arr, i, --r);
            }
        }

        swap(arr, i, right);
        return new int[] { l + 1, r };
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}