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

Accepted Answer

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.

Answer 2

By doing a simple google search, I found the biggest part of the code below on this site. I added the selectionSort method myself to suit your parameters.

    public void selectionSort(int a[], int n) 
    {
      recurSelectionSort(a, n, 0);
    }

    // Recursive selection sort. n is size of a[] and index
    // is index of starting element.
    static void recurSelectionSort(int a[], int n, int index)
    {
          
        // Return when starting and size are same
        if (index == n)
           return;
      
        // calling minimum index function for minimum index
        int k = minIndex(a, index, n-1);
      
        // Swapping when index nd minimum index are not same
        if (k != index){
           // swap
           int temp = a[k];
           a[k] = a[index];
           a[index] = temp;
        }
        // Recursively calling selection sort function
        recurSelectionSort(a, n, index + 1);
    }

    // Return minimum index
    static int minIndex(int a[], int i, int j)
    {
        if (i == j)
            return i;
  
        // Find minimum of remaining elements
        int k = minIndex(a, i + 1, j);
  
        // Return minimum of current and remaining.
        return (a[i] < a[k])? i : k;
    }

Recursive Selection Sort Java

2 Answers

Must Read

Your Answer

Marcus Vance

Recursive Selection Sort Java

2 Answers

Must Read

Your Answer

Sign up or log in

Post as a guest

Marcus Vance