En küçük sayıyı bulmak için hızlı seçim algoritmasının uygulanması

Question

Şu anda hızlı seçim algoritmasını kullanarak bir dizinin en küçük sayısını bulmak için bir program üzerinde çalışıyorum. Ben bitirdim ve çalışır, ancak her seferinde doğru sonuç vermez.

İşte benim kod (benim partition veya swap algoritmayı içermiyordu, onlar doğru konum oldukça eminim):

/* 
inputs... 
*A: pointer to array 
n: size of array 
k: the item in question 
*/ 
int ksmallest(int *A, int n, int k){ 

    int left = 0; 
    int right = n - 1; 
    int next = 1; 

    return quickselect(A, left, right, k); 
} 

int quickselect(int *A, int left, int right, int k){ 

    //p is position of pivot in the partitioned array 
    int p = partition(A, left, right); 

    //k equals pivot got lucky 
    if (p - 1 == k - 1){ 
     return A[p]; 
    } 
    //k less than pivot 
    else if (k - 1 < p - 1){ 
     return quickselect(A, left, p - 1, k); 
    } 
    //k greater than pivot 
    else{ 
     return quickselect(A, p + 1, right, k); 
    } 
} 

Her şey iyi derler. Sonra şu dizide programı kullanmaya çalıştı: Eğer en küçük 1th öğe üzerinde düzgün çalıştı görebileceğiniz gibi

> kthsm 2 
4 
> kthsm 1 
1 
> kthsm 3 
2 

ancak diğerleri üzerinde başarısız oldu:

[1,3,8,2,4,9,7] Bunlar benim sonuçlarını idi. Sorun ne olabilir? Endekslemenin kapalı olduğunu tahmin ettim ama tam olarak emin değilim.

DÜZENLEME: istendiği gibi, aşağıda benim bölümü ve takas kodunu eklendi: En bölüm fonksiyonunda

int partition(int *A, int left, int right){ 

    int pivot = A[right], i = left, x; 

    for (x = left; x < right - 1; x++){ 
     if (A[x] <= pivot){ 
      swap(&A[i], &A[x]); 
      i++; 
     } 
    } 

    swap(&A[i], &A[right]); 
    return i; 
} 

//Swaps 
void swap(int *a, int *b){ 
    int temp = *a; 
    *a = *b; 
    *b = temp; 
} 

Answer 1

döngü koşulu, doğru değil x < x < doğru olmalıdır - 1.

Ayrıca quickselect ifadelerinde if ifadelerinde, p-1'un her ikisini de kullanmalısınız. p zaten bir indekstir ve k'yi 1 ile azaltarak, onu bir indekse (bir sıradan ziyade) çevirirsiniz. Bir kere daha azaltmaya gerek yok.

int partition(int *A, int left, int right){ 
    int pivot = A[right], i = left, x; 

    for (x = left; x < right; x++){ 
     if (A[x] <= pivot){ 
      swap(&A[i], &A[x]); 
      i++; 
     } 
    } 

    swap(&A[i], &A[right]); 
    return i; 
} 


int quickselect(int *A, int left, int right, int k){ 

    //p is position of pivot in the partitioned array 
    int p = partition(A, left, right); 

    //k equals pivot got lucky 
    if (p == k-1){ 
     return A[p]; 
    } 
    //k less than pivot 
    else if (k - 1 < p){ 
     return quickselect(A, left, p - 1, k); 
    } 
    //k greater than pivot 
    else{ 
     return quickselect(A, p + 1, right, k); 
    } 
} 

İşte bir çalışma örneği. http://ideone.com/Bkaglb