Java ArrayList String Selection Sort

Question

I'm struggling mightly on doing selection sort on an ArrayList of Strings to alphabetize them. I have no idea what I'm doing wrong. But its just not working properly for me. Heres my code.

    ArrayList<String> list = new ArrayList<String>();
    list.add("a");
    list.add("d");
    list.add("f");
    list.add("c");
    System.out.println(list);
    int i;
    int j;
    int minValue;
    int minIndex;

    for (i=0; i<list.size(); i++) {
        System.out.println(list.get(i));
        char iLetter = (list.get(i).charAt(0));
        int iValue = (int) iLetter;
        minValue = iValue;
        minIndex = i;
        for(j=i; j<list.size(); j++) {
            char jLetter = list.get(j).charAt(0);
            int jValue = (int) jLetter;
            if (jValue < minValue) {
                minValue = jValue;
                minIndex = j;
            }
        }
        if(minValue < iValue) {
            int temp = iValue;
            char idx = list.get(minIndex).charAt(0);
            int idxValue = (int) idx;
            iValue = idxValue;
            idxValue = temp;

        }
    }
    System.out.println(list);
}

It still prints it out as ["a", "d", "f", "c"]

Where do you swap the positions of the Elements inside list? — Patrick Artner
– Patrick Artner, Commented Nov 10, 2017 at 9:14
What are you trying to do? In your whole "sorting" algorythm you don't change the list at all but just copy a bunch of primitive values around. And Overall whatever you are doing it's an awefull way trying to sort a simple String list when you could just call Collections.sort(list) and be done with it — user6073886
– user6073886, Commented Nov 10, 2017 at 9:15

Eran · Accepted Answer · 2017-11-10 09:18:29Z

5

You are not updating your list anywhere in your loop, so it remains unsorted.

In order to actually swap elements of the list, replace:

if(minValue < iValue) {
    int temp = iValue;
    char idx = list.get(minIndex).charAt(0);
    int idxValue = (int) idx;
    iValue = idxValue;
    idxValue = temp;
}

with:

if(minValue < iValue) {
    Collections.swap (list, i, minIndex);
}

Collections.swap performs the following modification:

list.set(i, list.set(minIndex, list.get(i)));

Now the output will be

[a, c, d, f]

answered Nov 10, 2017 at 9:18

Eran

395k57 gold badges726 silver badges793 bronze badges

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

Comments

Adriaan Koster · Accepted Answer · 2017-11-10 09:54:35Z

As mentioned, you need to do the actual swapping in the list, not just the temporary variables (doh!).

public static void main(String[] args) {

    List<String> list = new ArrayList<>();
    list.add("a");
    list.add("d");
    list.add("f");
    list.add("c");

    System.out.println(list);

    for (int i = 0; i < list.size(); i++) {
        String smallest = list.get(i);
        int smallestIndex = i;
        for (int j = i; j < list.size(); j++) {
            String value = list.get(j);
            if (value.compareTo(smallest) < 0) {
                smallest = value;
                smallestIndex = j;
            }
        }

        if (smallestIndex != i) {
            String head = list.get(i);
            list.set(i, smallest);
            list.set(smallestIndex, head);
        }
    }

    System.out.println(list);
}

Additionally, your code is just a single method, AKA spaghetti code. To make it more object-oriented you could make the following changes.

import java.util.*;

public class SelectionSort<T extends Comparable> {

    private List<T> values;

    public SelectionSort(List<T> values) {
        this.values = values;
    }

    private void sort() {
        for (int headIndex = 0; headIndex < values.size(); headIndex++) {
            sortFrom(headIndex);
        }
    }

    private void sortFrom(int headIndex) {
        int smallestIndex = findSmallestFrom(headIndex);
        if (smallestIndex != headIndex) {
            swap(headIndex, smallestIndex);
        }
    }

    private int findSmallestFrom(int i) {
        int smallestIndex = i;
        T smallest = values.get(i);
        for (int j = i; j < values.size(); j++) {
            T value = values.get(j);
            if (value.compareTo(smallest) < 0) {
                smallest = value;
                smallestIndex = j;
            }
        }
        return smallestIndex;
    }

    private void swap(int i, int j) {
        T head = values.get(i);
        values.set(i, values.get(j));
        values.set(j, head);
    }

    public static void main(String[] args) {

        List<String> values = createTestData();
        System.out.println(values);

        SelectionSort selectionSort = new SelectionSort<>(values);
        selectionSort.sort();

        System.out.println(values);
    }

    private static List<String> createTestData() {
        List<String> values = new ArrayList<>();
        values.add("a");
        values.add("d");
        values.add("f");
        values.add("c");
        return values;
    }
}

Some of the changes I made:

Separate method for creation of test data
Separate method for printing the before and after state of the list and calling the sort
Create an instance instead of only static code
separate iterations and logic into meaningful methods
Rename the 'list' variable to 'values'. The fact that it's a list is already clear. The convention is to name a collection by the meaning of the data it contains
Introduced a generic type variable on the class (<T extends Comparable>). This allows any type of data to be sorted, as long as it implements the Comparable interface

Collectives™ on Stack Overflow

Java ArrayList String Selection Sort

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related