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

Hi and welcome, while this would be an interesting challenge, it is not the philosophy of the site to provide code written from scratch. You probably should begin with it, do your best and come back when you're stuck with something. — Yassin Hajaj
– Yassin Hajaj, Commented May 27, 2018 at 13:42

Thomas Fritsch · Accepted Answer · 2018-05-27 15:25:21Z

2

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.

answered May 27, 2018 at 15:25

Thomas Fritsch

10.3k33 gold badges42 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Dharman · Accepted Answer · 2023-01-13 15:51:16Z

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;
    }

Madhushan Gamage · Accepted Answer · 2024-08-13 05:44:22Z

0

Try this and This is the base case of the code and I give the code order and give the explanation of it.

 public int[] selectionSort(int[] a, int k) {
         // Base case
            if (k == 0) {
                return a;
            }

Below code shows that You should Add the minimum element in the array from index 0 to k.

int minIndex = k;
for (int i = 0; i <= k; i++) {
    if (a[i] < a[minIndex]) {
        minIndex = i;
    }
}

and Below code shows that Swap the minimum element with the element at index k by using this methods

  int temp = a[k];
a[k] = a[minIndex];
a[minIndex] = temp;

then add Recursively call the function to sort the subarray from 0 to k-1

 return selectionSort(a, k - 1);

To more explanation : I add the Recursive Approach for The function reduces the problem size by 1 in each call by sorting the subarray of the first k elements.

and you should Find the Minimum In each step, the function finds the minimum element in the subarray and places it at the end (kth index) of the subarray.

& Swapping method will help you to find The smallest element is swapped with the element at the current index k.

answered Aug 13, 2024 at 5:44

Madhushan Gamage

11 bronze badge

1 Comment

Abra Over a year ago

For the sake of completeness, I suggest that you post a runnable class containing your code snippets and show how it produces the required results when using the sample data in the question.

Collectives™ on Stack Overflow

Recursive Selection sort Java

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related