Recursion in Java: Part 2 ( Subset, Subsequence, Quick sort and Merge sort)

Recursion is a powerful concept that simplifies problem-solving by breaking down problems into smaller subproblems. In this blog, we will explore advanced topics in recursion, specifically Quick Sort, Merge Sort, Subsets, and Subsequences. These concepts are fundamental to understanding recursive algorithms and mastering problem-solving.

Quick Sort

Quick Sort is a popular sorting algorithm based on the divide-and-conquer paradigm. Here’s how it works:

Pivot Element: We select the middle element as the pivot. The pivot serves as a reference point for sorting.
Partitioning: Two pointers are used:
- start is initialized to the beginning of the array.
- end is initialized to the last index of the array. Using a while loop, we increment the start pointer until we find an element greater than the pivot, and decrement the end pointer until we find an element smaller than the pivot. When a violation occurs, we swap the elements.
Recursive Process: After partitioning, the array is partially sorted with elements less than the pivot on the left and elements greater than the pivot on the right. This process is repeated recursively on the left and right partitions until the array is fully sorted.

static void quickSort(int[] nums, int low, int hi) {
    if (low >= hi) {
        return;
    }

    int s = low;
    int e = hi;
    int m = s + (e - s) / 2;
    int pivot = nums[m];

    while (s <= e) {

        // This is the reason why if its already sorted, it will not swap
        while (nums[s] < pivot) {
            s++;
        }
        while (nums[e] > pivot) {
            e--;
        }

        if (s <= e) {
            int temp = nums[s];
            nums[s] = nums[e];
            nums[e] = temp;
            s++;
            e--;
        }
    }

    // now my pivot is at correct index, it'll sort two halves now
    quickSort(nums, low, e);
    quickSort(nums, s, hi);
}

Merge Sort

Merge Sort is another divide-and-conquer algorithm that works as follows:

Divide: The array is recursively divided into two halves until each half contains only one element (the base condition).
Merge: The divided arrays are then merged in sorted order. The merging process involves:
- Comparing elements from the two subarrays.
- Adding the smaller element to the merged array.
- Repeating the process until all elements are merged.

Merge Sort guarantees a time complexity of O(n log n), making it efficient for large datasets.

static int[] mergeSort(int[] arr){
    if (arr.length==1){
        return arr;
    }
    int mid = arr.length/2;

    int[] first = mergeSort(Arrays.copyOfRange(arr,0,mid));
    int[] second = mergeSort(Arrays.copyOfRange(arr,mid,arr.length));

    return merge(first,second);
}

private static int[] merge(int[] first, int[] second) {
    int[] mix = new int[first.length + second.length];

    int i = 0;
    int j = 0;
    int k = 0;

    while (i < first.length && j < second.length) {
        if (first[i] < second[j]) {
            mix[k] = first[i];
            i++;
        } else {
            mix[k] = second[j];
            j++;
        }
        k++;
    }

    while (i < first.length) {
        mix[k] = first[i];
        i++;
        k++;
    }

    while (j < second.length) {
        mix[k] = second[j];
        j++;
        k++;
    }
    return mix;
}

Subsets

A subset is a collection of elements derived from an array, where each element is either included or excluded. For example, given an array {1, 2, 3}, the subsets are: [], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]

To generate all subsets programmatically:

Outer List: Create an empty list to store all subsets.
Empty Subset: Start by adding an empty subset to the outer list.
Iterate Through Elements:
- For each element in the array, iterate through all existing subsets in the outer list.
- Create a new subset by adding the current element to each existing subset.
- Add the new subset to the outer list.

static List<List<Integer>> subset (int[] arr){
    List<List<Integer>> outer = new ArrayList<>();

    outer.add(new ArrayList<>());

    for (int num : arr){
        int n = outer.size();
        for (int i = 0; i < n; i++) {
            ArrayList<Integer> inner = new ArrayList<>(outer.get(i));
            inner.add(num);
            outer.add(inner);
        }
    }
    return outer;
}

This ensures all possible subsets are generated and stored.

Subsequences

Subsequences are similar to subsets but apply to strings instead of arrays. A subsequence can include or exclude each character of a string.

For example, given the string "abc", the subsequences are: ["", "a", "b", "ab", "c", "ac", "bc", "abc"]

The process of generating subsequences involves two choices for each character in the string:

Include the character in the current subsequence.
Exclude the character and proceed with the rest of the string.

static ArrayList<String> subseq (String pr, String unPr){
    if (unPr.isEmpty()){
        ArrayList<String> list = new ArrayList<>();
        list.add(pr);
        return list;
    }

    char ch = unPr.charAt(0);
    ArrayList<String> left = subseqRet(pr + ch, unPr.substring(1));
    ArrayList<String> right = subseqRet(pr, unPr.substring(1));

    left.addAll(right);
    return left;
}

Combining the results of these choices recursively generates all possible subsequences.

GitHub Repository

To view all the code snippets related to Quick Sort, Merge Sort, Subsets, and Subsequences, visit the My GitHub Repository. This repository serves as a practical guide to understanding and implementing these concepts.

Here’s the link to my repository: GitHub Repo

LeetCode Problems

Practice is key to mastering recursion. Here are some recommended LeetCode problems that I solved, to enhance my understanding:

Conclusion

Understanding recursion is vital for tackling complex problems efficiently. Quick Sort, Merge Sort, Subsets, and Subsequences showcase the power of recursion in solving diverse problems. Sharing knowledge through examples and practical implementations not only reinforces learning but also inspires others in their journey.