Modifier l'algorithme de tri d'insertion pour qu'il ne soit pas en augmentation

Question

Je me demande comment je peux changer la sortie du tri d'insertion en ordre croissant? Par exemple 537 serait 753. De plus, le temps d'exécution serait-il le même comparé à l'augmentation (à la fois le meilleur et le pire des cas)?

Pseudo Code:

INSERTION-SORT(A) 
    for j = 2 to A.length 
     key = A[j] 
     // Insert A[j] into the sorted sequence A[1..j] 
     i = j - 1 
     while i > 0 and A[i] > key 
      A[i +1] = A[i] 
      i = i - 1 
     A[i + 1] = key 

Answer 1

Runtime ne sera pas touché par le changement. Il serait préférable de dire décroissant au lieu de non croissante en parlant de chiffres en informatique. Augmenter serait croissant. Cela étant dit, voyez le code ci-dessous pour le changement que vous recherchez (faites particulièrement attention à la boucle while).

for j = 2 to A.length 
    key = A[j] 
    i = j - 1 
    while i > 0 and A[i] < key 
     A[i + 1] = A[i] 
     i = i - 1 
    A[i + 1] = key