Problème de programmation de tri de partition

Question

J'ai besoin d'un algorithme pour sélectionner k la plus grande ou la plus petite valeur. Les valeurs seront ints. Mon instructeur m'a dit d'utiliser un algorithme de partition modifié pour trouver la k la plus grande ou la plus petite valeur. Des pensées?

Answer 1

Voici une description de l'algorithme quickselect. Je suppose que vous voulez trouver le k la plus petite valeur.

1. Prenez le premier élément de votre tableau. Ce sera votre pivot. Gardez une trace de sa position.

2. Partitionnez la baie en fonction de ce pivot. Les éléments plus petits que votre pivot vont avant votre pivot dans le tableau; plus grand, après votre pivot. (Cette étape déplacera votre pivot.) Gardez une trace de sa position dans votre matrice.)

3. Vous savez maintenant que votre pivot est plus grand que pivot_position nombre d'éléments. Par conséquent, votre pivot est le (pivot_position + 1) le plus petit élément.

   • Si k est égal à pivot_position + 1, alors vous avez trouvé votre k e valeur la plus petite. Félicitations, renvoyez pivot_position comme position de cette valeur dans le tableau.

   • Si k est inférieur à pivot_position + 1, vous voulez une valeur plus petite que votre pivot. Regardez dans la partie du tableau avant votre pivot pour le k la plus petite valeur.

   • Si k est supérieur à pivot_position + 1, vous voulez une valeur qui est plus grand que votre pivot. Regardez dans la partie du tableau après votre pivot pour la plus petite valeur * k - (pivot_position + 1) * (puisque cette partie du tableau exclut les plus petites valeurs (pivot_position + 1)).

Puisque vous utilisez C++, vous devriez probablement mettre en œuvre vos fonctions comme suit:

int select(int *array, int left, int right, int k); 
int partition(int *array, int left, int right, int pivot_position); 

select prend votre tableau, gauche et droite limites, et votre k. Pour clarifier, array[left] sera le premier élément; array[right] sera le dernier; right - left + 1 sera la longueur du tableau. select renvoie la position du k le plus petit élément.

partition prend votre tableau, les limites gauche et droite, et la position de départ de votre pivot. Il est sûr de simplement passer 0 pour pivot_position à chaque fois, ce qui signifie que vous voulez utiliser le premier élément du tableau comme pivot. (Dans une variante appelée sélection rapide aléatoire, vous choisissez un pivot_position aléatoire.) partition renvoie la position du pivot après que vous avez terminé de déplacer les choses.

Answer 2

La STL a une fonction partial_sort qui va trier les k premiers éléments d'une séquence, et vous permettant de saisir cet élément avec une simple recherche. En d'autres termes, cherchez std::partial_sort et le reste sera évident. Il existe également une fonction nth_element dans la liste STL. Je suis sûr que vous pouvez comprendre comment l'utiliser.