Illustration.

Vous pouvez observer ci-dessous la partition dessus-dessous autour d'un pivot en action.

Cliquez sur le bouton "Manuel" pour dérouler les étapes à votre rythme et comprendre ces étapes d'exécution.

Le bouton "Automate" enchaîne les étapes avec un intervalle de temps d'environ 3 secondes entre deux étapes (vous pouvez réduire ce temps en cliquant sur la petite flèche du formulaire contenant le nombre 3000).

Pour accélérer l'automate, régler ici le temps (en ms) qui sépare deux étapes :

formulation de l'algorithme.

Formulez, en français, l'algorithme de partition dessus-dessous illustré ci-dessus.

les couleurs
une formulation

A tout moment, on dispose d'éléments de diverses couleurs :

Éléments blancs : éléments non encore traités.
Élément rouge : le pivot.
Éléments jaunes : éléments en cours de traitement, l'un en queue de liste bleue, l'autre en tête de liste verte.
Éléments bleus : éléments traités, inférieurs ou égaux au pivot.
Éléments verts : éléments traités, supérieurs au pivot.

Tous les éléments de la liste sont passés en blanc.
On sélectionne un élément pivot (on prend ici la tête de liste pour simplifier).
On passe en jaune l'élément qui suit immédiatement le pivot, ainsi que l'élément de fin de liste.
Tant que l'élément jaune gauche est inférieur ou égal au pivot, on le passe en bleu et on passe l'élément suivant en jaune s'il est blanc.
Tant que l'élément jaune droit est supérieur au pivot, on le passe en vert et on passe l'élément précédent en jaune s'il est blanc.
Si l'élément jaune gauche est supérieur au pivot et l'élément jaune droit est inférieur au égal au pivot, on les échange, on passe le gauche en bleu, le droit en vert. On passe l'élément suivant la queue bleue en jaune s'il est blanc. On passe l'élément précédent la tête verte en jaune s'il est blanc.
On retourne au point 4 tant qu'il reste des blancs.
On échange le pivot et la queue des bleus.

programmer.

Écrire un programme python réalisant cet algorithme.

un code possible
avec affichage des états


from random import randint


def partitionDessusDessous(liste) :
	pivot = liste[0]
	gauche = 1
	droit = len(liste)-1
	while gauche <= droit :
		while gauche <= droit and liste[gauche] <= pivot :
			gauche +=1
		while gauche <= droit and liste[droit] > pivot :
			droit -= 1
		if gauche < droit :
			liste[gauche], liste[droit] = liste[droit], liste[gauche]
			gauche += 1
			droit -= 1
	liste[0], liste[gauche-1] = liste[gauche-1], liste[0]
	
	
 
	
	
L = [ randint(1,9) for _ in range(randint(5,12)) ]
print("Avant partition : ", L)
partitionDessusDessous(L)
print("Après partition : ", L)



from random import randint


def affiche(liste, gauche, droit) :
	print(' ', end=' ')
	for x in liste :
		print(x, end=' ')
	print(' ', end=' ')
	print()
	for i in range(-1,len(liste)+1) :
		if i == gauche : print('g', end=' ')
		elif i == droit : print('d', end=' ')
		else : print(' ', end=' ')
	print()
	if gauche == droit:
		for i in range(-1,len(liste)+1) :
			if i == droit : print('d', end=' ')
			else : print(' ', end=' ')
	print()
	print("*****************************************************")
	print()


def partitionDessusDessous_avecAffichage(liste) :
	pivot = liste[0]
	gauche = 1
	droit = len(liste)-1
	affiche(liste, gauche, droit)
	while gauche <= droit :
		while gauche <= droit and liste[gauche] <= pivot :
			gauche +=1
			affiche(liste, gauche, droit)
		while gauche <= droit and liste[droit] > pivot :
			droit -= 1
			affiche(liste, gauche, droit)
		if gauche < droit :
			liste[gauche], liste[droit] = liste[droit], liste[gauche]
			gauche += 1
			droit -= 1
			affiche(liste, gauche, droit)
	liste[0], liste[gauche-1] = liste[gauche-1], liste[0]
	
	
 
	
	
L = [ randint(1,9) for _ in range(randint(5,12)) ]
print("Avant partition : ", L)
partitionDessusDessous_avecAffichage(L)
print("Après partition : ", L)

Quelques exemples de déroulement obtenus :

 
Avant partition :  [6, 8, 1, 4, 5]
  6 8 1 4 5   
    g     d   

*****************************************************

  6 5 1 4 8   
      g d     

*****************************************************

  6 5 1 4 8   
        g     
        d     
*****************************************************

  6 5 1 4 8   
        d g   

*****************************************************

Après partition :  [4, 5, 1, 6, 8]

 
Avant partition :  [1, 3, 1, 4, 4, 4, 5, 6, 7, 9, 4]
  1 3 1 4 4 4 5 6 7 9 4   
    g                 d   

*****************************************************

  1 3 1 4 4 4 5 6 7 9 4   
    g               d     

*****************************************************

  1 3 1 4 4 4 5 6 7 9 4   
    g             d       

*****************************************************

  1 3 1 4 4 4 5 6 7 9 4   
    g           d         

*****************************************************

  1 3 1 4 4 4 5 6 7 9 4   
    g         d           

*****************************************************

  1 3 1 4 4 4 5 6 7 9 4   
    g       d             

*****************************************************

  1 3 1 4 4 4 5 6 7 9 4   
    g     d               

*****************************************************

  1 3 1 4 4 4 5 6 7 9 4   
    g   d                 

*****************************************************

  1 3 1 4 4 4 5 6 7 9 4   
    g d                   

*****************************************************

  1 1 3 4 4 4 5 6 7 9 4   
    d g                   

*****************************************************

Après partition :  [1, 1, 3, 4, 4, 4, 5, 6, 7, 9, 4]

 
Avant partition :  [3, 6, 9, 8, 2, 3, 4, 5, 2, 5, 6]
  3 6 9 8 2 3 4 5 2 5 6   
    g                 d   

*****************************************************

  3 6 9 8 2 3 4 5 2 5 6   
    g               d     

*****************************************************

  3 6 9 8 2 3 4 5 2 5 6   
    g             d       

*****************************************************

  3 2 9 8 2 3 4 5 6 5 6   
      g         d         

*****************************************************

  3 2 9 8 2 3 4 5 6 5 6   
      g       d           

*****************************************************

  3 2 9 8 2 3 4 5 6 5 6   
      g     d             

*****************************************************

  3 2 3 8 2 9 4 5 6 5 6   
        g d               

*****************************************************

  3 2 3 2 8 9 4 5 6 5 6   
        d g               

*****************************************************

Après partition :  [2, 2, 3, 3, 8, 9, 4, 5, 6, 5, 6]

 
Avant partition :  [9, 1, 5, 3, 3, 3, 3, 4, 5, 3, 1]
  9 1 5 3 3 3 3 4 5 3 1   
    g                 d   

*****************************************************

  9 1 5 3 3 3 3 4 5 3 1   
      g               d   

*****************************************************

  9 1 5 3 3 3 3 4 5 3 1   
        g             d   

*****************************************************

  9 1 5 3 3 3 3 4 5 3 1   
          g           d   

*****************************************************

  9 1 5 3 3 3 3 4 5 3 1   
            g         d   

*****************************************************

  9 1 5 3 3 3 3 4 5 3 1   
              g       d   

*****************************************************

  9 1 5 3 3 3 3 4 5 3 1   
                g     d   

*****************************************************

  9 1 5 3 3 3 3 4 5 3 1   
                  g   d   

*****************************************************

  9 1 5 3 3 3 3 4 5 3 1   
                    g d   

*****************************************************

  9 1 5 3 3 3 3 4 5 3 1   
                      g   
                      d   
*****************************************************

  9 1 5 3 3 3 3 4 5 3 1   
                      d g 

*****************************************************

Après partition :  [1, 1, 5, 3, 3, 3, 3, 4, 5, 3, 9]

 
Avant partition :  [2, 4, 4, 9, 2, 3]
  2 4 4 9 2 3   
    g       d   

*****************************************************

  2 4 4 9 2 3   
    g     d     

*****************************************************

  2 2 4 9 4 3   
      g d       

*****************************************************

  2 2 4 9 4 3   
      g         
      d         
*****************************************************

  2 2 4 9 4 3   
    d g         

*****************************************************

Après partition :  [2, 2, 4, 9, 4, 3]

à sa place.

Justifier qu'à la fin de l'exécution de la fonction partitionDessusDessous, le pivot est à la place qu'il occuperait dans la liste si elle était triée.

justification

A la fin de la fonction, le pivot est placé en queue de la sous-liste bleue, tous les éléments qui le précèdent sont donc inférieurs ou égaux à ce pivot. Et tous les éléments qui le suivent sont verts et sont donc strictement supérieurs à ce pivot. Le pivot est donc à la place qui lui revient si l'on trie la liste.

programmer.

Écrire une version de la fonction partition pour laquelle le pivot est initialement choisi à une position au hasard dans la liste.

un code possible
avec affichage des états


from random import randint

  

def partitionDessusDessous(liste) :
	indice_pivot = randint(0, len(liste)-1)
	pivot = liste[indice_pivot]
	gauche = 0
	droit = len(liste)-1
	 
	while gauche <= droit :
		while gauche <= droit and liste[gauche] <= pivot :
			gauche +=1
			 
		while gauche <= droit and liste[droit] > pivot :
			droit -= 1
			 
		if gauche < droit :
			liste[gauche], liste[droit] = liste[droit], liste[gauche]
			if droit == indice_pivot : indice_pivot = gauche
			gauche += 1
			droit -= 1
			 
	liste[indice_pivot], liste[gauche-1] = liste[gauche-1], liste[indice_pivot]





L = [ randint(1,9) for _ in range(randint(5,12)) ]
print("Avant partition : ", L)
partitionDessusDessous(L)
print("Après partition : ", L)


from random import randint

 
def affiche(liste, gauche, droit, pivot, indice_pivot) :
	print("Indice du pivot : ", indice_pivot)
	print("Valeur du pivot : ", pivot)
	print(' ', end=' ')
	for x in liste :
		print(x, end=' ')
	print(' ', end=' ')
	print()
	for i in range(-1,len(liste)+1) :
		if i == gauche : print('g', end=' ')
		elif i == droit : print('d', end=' ')
		else : print(' ', end=' ')
	print()
	if gauche == droit:
		for i in range(-1,len(liste)+1) :
			if i == droit : print('d', end=' ')
			else : print(' ', end=' ')
	print()
	print("*****************************************************")
	print()


def partitionDessusDessous_avecAffichage(liste) :
	indice_pivot = randint(0, len(liste)-1)
	pivot = liste[indice_pivot]
	gauche = 0
	droit = len(liste)-1
	affiche(liste, gauche, droit, pivot, indice_pivot)
	while gauche <= droit :
		while gauche <= droit and liste[gauche] <= pivot :
			gauche +=1
			affiche(liste, gauche, droit, pivot, indice_pivot)
		while gauche <= droit and liste[droit] > pivot :
			droit -= 1
			affiche(liste, gauche, droit, pivot, indice_pivot)
		if gauche < droit :
			liste[gauche], liste[droit] = liste[droit], liste[gauche]
			if droit == indice_pivot : indice_pivot = gauche
			gauche += 1
			droit -= 1
			affiche(liste, gauche, droit, pivot, indice_pivot)
	liste[indice_pivot], liste[gauche-1] = liste[gauche-1], liste[indice_pivot]





L = [ randint(1,9) for _ in range(randint(5,12)) ]
print("Avant partition : ", L)
partitionDessusDessous_avecAffichage(L)
print("Après partition : ", L)

Exemples d'exécutions de ce code :

 
Avant partition :  [9, 8, 9, 2, 1, 2, 9, 1, 1]
Indice du pivot :  6
Valeur du pivot :  9
  9 8 9 2 1 2 9 1 1   
  g               d   

*****************************************************

Indice du pivot :  6
Valeur du pivot :  9
  9 8 9 2 1 2 9 1 1   
    g             d   

*****************************************************

Indice du pivot :  6
Valeur du pivot :  9
  9 8 9 2 1 2 9 1 1   
      g           d   

*****************************************************

Indice du pivot :  6
Valeur du pivot :  9
  9 8 9 2 1 2 9 1 1   
        g         d   

*****************************************************

Indice du pivot :  6
Valeur du pivot :  9
  9 8 9 2 1 2 9 1 1   
          g       d   

*****************************************************

Indice du pivot :  6
Valeur du pivot :  9
  9 8 9 2 1 2 9 1 1   
            g     d   

*****************************************************

Indice du pivot :  6
Valeur du pivot :  9
  9 8 9 2 1 2 9 1 1   
              g   d   

*****************************************************

Indice du pivot :  6
Valeur du pivot :  9
  9 8 9 2 1 2 9 1 1   
                g d   

*****************************************************

Indice du pivot :  6
Valeur du pivot :  9
  9 8 9 2 1 2 9 1 1   
                  g   
                  d   
*****************************************************

Indice du pivot :  6
Valeur du pivot :  9
  9 8 9 2 1 2 9 1 1   
                  d g 

*****************************************************

Après partition :  [9, 8, 9, 2, 1, 2, 1, 1, 9]

 
Avant partition :  [4, 4, 4, 2, 8, 5, 9, 1]
Indice du pivot :  7
Valeur du pivot :  1
  4 4 4 2 8 5 9 1   
  g             d   

*****************************************************

Indice du pivot :  0
Valeur du pivot :  1
  1 4 4 2 8 5 9 4   
    g         d     

*****************************************************

Indice du pivot :  0
Valeur du pivot :  1
  1 4 4 2 8 5 9 4   
    g       d       

*****************************************************

Indice du pivot :  0
Valeur du pivot :  1
  1 4 4 2 8 5 9 4   
    g     d         

*****************************************************

Indice du pivot :  0
Valeur du pivot :  1
  1 4 4 2 8 5 9 4   
    g   d           

*****************************************************

Indice du pivot :  0
Valeur du pivot :  1
  1 4 4 2 8 5 9 4   
    g d             

*****************************************************

Indice du pivot :  0
Valeur du pivot :  1
  1 4 4 2 8 5 9 4   
    g               
    d               
*****************************************************

Indice du pivot :  0
Valeur du pivot :  1
  1 4 4 2 8 5 9 4   
  d g               

*****************************************************

Après partition :  [1, 4, 4, 2, 8, 5, 9, 4]

 
Avant partition :  [6, 6, 7, 7, 2, 5, 1, 4, 5, 6, 1, 1]
Indice du pivot :  2
Valeur du pivot :  7
  6 6 7 7 2 5 1 4 5 6 1 1   
  g                     d   

*****************************************************

Indice du pivot :  2
Valeur du pivot :  7
  6 6 7 7 2 5 1 4 5 6 1 1   
    g                   d   

*****************************************************

Indice du pivot :  2
Valeur du pivot :  7
  6 6 7 7 2 5 1 4 5 6 1 1   
      g                 d   

*****************************************************

Indice du pivot :  2
Valeur du pivot :  7
  6 6 7 7 2 5 1 4 5 6 1 1   
        g               d   

*****************************************************

Indice du pivot :  2
Valeur du pivot :  7
  6 6 7 7 2 5 1 4 5 6 1 1   
          g             d   

*****************************************************

Indice du pivot :  2
Valeur du pivot :  7
  6 6 7 7 2 5 1 4 5 6 1 1   
            g           d   

*****************************************************

Indice du pivot :  2
Valeur du pivot :  7
  6 6 7 7 2 5 1 4 5 6 1 1   
              g         d   

*****************************************************

Indice du pivot :  2
Valeur du pivot :  7
  6 6 7 7 2 5 1 4 5 6 1 1   
                g       d   

*****************************************************

Indice du pivot :  2
Valeur du pivot :  7
  6 6 7 7 2 5 1 4 5 6 1 1   
                  g     d   

*****************************************************

Indice du pivot :  2
Valeur du pivot :  7
  6 6 7 7 2 5 1 4 5 6 1 1   
                    g   d   

*****************************************************

Indice du pivot :  2
Valeur du pivot :  7
  6 6 7 7 2 5 1 4 5 6 1 1   
                      g d   

*****************************************************

Indice du pivot :  2
Valeur du pivot :  7
  6 6 7 7 2 5 1 4 5 6 1 1   
                        g   
                        d   
*****************************************************

Indice du pivot :  2
Valeur du pivot :  7
  6 6 7 7 2 5 1 4 5 6 1 1   
                        d g 

*****************************************************

Après partition :  [6, 6, 1, 7, 2, 5, 1, 4, 5, 6, 1, 7]

Avant partition :  [8, 2, 3, 5, 8, 5, 4, 6, 6, 8]
Indice du pivot :  5
Valeur du pivot :  5
  8 2 3 5 8 5 4 6 6 8   
  g                 d   

*****************************************************

Indice du pivot :  5
Valeur du pivot :  5
  8 2 3 5 8 5 4 6 6 8   
  g               d     

*****************************************************

Indice du pivot :  5
Valeur du pivot :  5
  8 2 3 5 8 5 4 6 6 8   
  g             d       

*****************************************************

Indice du pivot :  5
Valeur du pivot :  5
  8 2 3 5 8 5 4 6 6 8   
  g           d         

*****************************************************

Indice du pivot :  5
Valeur du pivot :  5
  4 2 3 5 8 5 8 6 6 8   
    g       d           

*****************************************************

Indice du pivot :  5
Valeur du pivot :  5
  4 2 3 5 8 5 8 6 6 8   
      g     d           

*****************************************************

Indice du pivot :  5
Valeur du pivot :  5
  4 2 3 5 8 5 8 6 6 8   
        g   d           

*****************************************************

Indice du pivot :  5
Valeur du pivot :  5
  4 2 3 5 8 5 8 6 6 8   
          g d           

*****************************************************

Indice du pivot :  4
Valeur du pivot :  5
  4 2 3 5 5 8 8 6 6 8   
          d g           

*****************************************************

Après partition :  [4, 2, 3, 5, 5, 8, 8, 6, 6, 8]