How to make a selection sort algorithm using Java collection linkedlist?

Question

I'm new to Java and I need to make a selection sort algorithm using Java LinkedList. I tried making the insertion sort, but I can't turn it into a selection sort. This is my selection sort code:

import java.util.*;
public class select {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        LinkedList<Integer> data = new LinkedList<>();

        System.out.println("Enter total count of elements-> ");
        int num = input.nextInt();

        while(num>0){
            data.add(input.nextInt());
            num--;
        }

        System.out.println("Original data:\n" +data);

        LinkedList<Integer> sortedData=sort(data);
        System.out.println("Sorted data:\n"+sortedData);
    }
    
    public static LinkedList<Integer> sort(LinkedList<Integer> data) {
        
        ListIterator<Integer> iterator=data.listIterator();
        while (iterator.hasNext()) {
            int key=iterator.next();
            

            for(int i = 0 ;i<data.size()-1;i++) {
                for(int j = i+1; j < data.size(); j++){
                    if(data.get(j) < key){
                        int x = data.get(j);
                        int y = key;
                        swap(data, x, y);
                    }
                }
                
            }
        }
        return data;
    }

    private static void swap(LinkedList<Integer> data, int x, int y) {
        int index1 = data.indexOf(x);
        int index2 = data.indexOf(y);

        if(index1 == -1 || index2== -2){
            return;
        }
    }
}

The sorted data is always the same as the original data and I don't know which went wrong.

Edit: The swap method can function perfectly now, but the data is still not in the right order.

Original data:
[23, 12, 6, 23, 98]
Sorted data:
[12, 6, 23, 98, 23]

So I guess the sort method is the problem.

Answer 1

To address the problem of the output not changing: your swap method doesn't actually swap the values.

These two lines will get the indices of your data, as you'd expect.

int index1 = data.indexOf(x);
int index2 = data.indexOf(y);

But all this does is ensure that your indices are valid, meaning the data were found. (Although the second check should also be -1 because the #indexOf method always returns the index, if found, or -1. Never -2.)

if (index1 == -1 || index2 == -1){ // changed to -1 on both
    return;
}

To actually do the swap, you need something like at the end of the other code in your swap method:

data.set(index1, y);
data.set(index2, x);

The #set method changes the value at the first argument index to the value in the second argument, so doing it twice will effectively swap the data.

To address the problem of your code not properly sorting: you use a ListIterator and a while loop to loop through the list, which means instead of incrementally checking each number and the numbers after it, you repeatedly check the first number and the numbers after it, which won't do anything after the first pass.

ListIterator<Integer> iterator=data.listIterator();
while (iterator.hasNext()) { // This will loop through the list once overall
    int key=iterator.next(); // This is the current item of the while loop

    for(int i = 0 ;i<data.size()-1;i++) { // This loop is completely ignored
        for(int j = i+1; j < data.size(); j++){
            if(data.get(j) < key){ // You are comparing to key, which is just the item in the overall list iteration
                int x = data.get(j);
                int y = key;
                swap(data, x, y);
            }
        }          
    }
}

You are not using i from the outer for loop because you are using key. To fix this, you should completely remove the while loop and iterator:

public static LinkedList<Integer> sort(LinkedList<Integer> data) {
    for(int i = 0 ;i<data.size()-1;i++) {
        for(int j = i+1; j < data.size(); j++){
            int x = data.get(j); // Another optimization you can make is to only call the `#get` method once for each index, like this
            int y = data.get(i);
            if(x < y){
                swap(data, x, y);
            }
        }
    }
    return data;
}