Entonces tengo este código para mi selección:

public static void selectionSort(int[] arrayToSort){
    int smallest;
    for(int i = 0; i < arrayToSort.length; i++){
        smallest = i;
        for(int j = i+1; j < arrayToSort.length; j++){
            if(arrayToSort[j] < arrayToSort[smallest]){
                smallest = j;
            }
            if(smallest != i){
                int temp = arrayToSort[i];
                arrayToSort[i] = arrayToSort[smallest];
                arrayToSort[smallest] = temp;
            }
        }
    }
}

Estoy generando una matriz int con números aleatorios. Mi selección de selección a veces ordena la matriz, a veces "casi" ordena la matriz. La matriz se ordenará principalmente, excepto por unos pocos números que están en lugares incorrectos. No puedo entender qué sale mal aquí, ¿alguna idea?

Algunos resultados de la prueba donde la matriz no se ordenó por completo:

***NON SORTED***
77
53
27
58
83
***SORTED***
27
53
77
58
83

Y

***NON SORTED***
40
87
27
48
82
***SORTED***
27
40
82
48
87
-1
Carlton 24 dic. 2016 a las 19:52

3 respuestas

La mejor respuesta

Tienes una parte del código dentro del bucle interno, ponlo fuera del bucle;

public static void selectionSort(int[] arrayToSort){
    int smallest;
    for(int i = 0; i < arrayToSort.length; i++){
        smallest = i;
        for(int j = i+1; j < arrayToSort.length; j++){
            if(arrayToSort[j] < arrayToSort[smallest]){
                smallest = j;
            }
        }
        if(smallest != i){
            int temp = arrayToSort[i];
            arrayToSort[i] = arrayToSort[smallest];
            arrayToSort[smallest] = temp;
        }
    }
}

Consulte, por ejemplo, el algoritmo en Wikipedia.

3
Renzo 24 dic. 2016 a las 16:59

Aquí dentro de 2nd foor loop, si encuentra algún elemento que sea menor que i (o el más pequeño), está haciendo una operación de intercambio que no se requiere aquí. En el orden de selección, debe obtener el elemento más pequeño de la matriz no ordenada e intercambiarlo con el elemento más a la izquierda, y ese elemento se convierte en parte de la matriz ordenada. Simplemente mantenga el intercambio fuera del segundo bucle interno para que solo se realice la operación de intercambio para el elemento más pequeño.

for(int i = 0; i < arrayToSort.length; i++){
    smallest = i;
    for(int j = i+1; j < arrayToSort.length; j++){
        if(arrayToSort[j] < arrayToSort[smallest]){
            smallest = j;
        }
    }
    if(smallest != i){
        int temp = arrayToSort[i];
        arrayToSort[i] = arrayToSort[smallest];
        arrayToSort[smallest] = temp;
    }
}
0
Bhagwati Malav 25 dic. 2016 a las 04:25

¡Hice esto cuando lo necesito en el proyecto universitario !

Referencias: algoritmo de selección con figura

selection sort

public static void selectionSort(int[] arr){  
        for (int i = 0; i < arr.length - 1; i++)  
        {  
            int index = i;  
            for (int j = i + 1; j < arr.length; j++){  
                if (arr[j] < arr[index]){  
                    index = j;//searching for lowest index  
                }  
            }  
            int smallerNumber = arr[index];   
            arr[index] = arr[i];  
            arr[i] = smallerNumber;  
        }  
    }  
2
Efrain Sanjay Adhikary 24 dic. 2016 a las 17:48