Tri d'un tableau d'objets à l'aide des tris Insert et Selection

Question

J'ai besoin de créer une méthode pour trier un tableau d'objets. Je n'ai jamais fait ça, mais je dois le réviser pour mon cours. Je suis totalement perdu quand il s'agit de mettre en place une méthode de tri. J'ai besoin de trier en utilisant un tri d'insertion et sélection trier.

Ceci est mon code que j'ai jusqu'ici. Tout ce que je dois faire est d'appeler le sort() lorsque l'utilisateur souhaite le faire.

package citylisttest; 

public class CityList { 
    private City[] city; 
    private Integer numberOfCities; 

    public CityList (Integer cityListSize){ 
     this.city=new City[cityListSize]; 
     this.numberOfCities=0; 
    } 

    public void addCity(String city){ 
     this.city[this.numberOfCities]=new City(city); 
     this.numberOfCities++; 
    } 

    public String toString(){ 
     String cityDetails=new String(); 
     if (this.numberOfCities!=0){ 
      cityDetails+=String.format("%-15s\n","CITY"); 
      for(Integer i=0;i<this.numberOfCities;i++) { 
       cityDetails+=this.city[i]+"\n"; } 
     } 
     else 
      cityDetails+="City list is empty"; 
      return cityDetails; 
     } 

    public void sort(){ 

    } 
} 

Answer 1

D'abord, je vous suggère de renommer la variable city-cities puisqu'il est un tableau, et il détient plus d'une ville. En outre, envisagez également d'encapsuler vos données en marquant comme privée votre variable d'instance et en créant des getters et des setters respectivement.

Disons que vous voulez les trier par nombre de villes dans l'ordre croissant, votre méthode de tri doit avoir:

for (int i = 0; i < city.length - 1; i++) { 
    for (int j = i + 1; j < city.length; j++) { 
     if (city[i].getNumberOfCities() > city[j].getNumberOfCities()) { 
      City temp_city = city[i]; 
      city[i] = city[j]; 
      city[j] = temp_city; 
     } 
    } 
} 

J'espère que cela aide, mais vous pouvez implémenter l'interface Comparable ou créer une classe Comparator suivant this tutorial.

EDIT: Si vous voulez utiliser compareTo, pour trier les noms de ville dans l'ordre croissant:

for (int i = 0; i < city.length - 1; i++) { 
    for (int j = i + 1; j < city.length; j++) { 
     if (city[i].getName().compareTo(city[j].getName()) > 1) { 
      City temp_city = city[i]; 
      city[i] = city[j]; 
      city[j] = temp_city; 
     } 
    } 
} 

Assumming x et y sont des chaînes, x.compareTo(y) vous donne:

un nombre positif si x> y

zéro si x est égal à y

un nombre négatif si x

Answer 2

Documentation sur ce sujet est très commun à trouver sur Internet, mais "laissez-moi google que pour vous".

Je suggérerais de comprendre ce que vous voulez faire. Par conséquent, je vous suggère de jeter un oeil à la première, ce qui est un algorithme de tri:

https://en.wikipedia.org/wiki/Sorting_algorithm

puis, en particulier à l'algorithme de tri d'insertion:

https://en.wikipedia.org/wiki/Insertion_sort

ou le type de sélection :

https://en.wikipedia.org/wiki/Selection_sort

Quelqu'un peut gIV e vous la réponse ici, mais si vous ne luttez pas avec le problème, vous n'apprendrez pas à ce sujet et vous oublierez bientôt à ce sujet.

Hope it helps :)

Answer 3

Cela ressemble beaucoup à une question de devoirs, la pratique courante est de ne pas créer votre propre algorithme de tri.

Vous allez plus loin en essayant de concevoir votre propre solution, même si c'est naïf, que de copier/coller n'importe quelle réponse que vous trouverez ici.

Si vous voulez vraiment explorer les différentes solutions possibles (avec le code source Java), vous pouvez suivre cette applet et tutoriel:

https://thomas.baudel.name/Visualisation/VisuTri/

Answer 4

Voici les codes. Mais avant d'aller là-bas, je pense que vous devriez regarder ces deux vidéos:

InsertionSort: https://www.youtube.com/watch?v=DFG-XuyPYUQ&t=142s

SelectionSort: https://www.youtube.com/watch?v=f8hXR_Hvybo

public static void insertionSort(Object[] data) { 
// i denotes where the partition is 
for (int i = 1; i < data.length; i++) { 
// the key is to the right of the partition 
Object key = data[i]; 
int j = i - 1; // use j to scan left to insert key 
while (j >= 0 && ((Comparable) key).compareTo(data[j]) < 0) { 
// shift item right to make room 
data[j + 1] = data[j]; 
j--; 
} 
// Found the position where key can be inserted 
data[j + 1] = key; 
} 
} 

public static void selectionSort(Object[] data) { 
for (int i = 0; i < data.length - 1; i++) { 
// Find the index of the minimum item, starting at `i'. 
int minIndex = i; 
for (int j = i + 1; j < data.length; j++) { 
if (((Comparable) data[j]).compareTo(data[minIndex]) < 0) 
minIndex = j; 
// Exchange with the first item (at `i'), but only if different 
if (i != minIndex) { 
Object tmp = data[i]; 
data[i] = data[minIndex]; 
data[minIndex] = tmp; 
} 
} 
}