Recherche du kième élément le plus petit dans un tableau non trié

Question

J'essaie d'implémenter le pseudo-code suivant. Je dois le faire en utilisant uniquement des partitions logiques.

Procedure SELECT(k,S) 
{ if |S| =1 then return the single element in S 
    else { choose an element a randomly from S; 
      let S1,S2,and S3 be he sequences of elements in S 
      less than, equal to, and greater than m, respectively; 
     if |S1| >=k then return SELECT(k,S1) 
      else 
       if (|S1| + |S2| >=k then return m 
       else return SELECT(k-|S1|-|S2| , S3); 
     } 
} 

Voici ma tentative jusqu'à présent:

public static int select(int k, int[] s, int arrayLeft, int arrayRight) { 
    if (s.length == 1) { 
     return s[0]; 
    } else { 
     Random rand = new Random(); 
     int right = rand.nextInt(arrayRight) + arrayLeft; 
     int m = s[right]; 
     int pivot = partition(s, arrayLeft, right); // pivot = |s1| 
     if (pivot >= k) { 
      return select(k, s, arrayLeft, pivot - 1); 
     } else { 
      // Calculate |s2| 
      int s2Length = 0; 
      for (int i = pivot; s[i] == m; i++) { 
       s2Length++; 
      } 
      if (pivot + s2Length >= k) { 
       return m; 
      } else { 
       int s3Left = pivot + s2Length; 
       return select(k - pivot - s2Length, s, s3Left + 1, s.length); 
      } 
     } 
    } 
} 

// all elements smaller than m are to the left of it, 
// all elements greater than m are to the right of it 
private static int partition(int[] s, int left, int right) { 
    int m = s[right]; 
    int i = left; 
    for (int j = left; j <= right - 1; j++) { 
     if (s[j] <= m) { 
      swap(s, i, j); 
      i++; 
     } 
    } 
    swap(s, i, right); 
    return i; 
} 

private static void swap(int[] s, int i, int j) { 
    int temp = s[i]; 
    s[i] = s[j]; 
    s[j] = temp; 
} 

Ma méthode select ne renvoie pas les réelles kième plus petit élément. La méthode de partition ne fait que son travail correctement sur les éléments plus petits que m. Sur la partie du tableau à droite de m, il y a des éléments de n'importe quelle valeur. Comment puis-je réparer ça? Toutes les solutions que j'ai vues en ligne ressemblent à ma méthode. Toute aide est appréciée!

Answer 1

Je ne suis pas sûr des détails de la façon dont votre code était censé fonctionner, mais je pense avoir repéré quelques points suspects.

D'abord je pense que vous devriez être précis sur les arguments valides pour votre méthode et comment il utilise arrayLeft et arrayRight. Écrivez un commentaire Javadoc et énoncez ceci. Il sera beaucoup plus facile pour vous-même et quiconque d'argumenter sur ce qui est correct et incorrect dans le code.

Ce qui ne va pas:

if (s.length == 1) { 

Vous passez le même tableau dans tous vos appels récursifs, donc si elle n'a pas la longueur 1 dès le départ (un cas trivial), il ne sera jamais avoir une longueur 1. Utilisez plutôt arrayLeft et arrayRight pour déterminer le nombre d'éléments à prendre en compte.

Cette ligne ne semble pas correcte:

 int right = rand.nextInt(arrayRight) + arrayLeft; 

Si arrayLeft est 10 et arrayRight 12, il peut produire jusqu'à 21. Je l'ai fait observer une fois ArrayIndexOutOfBoundsException dans la ligne suivante parce right pointe en dehors du tableau.

Le commentaire de cette ligne est incorrecte et peut vous conduire à de mauvais arguments sur le code:

 int pivot = partition(s, arrayLeft, right); // pivot = |s1| 

Le pivot retourné de partition() est l'index m après réordonnancement. Je pense que la déclaration correcte est pivot == arrayLeft + |s1|. S'il vous plaît vérifier vous-même.

Je crois en outre que vous ne devriez pas passer right comme dernier argument dans l'appel ci-dessus, mais arrayRight. Cette erreur peut être la cause de votre observation que partition() laisse toutes les valeurs à droite de m.

Vous pouvez risquer un ArrayIndexOutOfBoundsException ici aussi:

  for (int i = pivot; s[i] == m; i++) { 

Vous devez ajouter une condition supplémentaire comme i <= arrayRight ou i < s.length.

Enfin, cela semble mal à mes yeux:

   return select(k - pivot - s2Length, s, s3Left + 1, s.length); 

Je pense:

   return select(k - pivot - s2Length, s, s3Left, arrayRight); 

Mais s'il vous plaît vérifier avec vos propres connaissances. Je suis particulièrement dans le doute sur arrayRight.