Recursive Selection sort Java

Question

I've been looking for a recursive selection sort, using only 2 parameters:

• The array that has to be sorted
• a value k, which indicates till which element it has to be sorted.

Example: SelectionSort(array[] a, int k) with a being {6,3,5,7,2} and k being 2 will sort the first 3 elements, and will keep the last elements untouched.

I was thinking about starting with an if-statement for k being 0, and if that was the case, it would just return the array as it is, since you cant sort an array of size 1. Something like:

public int[] sort(int[] a){
    a = selectionSort(a, n-1);
    return a;
}

public int[] selectionSort(int[] a, int k){
    if (k = 0){
        return a;
    }
    else{
        selectionSort(a, k-1 );
               ... (part i really don't know)
}

I have no clue how to do the 'else' part since I only know that it has to call the method again. I'm not allowed to create other methods. I also need to make sure I use exactly 2 parameters, nothing more, nothing less.

I have to work it out in pseudocode, but I understand some Java, so if someone could help me by using either pseudo, or Java, it would be so helpful

Answer 1

First some remarks to your code:

• Your methods sort and selectionSort don't need to return an int[] array, since the array object a stays the same all the time. It is only the content within this array which changes. Hence, you can use void as return-type.
• In your if use (k == 0) instead of (k = 0)

You already figured out the first part. Here it is how you can do the second part in pseudo code:

public void selectionSort(int[] a, int k) {
    if (k == 0) {
        return;
    }
    else {
        selectionSort(a, k-1 );
        find x such that a[x] is the smallest of a[k] ... a[a.length - 1]
        if (a[k-1] > a[x]) {
            swap a[k-1] and a[x]
        }
    }
}

I'm sure you are able to refine the pseudo code to real Java code.