InsertionSort Ordre décroissant java

Question

Ceci est le code pour faire un insertionSort dans l'ordre croissant. J'essaye de changer le code afin qu'il puisse faire l'ordre décroissant. Mais chaque fois que je change quelque chose, c'est pire. Quelqu'un peut-il m'indiquer la bonne direction?

public static void insertionSort(Comparable[] list) 
{ 
    for (int index = 0; index < list.length; index++) 
    { 
    Comparable key = list[index]; 
    int position = index; 

    // Shift larger values to the right 
    while (position > 0 && key.compareTo(list[position-1]) < 0) 
    { 
     list[position] = list[position-1]; 
     position--; 
    } 

    list[position] = key; 
    } 
} 

Answer 1

code de fonction Votre insertionSort() actuelle est correcte pour le tri dans l'ordre croissant. C'est une bonne base pour commencer.

Je ne sais pas quels changements vous avez essayés pour faire une version décroissante. S'il vous plaît inclure cette information la prochaine fois, parce que nous autrement, nous ne pouvons pas vous dire pourquoi cela n'a pas fonctionné.

Pour changer votre fonction pour trier par ordre décroissant, littéralement changer un seul caractère:

// Sort-ascending version (current) 
key.compareTo(list[position-1]) < 0 

// Sort-descending version (proposed 
key.compareTo(list[position-1]) > 0 

J'ai testé ce changement et a confirmé cela fonctionne. J'espère que cela t'aides!

Answer 2

Je ne vois pas de gros problèmes avec votre code. Ce que je ferais, c'est que je surchargerais cette fonction avec un paramètre supplémentaire: un Comparator (docs here) qui est utilisé à la place du compareTo naturel.

d'inspiration Regardons les this (Collections en java)

static <T> void sort(List<T> list, Comparator<? super T> c) trie la liste spécifiée selon l'ordre induite par le comparateur spécifié.

Pour obtenir l'ordre décroissant, vous pouvez appeler votre fonction avec quelque chose comme ce qui suit:

insertionSort(A, 
       new Comparator<Integer>() { 

      @Override 
      public int compare(Integer o1, Integer o2) { 
       return o2.compareTo(o1) ; 
      }} 
     );