(JAVA) Help in Sorting Exercise (Selection Sort and Insertion)

Question

/*EXERCISE: Write a method that puts in ascending order a disordered sequence of n integer.
(a) Using sorting by selection
(b) Using sorting by insertion*/

I tried to solve the exercise, but I’m getting this result:
Original sequence: 3 9 1 3 2 0 8 11
Selection sequence: 0 3 1 3 2 11 8 9
Insertion sequence: 0 1 3 2 3 8 9 11
What could I be doing wrong?

class Tres {

    public static int [] ordenaSelecao (int [] array) {
    int [] arraySelecao = array;
    int menor = arraySelecao[0];
    int posMenor = 0;

        for (int i = 0; i<arraySelecao.length; i++) {
            //buscando menor elemento
            for (int j=i+1; j<arraySelecao.length; j++){
                if (menor > arraySelecao[j]) {
                menor = arraySelecao[j];
                posMenor = j;
                }

            }   

            if (arraySelecao[i] > arraySelecao[posMenor]) {
                int aux = arraySelecao[posMenor];
                arraySelecao[posMenor] = arraySelecao[i];
                arraySelecao[i] = aux;
            }

        }
        return arraySelecao;
    }


    public static int [] ordenaInsercao (int [] array) {
    int [] arrayInsercao = array;
        for (int i=1; i<arrayInsercao.length; i++){
            for (int j=i-1; j>0; j--){
                if (arrayInsercao[i]<arrayInsercao[j]) {
                    int aux = arrayInsercao[i];
                    arrayInsercao[j+1] = arrayInsercao[j];
                    arrayInsercao[j] = aux;
                }
            }
        }

        return arrayInsercao;

    }



    public static void main(String[] args) {
        int [] array = {3,9,1,3,2,0,8,11};

        System.out.print("Sequencia Original: ");
        for (int i=0; i<array.length; i++) {
            System.out.print(array[i]+" ");
        }

        System.out.println(" ");
        System.out.print("Sequencia Selecao: ");
        int [] arraySelecao = ordenaSelecao(array);
        for (int i=0; i<arraySelecao.length; i++) {
            System.out.print(arraySelecao[i]+" ");
        }

        System.out.println(" ");
        System.out.print("Sequencia Insercao: ");
        int [] arrayInsercao = ordenaInsercao(array);
        for (int i=0; i<arrayInsercao.length; i++) {
            System.out.print(arrayInsercao[i]+" ");
        } 
    }
}

Answer 1

I fixed your program, here’s how it turned out:

import java.util.Arrays;

class Tres {
    public static int[] ordenaSelecao(int[] array) {
        int[] arraySelecao = array.clone();

        for (int i = 0; i < arraySelecao.length; i++) {
            int menor = arraySelecao[i];
            int posMenor = i;

            // Buscando o menor elemento.
            for (int j = i + 1; j < arraySelecao.length; j++) {
                if (menor > arraySelecao[j]) {
                    menor = arraySelecao[j];
                    posMenor = j;
                }
            }

            // Posicionando o menor elemento.
            if (arraySelecao[i] > arraySelecao[posMenor]) {
                int aux = arraySelecao[posMenor];
                arraySelecao[posMenor] = arraySelecao[i];
                arraySelecao[i] = aux;
            }
        }
        return arraySelecao;
    }

    public static int[] ordenaInsercao(int[] array) {
        int[] arrayInsercao = array.clone();
        for (int i = 1; i < arrayInsercao.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (arrayInsercao[j + 1] < arrayInsercao[j]) {
                    int aux = arrayInsercao[j + 1];
                    arrayInsercao[j + 1] = arrayInsercao[j];
                    arrayInsercao[j] = aux;
                }
            }
        }

        return arrayInsercao;
    }

    public static void main(String[] args) {
        int[] arrayOriginal = {3, 9, 1, 3, 2, 0, 8, 11};
        System.out.println("Sequencia Original: " + Arrays.toString(arrayOriginal) + ".");

        int[] arraySelecao = ordenaSelecao(arrayOriginal);
        System.out.println("Sequencia Selecao: " + Arrays.toString(arraySelecao) + ".");

        int[] arrayInsercao = ordenaInsercao(arrayOriginal);
        System.out.println("Sequencia Insercao: " + Arrays.toString(arrayInsercao) + ".");
    }
}

See here working on ideone.

Your program was almost right, the mistakes there were few and silly:

• In the selection algorithm, you must track the smallest element of each iteration of i regardless of other iterations. You should not track in the context of the entire function because then, once the smallest element is found, you get stuck in it. The solution to this is to put the veritable menor and posMenor into the loop of i getting them out of position i (and not zero).

• In the insertion algorithm, inside the loop of the j, you compare the positions i, j and j + 1. You should only use positions j and j + 1. In addition, the stopping condition is j >= 0, and not j>0.

• Arrays that are being passed by parameters are modified and then returned. This means that in your test (in the method main), the array that would be passed to the insertion sort would be the array resulting from the sorting by selection (which if it is working, is already sorted). What you wanted was to test the sorting by selection on top of an array with the same content given to the sorting by insertion. To do this, you can use the method clone() of the array to create a copy, thus avoiding changing the original array.

• You can use the method java.util.Arrays.toString(int[]) to convert array elements into an String, which eliminates the need to print element by element.