Recursive/Sorting an Array a specific way

Question

To recursively sort an array, fi nd the largest element in the array and swap it with the last element. Then recursively sort the array from the start to the next-to-the-last element. Write and test a method that recursively sorts an array in this manner. Started it and I think my code complete trash. Recursion do not make much sense to me and just needing help with this problem. Ive found how to locate the highest int in the array just havihng trouble finding out the recursion to sort it now.

public class Sorting
{
    public static void main(String[] args) 
    {
        int[] array={5,1,8,3,4,7};
        int length = array.length;
        int max = -99999;
        int[] revArray= sortArray(array,length-1,max,length);  

        for(int i:revArray)
            System.out.print(i+" ");

    }

    public static int[] sortArray(int[] a,int j,int max,int length)
    {        

        if( j <= 0)   
        {    
            return a;  

        }

        if(max < a[j])
        {
            max = a[j];            
            return sortArray(a, j-1, max,length); 

        }  

         return a;
    }
}

Answer 1

Andreas Troelsen wrote a really good answer on how you break down the problem.

Here is the code and below is written in short how it works:

public class Sorting {

public static void main (String[] args) { 
    int[] array = {5,1,8,3,4,7};
    sortArray(array, 0, array.length-1);
    printArray(array);
}

public static void sortArray(int[] array, int start, int end) {
    if ( start == end ) return;
    int max_index = findMax(array, start, end);
    swap(array, max_index, end);
    sortArray(array, start, end-1);
}

public static void swap(int[] array, int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

public static void printArray(int[] array) {
    for (int x : array)
        System.out.print(x + " ");
    System.out.println();
}

public static int findMax(int[] array, int start, int end) {
    int max = array[start];
    int index = start;
    for( ; start <= end; start++)
        if ( max < array[start] ) {
            max = array[start];
            index = start;
        }
    return index;
}

}

You are given an array and want to sort it with the way you describe in your question.

sortArray method does the below:

1. Finds the index of the element with the maximum value. That is being done with the findMax method.
2. Swaps that element with the last element of the array.
3. Recursively calls itself for the same array but without its last element (which is the largest and already sorted correctly).

Answer 2

You're sort of on the right track, but your code does look a bit like you're shooting in the dark with regards to a few things. Sometimes, breaking the problem down into subproblems and tackling each one in isolation makes the whole thing less overwhelming...

Finding the index of the largest element in an array

First of all, you need to be able to figure out the largest element in an unsorted array (or in this case, in a subarray). Since the array is unsorted, you have to loop through all of its elements to find the maximum. So to start off, you can write an auxiliary method that takes as input an array, and returns the index of the largest element. To do this, you need to keep track of both the value of the largest element as well as its index. In pseudo-code:

function indexOfLargestElement(array)
    index = -1
    max = -infinity
    for i = 0 to array.length do
        if array[i] > max then
            index = i
            max = array[i]
        end
    end
    return index
end

Now, this only solves the problem of finding the largest element in a full array. Modify the method to take an end index, so you can specify exactly how far into the array you want to look. This allows you to find the largest element in any range starting from the first element.

Swapping elements

Java doesn't have a swap function like some other languages do, so you will need a temporary variable to hold the value of one index while you write the value of the other index to it. Then you can write the value of the temporary variable to the other index, and the two elements will effectively be swapped. You could also write an auxiliary method to do this - it takes as input an array, and the two indices to swap.

Putting it together

Now you have the tools to write your recursive sorting method. Before you do, though, think about why this algorithm works. If you find the largest element in the array and swap it with the last element of the array, it means that you can reduce your sorting problem by one element. Now you just have to find the largest element in the subarray that starts at the first element of the array and ends at the second-to-last element. Then you swap that element with the second-to-last element, and by now, you have reduced your sorting problem by two elements. Now you just have to find the largest element in the subarray that starts at the first element of the array and ends at the third-to-last element. Then you swa...

And that's basically what recursion is. Simple recursive functions have a base case (e.g. an array of size 1), and an induction case (an array of size n). The idea is to partially solve the induction case, so you can reduce it to another induction case that's smaller, and continue to do so until you reach the base case, which is often trivial (an array of size 1 is already sorted).