Mon test de bureau quicksort ne semble pas être correct

Question

Je pratique actuellement le quicksort et ça a bien fonctionné jusqu'à maintenant. Mais je pourrais trouver un exemple où j'échoue (parce qu'il semble être un cas spécial et je n'ai pas encore lu à ce sujet, c'est pourquoi je le fais mal .. ne peut pas le résoudre). Le problème est que je pense parce que je choisis le plus petit élément comme pivotelement:

9 1 4 2 7 *0* (star mark means pivotelement) 

Maintenant, je mis i,j où i passera par Array (passer à droite) jusqu'à ce qu'il trouve un élément qui est supérieur au pivotelement. Et j passera par Array (se déplacer à gauche) jusqu'à ce qu'il trouve un élément qui est inférieur au pivotelement. Trouvé, nous Commutons les éléments où i et j Montrer à. Nous faisons cela jusqu'à i et j croisés (aka "j est avant i"). Dans ce cas, on passe l'élément i montre et index i avec pivotelement ... Je ne veux pas décrire l'algorithme ensemble maintenant ou il sera question de longue ..

9 1 4 2 7 *0* 
i  j  but now we cannot find a j that is lower than Pivotelement. What we do? 
       I would continue by switching i with pivotelement: 

*0* 1 4 2 7 9 
      j i But now is the Problem that i and j are in other positions 
       (j is before i). I have no idea.. Please clarify and help.. 

Answer 1

Ce que vous avez est bien, vous avez réussi à pivoter.

Le pivot est dans la bonne position et les deux côtés du pivot satisfont à la condition que tous les éléments vers la gauche sont moins et tous les éléments vers la droite sont plus grands. L'index i obtient une mauvaise position sur le dernier mouvement du pivot, mais cela ne vous dérange pas que vous l'ayez cassé parce que vous en avez fini quand même. Maintenant, vous recurerez et triez rapidement les côtés gauche et droit du pivot - sauf qu'il n'y a pas de côté gauche, donc dans ce cas, vous ne faites que recurse vers la droite.

Answer 2

QuickSort travaille sur le concept de partitionnement . À chaque itération, il prend un élément pivot et essaie de le placer dans la position où il serait finalement placé. Au début, le pointeur i est toujours maintenu à l'index -1 (ce qui n'est évidemment pas possible, donc nous assignons simplement la valeur -1 et nous ne faisons référence qu'à un élément du tableau après l'avoir incrémenté).

Donc, dans votre scénario après la première itération vous obtenez,

0 1 4 2 7 9

qui est la position correcte pour l'élément de pivot choisi.

Explication: Depuis i est d'abord à -1, vous décrémentez j pointeur jusqu'à ce que vous obtenez un élément qui est inférieur à votre élément de pivot actuel (0). Cela amène j jusqu'à l'index 0 (vous devez ajouter ces conditions à votre code pour vous assurer qu'aucun espace mémoire illégal n'est accédé).

Enfin i+1 (où i est encore -1) est remplacé par l'élément pivotant, donc effectivement 9 est remplacé par 0 et alto!

Référez-vous au lien this pour une explication plus complète.