Algorithme RadixSort

Question

J'ai une question concernant l'algorithme de tri radix. J'ai trouvé cette implémentation:

import java.lang.*; 
import java.util.LinkedList; 
import java.util.Queue; 
import java.io.*; 

public class RadixSort { 

    public static void radixSort(int[] data) { 
     int z = 0 ; 
     boolean flag = true; 
     int divisor = 1; 
     Queue[] buckets = new Queue[10]; 
     for (int i = 0; i < 10; i++) 
      buckets[i] = new LinkedList(); 

     while (flag) { 
      flag = false; 
      // first copy the values into buckets 
      for (int i = 0; i < data.length; i++) { 
       int hashIndex = (data[i]/divisor) % 10; 
       if (hashIndex > 0) 
        flag = true; 
       ((LinkedList) buckets[hashIndex]).addLast(new Integer(data[i])); 
      } 
      // then copy the values back into vector 
      divisor *= 10; 
      int i = 0; 

      for (int j = 0; j < 10; j++) { 
       while (!buckets[j].isEmpty()) { 
        Integer ival = (Integer) ((LinkedList) buckets[j]) 
          .getFirst(); 
        ((LinkedList) buckets[j]).removeFirst(); 
        data[i++] = ival.intValue(); 
       } 
      } 
      z=z+1 ; 

      System.out.print("Durchlauf " + z + " : "); 
      for (int m = 0; m < data.length; m++){ 

       System.out.print(data[m] + " "); 


      } 
      System.out.println(); 
     } 
    } 

    public static void main(String[] args) { 
     int i; 
     int[] arr = new int[15]; 
     System.out.print("original: "); 
     for (i = 0; i < arr.length; i++) { 
      arr[i] = (int) (Math.random() * 1024); 
      System.out.print(arr[i] + " "); 

     } 
     System.out.println(); 
     System.out.println(); 
     radixSort(arr); 


    } 
} 

Je veux comprendre où le flux de boucle est défini. Si j'ai un nombre de longueur 4, alors la boucle traverse la quatrième. Où est-ce défini?

Answer 1

Je ne suis pas sûr de ce genre d'explication que vous cherchez, mais j'espère que cela aide:

Les pistes en boucle while extérieures tout en flag est vrai. Le flag sera faux après la première exécution sauf si hashIndex > 0 au moins une fois lorsque vous affectez des valeurs dans des compartiments dans votre première boucle for.

Ensuite, vous avez un autre for (int j = 0; j < 10; j++) qui sera exécuté 10 fois pour chaque valeur de j. La boucle while imbriquée while (!buckets[j].isEmpty()) s'exécute autant de fois qu'elle le doit, pour chaque valeur de j.