Kth plus petit algorithme d'élément

Question

J'écris un algorithme qui divise et conquiert un tableau non trié d'entiers pour trouver le kth plus petit élément. Lors du test de mon programme, quelques-unes de mes sorties sont erronées. Voici le code:

public class kthsmallest { 

public static final int MaxSize = 500; 

public static int find_kth_smallest(int[] A, int n, int k) 
{ 
     return quicksort(A, n, k, 0, n-1); 
} 

public static int quicksort(int[] A, int n, int k, int low, int high){ 
int i = low; 
int j = high; 
int position = low + (high-low)/2; 
int pivot = A[position]; 

while (i <= j){ 
    while(A[i] < pivot) 
     i++; 

    while(A[j] > pivot) 
     j--; 

    if (i <= j){ 
     int temp = A[i]; 
     A[i] =A[j]; 
     A[j] = temp; 
     i++; 
     j--; 
    } 
} 

// 
if (position + 1 > k){ 
    return quicksort(A, n, k, low, position-1); 
} else if (position + 1 < k){ 
    return quicksort(A, n, k, position+1, high); 
} else 
    return A[position]; 

Si quelqu'un peut voir quelque chose de mal avec cet algorithme, s'il vous plaît faites le moi savoir. J'ai débogué pendant des heures. Merci.

Answer 1

Vous allez vous tromper pour l'entrée 1,2,3,20,4,5,6 et la recherche du 6ème élément. C'est parce que dans ce cas vous devrez échanger un élément plus d'une fois et il me semble que vous ne le faites jamais. Vous allez échanger 20 et 6, mais après cela, vous augmenterez i et donc ne changera jamais 6 à nouveau alors que vous devriez effectivement. 6 est la bonne réponse. Je ne suis pas sûr de la valeur que vous trouverez, mais ce ne sera pas 6.

Plusieurs problèmes peuvent également survenir en raison d'éléments équivalents au pivot. Essayez d'ajouter des contrôles spéciaux pour ces éléments.