Code 101: Sort an Array using Recursion

Question:

Given an array of integers nums, sort the array in ascending order.

Example 1:

Input: nums = [5,2,3,1] Output: [1,2,3,5] 

Example 2:

Input: nums = [5,1,1,2,0,0] Output: [0,0,1,1,2,5] 

Constraints:

• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104

Solution:

Let’s start with Recursion.

I found this definition while starting with recursion and found it useful.

Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself.

Recursive Algorithm

All recursive algorithms must have the following:

1. Base Case (when to stop)
2. Work needed to move toward Base Case or Solution
3. Recursive Call (call ourselves)

Now coming back to the problem, we know that we need to breakdown our solution in above 3 points

1. Think when do you tell an array to be sorted.
2. if the size is zero?
3. if the size is 1?
4. if the array is in ascending order :)?
5. Now can we make a recursive call to attain 1.a?
6. yes, if we make a recursive call by decreasing the size of the array
7. Now we will try to code what we just thought.

public class SortArray {
    public static void sort(int[] arr, int n) {
        if (n == 0) return;
        sort(arr, n-1);
    }
    public static void main(String[] args) {
        int[] arr = new int[] {3, 4, 2, 6, 1, 1, 9, 1};
        for (int i : arr) {
            System.out.print(i + " ,");
        }
        System.out.println("\n>>>");
        sort(arr, arr.length - 1);
        System.out.println("<<<");
        for (int i : arr) {
            System.out.print(i + " ,");
        }
    }
}

1. Now we will think how we can achieve 1. c
2. Let’s say we have an empty array. Now if we want to add an element to it and the resultant should be a sorted array.
3. so we can add the element directly in this case, correct?
4. Let’s say we have a sorted array. Now if we want to add an element to it and the resultant should be a sorted array.
5. so if the element is greater than the last element then we can add the element directly at the end in this case, correct?
6. if the element is shorter than the last element then we need to put it in between the array, at its correct place. Now, don’t you think this is again pointing to recursion, because we need to go to a place where we can insert the element in the array and it will be sorted.
7. Now we know that we need 2 recursive functions
8. sort
9. insert
10. With this, we will again try to write a code
11. Now adding to the last piece of code we have written. It was reducing or array by 1 in each call so we need to add those back at the correct place.

public static void sort(int[] arr, int n) {
    if (n == 0) return;
    int val = arr[n];
    sort(arr, n-1);
    insert(arr, val, n);
}
// So we just took the last element and put it at it's correct position

Now to insert elements back we will write the insert method.

private static void insert(int[] arr, int value, int n) {
    if (n == 0 || arr[n-1] <= value) {
        arr[n] = value;
    } else {
        int val = arr[n-1];
        insert(arr, value, n - 1);
        arr[n] = val;
    }
}

Code and The order of the calls

import java.util.Arrays;

public class SortArray {
    public static void sort(int[] arr, int n) {
        if (n == 0) return;
        int val = arr[n];
        sort(arr, n-1);
        insert(arr, val, n);
    }
    private static void insert(int[] arr, int value, int n) {
        if (n == 0 || arr[n-1] <= value) {
            arr[n] = value;
        } else {
            int val = arr[n-1];
            insert(arr, value, n - 1);
            arr[n] = val;
        }
    }
    public static void main(String[] args) {
        int[] arr = new int[] {9, 4, 2, 9, 1};
        for (int i : arr) {
            System.out.print(i + " ,");
        }
        System.out.println("\n>>>");
        sort(arr, arr.length - 1);
        System.out.println("<<<");
        for (int i : arr) {
            System.out.print(i + " ,");
        }
    }
}

Sort [9, 4, 2, 9, 1] Arr Size: 4
Sort [9, 4, 2, 9, 1] Arr Size: 3
Sort [9, 4, 2, 9, 1] Arr Size: 2
Sort [9, 4, 2, 9, 1] Arr Size: 1
Sort [9, 4, 2, 9, 1] Arr Size: 0
Insert [9, 4, 2, 9, 1] Arr Size: 1
Insert [9, 4, 2, 9, 1] Arr Size: 0
Inserting Value: 4 at 0
Inserting Value: 9 at 1
Insert [4, 9, 2, 9, 1] Arr Size: 2
Insert [4, 9, 2, 9, 1] Arr Size: 1
Insert [4, 9, 2, 9, 1] Arr Size: 0
Inserting Value: 2 at 0
Inserting Value: 4 at 1
Inserting Value: 9 at 2
Insert [2, 4, 9, 9, 1] Arr Size: 3
Inserting Value: 9 at 3
Insert [2, 4, 9, 9, 1] Arr Size: 4
Insert [2, 4, 9, 9, 1] Arr Size: 3
Insert [2, 4, 9, 9, 1] Arr Size: 2
Insert [2, 4, 9, 9, 1] Arr Size: 1
Insert [2, 4, 9, 9, 1] Arr Size: 0
Inserting Value: 1 at 0
Inserting Value: 2 at 1
Inserting Value: 4 at 2
Inserting Value: 9 at 3
Inserting Value: 9 at 4

Hope you have a better understanding now, continue with the code101 series, and you’ll gain a better understanding.

#HappyCoding