Zrozumienie algorytmu QuickSelect

Question

Przeglądałem różne samouczki i artykuły omawiające quicksort i szybkie wybieranie, jednak moje rozumienie ich jest wciąż niepewne.

Biorąc pod uwagę tę strukturę kodu, muszę być w stanie zrozumieć i wyjaśnić, jak działa funkcja szybkiego wyboru.

// return the kth smallest item 
int quickSelect(int items[], int first, int last, int k) { 
    int pivot = partition(items, first, last); 
    if (k < pivot-first) { 
     return quickSelect(items, first, pivot, k); 
    } else if (k > pivot) { 
     return quickSelect(items, pivot+1, last, k-pivot); 
    } else { 
     return items[k]; 
    } 
} 

Potrzebuję trochę pomocy ze uszkodzi do pseudo-kodu, a ja nie zostały dostarczone z kodem funkcji partycji, chciałbym, aby zrozumieć, co to nie ze względu na funkcję quickselect dostarczone.

Wiem, jak działa quicksort, ale nie po prostu szybko. Podany przeze mnie kod jest przykładem na to, jak sformatować szybki wybór.

EDIT: Skorygowana kod jest

int quickSelect(int items[], int first, int last, int k) 
{ 
    int pivot = partition(items, first, last); 
    if (k < pivot-first+1) 
    { //boundary was wrong 
     return quickSelect(items, first, pivot, k); 
    } 
    else if (k > pivot-first+1) 
    {//boundary was wrong 
     return quickSelect(items, pivot+1, last, k-pivot); 
    } 
    else 
    { 
     return items[pivot];//index was wrong 
    } 
} 

Courtesty: @Haitao

Answer 1

Ważną częścią jest w szybkie select partition. Pozwól mi to najpierw wyjaśnić.

Partycja w szybkim wyborze wybiera pivot (element losowy lub pierwszy/ostatni). Następnie zmienia kolejność listy w taki sposób, że wszystkie elementy mniej niż pivot znajdują się po lewej stronie osi obrotu, a inne po prawej. Następnie zwraca indeks elementu pivot.

Teraz znajdujemy kogo najmniejszego elementu. Po przypadkach partycji są to:

1. k == pivot. Wtedy już znalazłeś kogo najmniejszego. Dzieje się tak, ponieważ sposób działania partycji działa. Są dokładnie takie elementy, które są mniejsze niż element kth.
2. k < pivot. Następnie kth najmniejszy znajduje się po lewej stronie pivot.
3. k > pivot. Następnie kth najmniejszy znajduje się po prawej stronie osi obrotu. Aby go znaleźć, musisz znaleźć najmniejszy numer po prawej.

Answer 2

Podział jest dość prosty: przestawia elementy tak, aby mniej niż wybrany czop znajdował się w niższych indeksach w macierzy niż w osi głównej, a większe od osi obrotu w wyższych indeksach w macierzy.

Mówiłem o reszcie w previous answer.

Answer 3

btw, Twój kod ma kilka błędów ..

int quickSelect(int items[], int first, int last, int k) { 
    int pivot = partition(items, first, last); 
    if (k < pivot-first+1) { //boundary was wrong 
     return quickSelect(items, first, pivot, k); 
    } else if (k > pivot-first+1) {//boundary was wrong 
     return quickSelect(items, pivot+1, last, k-pivot); 
    } else { 
     return items[pivot];//index was wrong 
    } 
} 

Answer 4

int quickSelect(int A[], int l, int h,int k) 
{ 
     int p = partition(A, l, h); 
     if(p==(k-1)) return A[p]; 
     else if(p>(k-1)) return quickSelect(A, l, p - 1,k); 
     else return quickSelect(A, p + 1, h,k); 

} 

// funkcja partycji samo jak Quicksort

Answer 5

można znaleźć quickSelect here stosując 3-way partycjonowania.

Kod jest napisany w Scala. Dodatkowo dodam więcej algorytmów i struktur danych w mojej podróży do opanowania tematu.

Można również zauważyć, że istnieje funkcja mediany dla tablic z nieparzystą liczbą elementów zaimplementowanych przy użyciu funkcji quickSelect.

edit: Wymagane jest, aby przetasować tablicę zagwarantować liniową średni czas przebiegu

Answer 6

int partition(vector<int> &vec, int left, int right, int pivotIndex) 
{ 
     int pivot = vec[pivotIndex]; 
     int partitionIndex = left; 

     swap(vec[pivotIndex],vec[right]); 
     for(int i=left; i < right; i++) { 
       if(vec[i]<pivot) { 
         swap(vec[i],vec[partitionIndex]); 
         partitionIndex++; 
       } 
     } 
     swap(vec[partitionIndex], vec[right]); 

     return partitionIndex; 
} 

int select(vector<int> &vec, int left, int right, int k) 
{ 
     int pivotIndex; 
     if (right == left) { 
       return vec[left]; 
     } 
     pivotIndex = left + rand() % (right-left); 

     pivotIndex = partition(vec,left,right,pivotIndex); 
     if (pivotIndex == k) { 
       return vec[k]; 
     } else if(k<pivotIndex) { 
       /*k is present on the left size of pivotIndex*/ 
       return partition(vec,left,pivotIndex-1, k); 
     } else { 
       /*k occurs on the right size of pivotIndex*/ 
       return partition(vec, pivotIndex+1, right, k); 
     } 
     return 0; 
}