Sort a linked list with Selection algorithm in Java

1

I'm working with sorting algorithms. I implemented by ordering with Bubble sort, however, must be implemented with an example where the algorithm is not stable (Selection, Quicksort, Heapsort or Introsort). The idea is to sort a list of integers

Implementation with Bubble sort

import java.util.LinkedList;
import java.util.List;

public class Ordenação {

    public static void main(String[] args) {
          List<Integer> lista = new LinkedList<Integer>();

            lista.add(5);
            lista.add(3);
            lista.add(1);
            lista.add(2);
            lista.add(4);
            ordenacaoBubleSort(lista);     
    }


 public static  void ordenacaoBubleSort(List<Integer> lista) {

     for(int i = 0; i < lista.size(); i++) {
         for(int j = 0; j < (lista.size() - 1 - i); j++) {
             if(lista.get(j) > lista.get(j + 1)) {
                 Integer aux = lista.get(j);
                 lista.set(j, lista.get(j + 1));
                 lista.set(j + 1, aux);
             }
             System.out.println(lista);

         }
     }

     System.out.println(lista);
 }

//public static void ordenacaoSelecao(List<Integer>lista) {

//}



}

How could I adapt this Selection algorithm using a list?

    public void selectionSort(int vetor[]) {
    for (int i = 0; i < vetor.length; i++) {
        int posicaoMenor = i;
        for (int j = (i + 1); j < vetor.length; j++) {
            if (vetor[j] < vetor[posicaoMenor]) {
                posicaoMenor = j;
            }
        }
        if (vetor[i] != vetor[posicaoMenor]) {
            int temp = vetor[i];
            vetor[i] = vetor[posicaoMenor];
            vetor[posicaoMenor] = temp;
        }
    }
}
    
asked by anonymous 02.05.2018 / 15:33

1 answer

1

Your adapted method for a list looks like this. Take a look at the code comments to understand the changes you need:

private static void selectionSort(List<Integer> vetor) {
        // o método size() retorna o tamanho de uma lista
        // (é o equivale ao length do array)
        for (int i = 0; i < vetor.size(); i++) {
            int posicaoMenor = i;
            for (int j = (i + 1); j < vetor.size(); j++) {
                //o método get() acessa o valor em uma determinada posição da lista
                //é o equivalente ao vetor[j] do array
                if (vetor.get(j) < vetor.get(posicaoMenor)) {
                    posicaoMenor = j;
                }
            }
            if (vetor.get(i) != vetor.get(posicaoMenor)) {
                int temp = vetor.get(i);
                //o método set() substitui um valor por outro em
                //uma determinada posição da lista
                //o primeiro parâmetro é onde eu quero mudar,
                //o segundo é o que eu quero colocar no lugar
                vetor.set(i, vetor.get(posicaoMenor));
                vetor.set(posicaoMenor, temp);
            }
        }
    }

And a test method:

public static void main(String[] args) {
   List<Integer> lista = new ArrayList<>();
   Collections.addAll(lista, 5, 1, 8, 2, 9);
   selectionSort(lista);
   System.out.println(lista); //imprime [1, 2, 5, 8, 9]
}

If you have any questions, just ask. Otherwise, just mark as resolved. ;)

    
02.05.2018 / 17:57