Recursive Selection Sort in Java

Question

I need to implement this algorithm creating a new ArrayList object at each recursive call.

My starting Array contains integers in this order"20, 40 ,10, 30 ,50 ,5" , after sorting it I have 5,5,5,5,5,5. I think that the problem is in the recursive call and in the last for cicle of the SelectionSort because removing the last for I notice that the the first element is sorted correctly.

import java.util.*;

public class SelectionSort {

   //var
   public ArrayList<Integer> arr ;

   //constructor
   public SelectionSort(ArrayList<Integer> arr){
      this.arr = arr;
   }

   public ArrayList<Integer> getarraylist() {
   return arr;
   }


   public void sort(){  

     //position of the last sorted element
     int minimum =0;

     if (arr.size() <=0 )  return;

     for ( int j = 1; j < arr.size()-1; j++ ) { 

           if (arr.get(j) < arr.get(0) ) {
               minimum = j;
               //swap element 0 and minimum
               int temp = arr.get(0);
               arr.set(0, arr.get(minimum));
               arr.set(minimum, temp);
           }
     }

     //recursive call, new array without first element (already sorted)
     ArrayList<Integer> arr2 = new ArrayList<>(arr.subList(1,arr.size()));
     SelectionSort s2 = new SelectionSort(arr2);
     s2.sort();

     for(int i=0;i<s2.getarraylist().size();i++) {
         arr.set(i, s2.getarraylist().get(i));
     }
}

Driver class

public class Main {

    public static void main(String[] args) {

    ArrayList<Integer> arr = new ArrayList<Integer (Arrays.asList(20,40,10,30,50,5));


    System.out.println("\n ARRAY ELEMENTS \n ");
    for (int i: arr) {
        System.out.println(i);
    }

    System.out.println("\n SORTED ELEMENTS \n ");
    SelectionSort s = new SelectionSort(arr);
    s.sort();
    for (int i: s.getarraylist()) {
        System.out.println(i);
    }

}
}

Answer 1

You have actually two bugs in your algorithm that, together, lead to the observed output.

---

The first bug is within the for-loop that determines the minimal element:

for ( int j = 1; j < arr.size()-1; j++ ) { ...

You terminate one element too early, i.e. the last element is never considered. Thus, after the first iteration, the 5 is the last element in your ArrayList. In fact, it is the last element in every of your ArrayLists. The fix is to not subtract 1 in the for-condition:

for ( int j = 1; j < arr.size(); j++ ) { ...

---

The second bug is in your last for-loop where you copy the values from index i of s2 to index i of arr. You neglect the fact that s2 is one element shorter than arr. Thus, the only element not overriden is the last element. The fix is to get the i-th element from s2, but write it at the i + 1-th index of arr:

arr.set(i + 1, s2.getarraylist().get(i));

---

Now let us take look at how those two bugs lead to the observed output. Since

• the last element in your ArrayList is never overridden and
• the last element is always the same,

all elements have the same value (in your test case: 5).

---

Some remarks on your code:

• the variable minimum is superfluous and can be replaced with j.

• If you replace all occurences of ArrayList in SelectionSort with List, you can actually simplify the last part of your code to:

  // remove the line declaring arr2, it is no longer needed
  SelectionSort s2 = new SelectionSort(arr.subList(1, arr.size()));
  s2.sort();
  // last for-loop not needed anymore, method ends here
  

  This is possible because ArrayList#subList(...) states that "The returned list is backed by this list, so non-structural changes in the returned list are reflected in this list, and vice-versa."

• You should take a little bit more care wrt. indentation.
• You have some minor inconsistencies in your coding style. For example, sometimes you write a blank after ( or before a ) or {, sometimes you do not. See what you like more and use it uniformly.
• In Java, variable-, parameter- and methodnames should be written in camelCase (getarraylist() -> getArrayList())