Sélection Trier avec ArrayList

Question

J'essaye de coder un tri de sélection en utilisant ArrayList. Mon programme m'oblige à créer un tableau de taille 20 et à le peupler avec des entiers aléatoires compris entre 1 et 1000 (aucune entrée utilisateur ou code rigide). La sortie nécessitera l'affichage de la liste originale des entiers non triés et l'affichage de chaque passage de l'algorithme de tri sur une ligne distincte.

J'ai essayé de créer une méthode pour le tri par sélection, donc c'est là que je suis bloqué parce que je ne suis pas sûr de savoir comment implémenter le code dans ma méthode principale.

Un exemple de la façon dont je veux que ma sortie de sortir comme il est indiqué ci-dessous (bien qu'il montre seulement 5 entiers quand je suis en train de faire 20):

Liste non triée: 3 68 298 290 1
col 1: 1 68 298 290 3
col 2: 1 3 298 290 68
col 3: 1 3 68 290 298
col 4: 1 3 68 290 298

// Used to capture keyboard input 
import java.util.*; 

// Our class called SelectionSort 
public class SelectionSort { 

// Create doSelectionSort method 
public static int[] doSelectionSort(int[] arr) { 
    for (int i = 0; i < arr.length - 1; i++) { 
     int pos = i; 
     // find position of smallest num between (i + 1)th element and last element 
     for (int j = i + 1; j <= arr.length; j++) { 
      if (arr[j] < arr[pos]) 
       pos = j; 

      // Swap min (smallest num) to current position on array 
      int min = arr[pos]; 
      arr[pos] = arr[i]; 
      arr[i] = min; 
     } 
    } 
    return arr; 
} 

// Main method 
public static void main(String[] args) { 
    ArrayList<Integer> array = new ArrayList<Integer>(); // Declare and instantiate a new ArrayList object 
    Scanner userChoice = new Scanner(System.in); // User input for quitting program 
    String choice = ""; // Will hold user choice to quit program 
    boolean inputFlag = false; // True if input is valid, false otherwise 

    // Repeat program until user chooses to quit 
    while (inputFlag = true) { 
     System.out.print("\nWould you like to continue the program? (Y/N): "); 
     choice = userChoice.nextLine(); 
     if (choice.equalsIgnoreCase("Y")) { 
      try { 
       /* Create an array of size 20 and populate it with random integers between 1 and 1000. 
       Do not ask user for the numbers and do not hard code them */ 
       for (int i = 0; i < 20; i++) { 
        int integer = (int)(1000.0 * Math.random()); 
        array.add(integer); 
       } 
       System.out.print("\nUNSORTED LIST: "); 

       //Display the 20 size of the unsorted ArrayList 
       for (int i = 0; i < array.size() - 1; i++) { 
        System.out.print(array.get(i) + ", "); 
       } 
       // Shows very last integer with a period 
       System.out.print(array.get(array.size() - 1) + "."); 
       System.out.println(); 
      } 

      catch (IndexOutOfBoundsException e) { 
       System.out.println("\nThere is an out of bounds error in the ArrayList."); 
      } 
      // Display each pass of the sorting algorithm on a separate line 
      for (int i = 1; i < array.size(); i++) { 
       System.out.print("PASS " + i + ": "); 
       for (int arr2:array) { 
        System.out.print(arr2 + ", "); 
       } 
       System.out.print(array.get(array.size() - 1) + ".\n"); 
      } 
     array.clear(); 
     } 
     else if (choice.equalsIgnoreCase("N")) { 
      break; 
     } 
     // Error message when inputting anything other than Y/N 
     else { 
      System.out.println("\nERROR. Only Y, y, N, or n may be inputted."); 
      System.out.println("Please try again."); 
     } 
    } 
} 
} 

Je rencontre également des difficultés pour supprimer le dernier numéro de chaque passage parce qu'il est affiché deux fois ... vous avez une idée de ce que je devrais faire? Désolé pour la noob-ness de mon codage, j'essaie toujours de le comprendre.

Answer 1

J'ai corrigé votre code, cela devrait fonctionner maintenant.

// Used to capture keyboard input 
import java.util.*; 

// Our class called SelectionSort 
public class SelectionSort { 

    // Create doSelectionSort method 
    public static void doSelectionSort(ArrayList<Integer> arr) { 
     for (int i = 0; i < arr.size(); i++) { 
      // find position of smallest num between (i + 1)th element and last element 
      int pos = i; 
      for (int j = i; j < arr.size(); j++) { 
       if (arr.get(j) < arr.get(pos)) 
        pos = j; 
      } 
      // Swap min (smallest num) to current position on array 
      int min = arr.get(pos); 
      arr.set(pos, arr.get(i)); 
      arr.set(i, min); 
      printOut(i + 1, arr); 
     } 
    } 

    private static void printOut(int pass, ArrayList<Integer> array) { 
     System.out.print("PASS " + pass + ": "); 
     for (int i = 0; i < array.size() - 1; i++) { 
      System.out.print(array.get(i) + ", "); 
     } 
     // Shows very last integer with a period 
     System.out.print(array.get(array.size() - 1) + "."); 
     System.out.println(); 
    } 

    // Main method 
    public static void main(String[] args) { 
     ArrayList<Integer> array = new ArrayList<Integer>(); // Declare and instantiate a new ArrayList object 
     Scanner userChoice = new Scanner(System.in); // User input for quitting program 
     String choice = ""; // Will hold user choice to quit program 
     boolean inputFlag = false; // True if input is valid, false otherwise 

     // Repeat program until user chooses to quit 
     while (inputFlag = true) { 
      System.out.print("\nWould you like to continue the program? (Y/N): "); 
      choice = userChoice.nextLine(); 
      if (choice.equalsIgnoreCase("Y")) { 
       try { 
        /* Create an array of size 20 and populate it with random integers between 1 and 1000. 
        Do not ask user for the numbers and do not hard code them */ 
        for (int i = 0; i < 20; i++) { 
         int integer = (int)(1000.0 * Math.random()); 
         array.add(integer); 
        } 
        System.out.print("\nUNSORTED LIST: "); 

        //Display the 20 size of the unsorted ArrayList 
        for (int i = 0; i < array.size() - 1; i++) { 
         System.out.print(array.get(i) + ", "); 
        } 
        // Shows very last integer with a period 
        System.out.print(array.get(array.size() - 1) + "."); 
        System.out.println(); 
        doSelectionSort(array); 
       } 

       catch (IndexOutOfBoundsException e) { 
        System.out.println("\nThere is an out of bounds error in the ArrayList."); 
       } 
      } 
      else if (choice.equalsIgnoreCase("N")) { 
       break; 
      } 
      // Error message when inputting anything other than Y/N 
      else { 
       System.out.println("\nERROR. Only Y, y, N, or n may be inputted."); 
       System.out.println("Please try again."); 
      } 
     } 
    } 
} 

Answer 2

Votre méthode doSelectionSort semble correcte, mais elle fait tout le tri. Si vous voulez afficher chaque itération, il vous suffit d'ajouter une ligne:

public static int[] doSelectionSort(int[] arr) { 
    for (int i = 0; i < arr.length - 1; i++) { 
     int pos = i; 
     // find position of smallest num between (i + 1)th element and last element 
     for (int j = i + 1; j <= arr.length; j++) { 
      if (arr[j] < arr[pos]) 
       pos = j; 

      // Swap min (smallest num) to current position on array 
      int min = arr[pos]; 
      arr[pos] = arr[i]; 
      arr[i] = min; 
     } 
     System.out.println("Pass "+pos+" : "+arr); 
    } 
    return arr; 
}