Selection Sort without collections.sort in ArrayList

Question

So, why won't this code work it is returning the original list always (I haven't put the return statement, but can someone determine why the logic behind my selection sort algorithm is not working). Any help would be gladly appreciated!

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class ArrayListDemo {
    public static void main(String [] args) {
        ArrayList <String> list = new ArrayList <String> (15);
        list.add("Wilson");
        list.add("Annans");
        list.add("Manning");
        list.add("Branday");
        list.add("Smittens");
        list.add(2, "Goddard Fey");
        list.set((list.size()) - 1, "Brand Brandon");
        list.add("Brand Boarders");
        selectionSort(list);
    }
    static void selectionSort(ArrayList<String> a) {
         int smallindex;
         for(int i = 0; i < a.size(); i++) {
              smallindex = i; // set first element as smallest
              for(int j = i + 1; j < a.size(); j++) { // find smallest
                   if (a.get(j).compareTo(a.get(smallindex)) > 0) {
                       swap(a, i, j);
                   }

              }
         }
    }

    static void swap(ArrayList<String> a, int index1, int index2) {
         String i_string = a.get(index1);
         String j_string = a.get(index2);
         String temp = i_string;
         i_string = j_string;
         j_string = temp;
    } 
}

Your swap method does not modify the ArrayList a anywhere. You need something like a.set(index1, i_string) etc. — Lee
– Lee, Commented Jan 15, 2018 at 16:22
Yes, you are creating new variables holding references, not values and then you are reassigning references without modifing the values. you would have to go with a.set(index1, ...) — alobodzk
– alobodzk, Commented Jan 15, 2018 at 16:57

Eran · Accepted Answer · 2018-01-15 19:46:03Z

1

Your swap(ArrayList<String> a, int index1, int index2) method creates local variables - i_string and j_string - and then swaps them. This has no impact on the contents of the input List a.

To change the value of the i'th element of the List a you must call a.set(i,newValue).

You can either implement the swap method yourself, or use the existing Collections.swap:

static void selectionSort(ArrayList<String> a) {
    int smallindex;
    for(int i = 0; i < a.size(); i++) {
        smallindex = i; // set first element as smallest
        for(int j = i + 1; j < a.size(); j++) { // find smallest
            if (a.get(j).compareTo(a.get(smallindex)) > 0) {
                Collections.swap(a, i, j);
            }
        }
    }
}

If you wish to learn how to implement swap correctly, you can take a look at the JDK implementation:

public static void swap(List<?> list, int i, int j) {
    final List l = list;
    l.set(i, l.set(j, l.get(i)));
}

As you can see, this method sets the value returned by l.set(j, l.get(i)) to be the new i'th element of the List. l.set(j, l.get(i)) sets the value l.get(i) as the new j'th element of the List and returns the previous j'th element. Therefore the new i'th element of the List becomes the previous j'th element.

answered Jan 15, 2018 at 19:46

Eran

395k57 gold badges726 silver badges793 bronze badges

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

2 Comments

Gabriel Over a year ago

Side question: Why did they assign list to a final variable before swaping elements?

Eran Over a year ago

@Gabriel well, list.set(i, list.set(j, list.get(i))); doesn't pass compilation due to the type of list being List<?>. Of course, they could have defined the method as public static <T> void swap(List<T> list, int i, int j), and then list.set(i, list.set(j, list.get(i))); would have worked. I'm not sure why they didn't do that. Perhaps the reason was backwards compatibility (this method was introduced before generics were added to Java).

Collectives™ on Stack Overflow

Selection Sort without collections.sort in ArrayList

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related