Essayer de comprendre le code de tri seau

Question

J'ai trois questions sur le code suivant:

static void funct(int[] list) { 
    final int N = 20; 

    java.util.ArrayList[] buckets = new java.util.ArrayList[N]; 
    for(int i = 0; i< list.length; i++) { 
    int key = list[i]; 
    if(buckets[key] = null) 
      buckets[key].add(list[i]); 
    } 
    int k = 0 
    for(int i = 0; i <buckets.length; i++) { 
     if(buckets[i] != null) { 
      for(int j = 0; j< buckets[i].size(); j++) 
       list[k++] = (Integer)buckets[i].get(j); 
     } 
    } 

}

1. L'algorithme a une lacune majeure, est-ce que cela ne fonctionnera que jusqu'à 20 éléments et que cela a une faible complexité?

2. Le point du code est de trier une liste d'éléments - ils sont placés dans un tableau, puis mis dans des compartiments, puis ils sont mis à nouveau des baquets dans le tableau?

3. Heres celui sur lequel je suis perplexe, comment modifieriez-vous la méthode afin que vous puissiez passer un tableau qui contient des objets d'une autre classe au lieu d'entiers?

Answer 1

répondre à vos questions:

1. Voilà deux lacunes. Peu importe la complexité pour un moment; considérez comment il est censé fonctionner pour plus de 20 éléments. Pour un tri par compartiment, l'idée est de sélectionner un compartiment en fonction de la position de l'élément dans l'ensemble des éléments. Le moyen le plus simple de faire cela sur un ordinateur avec des entiers binaires est de sélectionner les premiers bits (les bits les plus significatifs) du nombre, et d'utiliser un nombre de buckets de puissance de deux, tels que 16 ou 32. Vous pouvez obtenir les bits les plus significatifs (et donc comprendre le seau) avec une opération et (&). Vous pouvez ensuite utiliser les bits pour sélectionner le bucket directement. L'idée derrière le tri par seau est d'utiliser un élément de tri de base pour un passage initial sur l'entrée, puis d'utiliser un tri différent (ou un tri de base itéré) sur les petits compartiments, qui peuvent être petits et plus facilement triés, ou la concaténation de tous les compartiments (tels que retour dans le tableau) peut être triée avec une complexité moindre.

2. Le tri par godet est basé sur la connaissance de la plage totale d'entrée, afin que vous puissiez diviser cette plage en segments et ensuite catégoriser les entrées individuellement. La façon la plus simple de le faire est de savoir si l'entrée est numérique. Si l'ordre dans l'entrée est seulement relatif, et il n'y a aucun absolu connu et aucun moyen facile de déterminer où dans la gamme totale un élément est, alors le tri de baquet n'est pas approprié.

Answer 2

Ceci est une bonne question de devoirs. Beaucoup de questions sont subjectives et dépendent presque certainement de votre travail de classe.

Je vous suggère de faire un coup vous-même parce que les leçons en classe donneront une meilleure idée de ce que l'instructeur recherche que des réponses ici. En outre, si quelqu'un à l'extérieur d'une salle de classe voyait cela, la réponse serait d'utiliser simplement le tri en réseau intégré et de jeter cette poubelle!