Algorithme de partition rapide

void partition(int *a, int size) { int pivot = a[0]; int left = 0, right = 0; for(left = 1, right = size-1; left = pivot && a[right] <= pivot){ swap(left, right, a); } } swap(0, right, a); } 

J’ai écrit cette méthode pour partitionner un tableau comme une étape préliminaire afin d’appliquer un sorting rapide, je l’ai testé sur cet exemple de données:

 8 2 5 13 4 19 12 6 3 11 10 7 9 

la sortie correcte doit être:

 6 2 5 7 4 3 8 12 19 11 10 13 9 

mais la sortie réelle est:

 6 2 5 13 4 3 8 12 19 11 10 7 9 

L’algorithme doit permuter 13 avec 7 mais il échoue à cause de la condition && dans la boucle ci-dessus. Je veux incrémenter à left uniquement si a[left] >= pivot et décrémenter à right uniquement si a[right]<= pivot .

• Séparer un tableau pour les nombres pairs et impairs
• lequel est plus vite? «Vecteur de struct» ou «nombre de vecteurs»?
• Boost liste de graphes ou vec
• Calculer le minimum, le maximum et la moyenne des nombres entrés
• Comment trouver et remplacer toutes les occurrences d’une sous-chaîne dans une chaîne?

• C ++: Comment diviser une chaîne en chaînes plus petites de taille égale?
• stl map performance?
• Nombre minimum de clics pour résoudre le casse-tête de type Flood-It
• Ensemble C ++: compter les éléments inférieurs à une valeur
• Comment pouvons-nous trouver le deuxième maximum de array efficacement?

 void partition(int *a, int size) { int pivot = a[0]; int left, right; for(left = 1, right = size-1; left < right; ) { if(a[left] > pivot && a[right] <= pivot) { swap(left, right, a); } if(a[left] <= pivot) left++; if(a[right] > pivot) right--; } } 

 int partition(int arr[], int left, int right) { int pivot = arr[left]; while (left != right) { if (arr[left] > arr[right]) { swap(arr[left], arr[right]); } if (pivot == arr[left]) right--; else // Pivot == arr[right] left++; } return left; }