Tri par sélection Java et analyse

Question

J'ai écrit un code de tri de sélection en java. Je connais son algorithme très élémentaire, mais depuis que j'apprends, je voulais donc votre avis sur la qualité du code. Veuillez consulter le code: package selection_sort;

import java.util.Scanner;

public class SelectionSort {

int [] arrayToBeSorted;
Scanner scan=new Scanner(System.in);


SelectionSort(){
    System.out.println("Enter the number of elements");
    int total=scan.nextInt();
    this.arrayToBeSorted=new int[total];
    for(int i=0;i<total;i++) {
        System.out.println("Enter the "+i+" number of elements");
        this.arrayToBeSorted[i]=scan.nextInt();
    }
    
}

public void Sort() {
    int minIndex,min;
    boolean swapRequired=false;
    for(int i=0;i<arrayToBeSorted.length;i++) {
        minIndex=i;
        min=this.arrayToBeSorted[i];
        for(int j=i+1;j<this.arrayToBeSorted.length;j++) {
            if(this.arrayToBeSorted[j]<min) {
                min=this.arrayToBeSorted[j];
                minIndex=j;
                swapRequired=true;
            }
        }
        if(swapRequired) {
            swap(i,minIndex);
        }
                    
    }
    
    for(int x:this.arrayToBeSorted) {
        System.out.print(x+" ");
    }
        
    }

public void swap(int i,int j) {
    
    //System.out.println("swap called, pos="+i+"and minindex="+j);
    int temp=this.arrayToBeSorted[i];
    this.arrayToBeSorted[i]=this.arrayToBeSorted[j];
    this.arrayToBeSorted[j]=temp;
    
    //System.out.println("------------");
    
}
public static void main(String[] args) {
    SelectionSort s=new SelectionSort();
    s.Sort();
}

}

Aussi à propos de l'analyse, comme la sélection est O (n2), est-ce parce que j'utilise une boucle imbriquée pour. Existe-t-il un outil qui nous renseigne sur la complexité du code. Merci d'avance et soyez patient si c'est très naïf

Answer 1

int [] arrayToBeSorted;
Scanner scan=new Scanner(System.in);

Sans aucun modificateur, les membres et les fonctions le sont package-private. Ce qui signifie qu'ils sont accessibles à partir du même package, mais pas par des instances étendant la classe. C'est une chose extrêmement étrange, en fait, quand on la regarde d'un point de vue orienté objet. Vous voulez les faire soit private, ou si les classes étendant devrait pouvoir y accéder, protected.

Il en va de même pour le constructeur.

---

    System.out.println("Enter the number of elements");
    int total=scan.nextInt();
    this.arrayToBeSorted=new int[total];

Vous pouvez utiliser un List/ ArrayListau lieu d'un tableau, ce qui signifie que vous pouvez recevoir autant de numéros des utilisateurs qu'ils le souhaitent sans avoir à spécifier le nombre au préalable. Une entrée vide pourrait être utilisée pour déclarer la fin de la liste. Cependant, cela présente l'inconvénient que vous devez utiliser à la Integerplace int, il est donc difficile de dire ce qui est mieux. Cela présente également l'inconvénient que la détection d'une entrée vide est facilement disponible à partir de Scanner, comme vous devez l'utiliser nextLinepour cela, avec une conversion manuelle en int.

Vous pouvez également émuler un Listen développant dynamiquement le tableau. Soit en le faisant pour chaque élément, les performances n'ont pas d'importance dans ce cas d'utilisation, soit en doublant la taille si nécessaire.

---

this.arrayToBeSorted=new int[total];

Vous n'avez besoin du thismodificateur que si vous avez une variable du même nom dans la même portée, par exemple dans un constructeur:

public ValueContainer(int value) {
    this.value = value;
}

Il est courant d'omettre thissi cela n'est pas nécessaire. Si jamais vous vous trouvez dans la situation où il est difficile de savoir si une instance, une variable statique ou locale est utilisée, vous avez quand même fait quelque chose de mal.

---

for(int i=0;i<total;i++) {

Je suis un partisan très persévérant de l'utilisation de «vrais» noms pour les variables dans les boucles.

for (int counter = 0; counter < total; counter++) {
// or
for (int index = 0; index < total; index++) {

---

public void Sort() {

Les conventions de dénomination Java stipulent que les méthodes / fonctions doivent être lowerCamelCase.

---

int minIndex,min;

Personnellement, j'éviterais de déclarer plusieurs variables sur la même ligne. Il est facile de rater la déclaration.

---

boolean swapRequired=false;

C'est un excellent exemple d'un bon nom pour une variable, merci!

---

    for(int x:this.arrayToBeSorted) {
        System.out.print(x+" ");
    }

C'est malheureusement un mauvais nom pour une variable. Utilisez uniquement "x", "y" et "z" lorsque vous travaillez avec des cotes. «valeur» ou «nombre» serait un grand nom ici.

---

Dans l'ensemble, cela semble valable. Cependant, je ne l'ai pas exécuté pour tester la fonctionnalité. Ce que vous devez changer, c'est que vous avez une logique dans le constructeur. Personne ne s'attend à ce que les constructeurs soient remplis de logique, car vous ne pouvez pas voir l'intention de la logique de leur part. Ils ne devraient pas faire autant que possible. Cela signifie que vous devez déplacer la logique dans sortou, mieux encore, dans main. Votre trieur ne devrait pas du tout se préoccuper de l'entrée, il devrait uniquement être concerné par le tri des valeurs, idéalement, et une autre classe ( InputReader?) Devrait être concernée par l'obtention de l'entrée. Donc, ce que vous pourriez faire est quelque chose comme ceci:

public static final void main(String[] args) {
    InputReader inputReader = new InputReader();
    
    int[] values = inputReader.readValues();
    
    Sorter sorter = new Sorter();
    sorter.sort(value);
    
    // TODO Print sorted output.
}

Cela a également l'avantage que vous n'avez pas du tout besoin de conserver l'état Sorter, ce qui le rendrait thread-safe par défaut.