Tri rapide en python

jojol_8144 Messages postés 132 Date d'inscription   Statut Membre Dernière intervention   -  
jojol_8144 Messages postés 132 Date d'inscription   Statut Membre Dernière intervention   -
Bonjour,


Voilà, j'essaye de créer un programme de tri rapide, mais l'on me demande aussi d'ajouter des entrées/sorties:

Voici le code déjà existant sur lequel je me base: 

def quicksort(alist, start, end):
    '''Sorts the list from indexes start to end - 1 inclusive.'''
    if end - start > 1:
        p = partition(alist, start, end)
        quicksort(alist, start, p)
        quicksort(alist, p + 1, end)
  
  
def partition(alist, start, end):
    pivot = alist[start]
    i = start + 1
    j = end - 1
  
    while True:
        while (i <= j and alist[i] <= pivot):
            i = i + 1
        while (i <= j and alist[j] >= pivot):
            j = j - 1
  
        if i <= j:
            alist[i], alist[j] = alist[j], alist[i]
        else:
            alist[start], alist[j] = alist[j], alist[start]
            return j
  
  
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
quicksort(alist, 0, len(alist))
print('Sorted list: ', end='')
print(alist)


J'aurais aimé savoir si vous aviez une solution à me proposer pour ajouter des E/S dans mon programme svp ?

Aussi, j'ai un soucis de syntaxe, je n'arrive pas à faire un tableau du genre: 

tableau[0..N-1]


Je ne sais pas comment rédiger le N-1 en python, si vous avez une idée pour m'aider svp ?...

Merci par avance

B.cdlt
A voir également:

1 réponse

Réponse 1 / 1
quent217 Messages postés 420 Date d'inscription   Statut Membre Dernière intervention   347
 
Bonjour,
votre question n'est pas très claire.
Que voulez-vous dire par "ajouter des entrées/sorties" ?
Et que signifie pour vous 
tableau[0..N-1]
? Si c'est une sous liste contenant les N premiers éléments d'une liste, vous pouvez faire 
tableau[:N]
.
0
jojol_8144 Messages postés 132 Date d'inscription   Statut Membre Dernière intervention   3
 
Salut Qut217:

voilà, j'ai écris ça en langage algo que j'ai pas encore appliqué car je sais pas comment faire: 


procedure echanger (E/S valeur1 : entier, E/S valeur2 : entier)


étant donné que le typage n'est pas explicite en python, je suppose que je ne doit pas définir 
 x : entier
par exemple

pareil pour cette entête, j'arrive pas à le faire: 


fonction partitionner (E/S t[0..N-1] : entier, premier : entier, dernier : entier, pivot : entier)


le corps de mon programme est déjà rédigé ( cf: code posté en haut) mais voilà, avec ceci: 
 E/S t[0..N-1]
, je sais pas comment gérer les entrée sortie et modifier ça pour intégrer ça dans mon programme déjà existant posté dans mon premier message....

Si tu pouvais m'aider ce serait cool.
0
quent217 Messages postés 420 Date d'inscription   Statut Membre Dernière intervention   347 > jojol_8144 Messages postés 132 Date d'inscription   Statut Membre Dernière intervention  
 
En pseudo-code, on a tendance à préciser beaucoup d'informations, notamment on déclare les variables avant le début du code et on précise leurs types. Je pense que cela vient du fait qu'on a commencé à faire du pseudo-code il y a longtemps quand il existait uniquement des langages de bas niveau comme le C. Mais aujourd'hui avec Python et d'autres langages de haut niveau, ça ne fonctionne plus de la même manière. Il est donc normal que vous ne sachiez pas comment traduire ça en Python car ce n'est pas possible.
Premièrement, en Python on ne précise effectivement pas le type des variables ni des arguments donc pas de 
x: entier
.
Ensuite si je ne me trompe pas, le 
t[0..N-1]
permet de dire que t est un tableau de N éléments indexés de 0 à N-1. Encore une fois, en Python on ne précise pas la taille d'un tableau (qui se trouve être une liste en Python) et les éléments sont toujours indexés de 0 à N-1 donc on ne le précise pas non plus.
Pour finir, celui dont je suis le moins sûr est le 
E/S
mais il me semble que cela signifie que la variable passée en paramètre peut-être lue et modifiée à l'intérieur de la procédure ou de la fonction. Cela se fait avec des pointeurs en C, mais en Python les pointeurs n'existent pas donc ce n'est pas possible dans tous les cas.
En Python, quand on fait une affectation 
a=5
à l'intérieur d'une fonction, cela créer obligatoirement une variable locale qui ne pourra pas être lue depuis l'exterieur donc on ne peut pas passé un entier en paramètre et le modifier. On est donc obligé de retourner les nouvelles valeurs.
La procédure echanger doit donc être une fonction et s'écrit comme ça : 
def echanger(valeur1, valeur2):
    return valeur2, valeur1

Bon en réalité on peut se débrouiller pour modifier les valeurs sans les retourner (par exemple avec des variables globales, ou encore en créant son propre type mutable) mais c'est plus simple de les retourner.
Pour les listes c'est un peu différent. En fait l'affectation produit toujours le même effet mais comme il s'agit d'un type mutable, on peu modifier son contenu sans faire d'affectation en faisant 
t[0]=42
qui n'est pas du tout pareil que 
t=[42, ...]
. C'est pour cela que la fonction partition dans votre premier message peut modifier le contenu de alist.
la fonction partitionner se fait donc exactement comme vous l'avez fait et vous ne pouvez rien précisez de plus pour les paramètres.
Je précise quand même qu'on peut écrire 
def echanger(valeur1 : int, valeur2 : int):

mais je n'ai jamais compris à quoi ça sert car ça n'empèche pas de passer une chaine de caractère ou n'importe quoi d'autre en paramètre, et de toute facon, personne ne l'utilise. C'est juste si vous voulez rendre le code plus clair et savoir rapidement ce qu'il attend en entrée.

Donc pour résumé, je ne sais pas pourquoi vous vouliez faire ça, si c'est un exercice à faire ou autre chose, mais ce n'est pas possible en Python et vous ne pouvez pas faire autrement que le code que vous avez donné au début.

Bonne journée.
0
jojol_8144 Messages postés 132 Date d'inscription   Statut Membre Dernière intervention   3
 
En fait, voici ce que j'essaye de faire: 


fonction partitionner (E/S t[0..N-1] : entier, premier : entier, dernier : entier, pivot : entier) : 
j : entier // nouveau pivot   
i : entier // indice de boucle 
debut   // place le pivot en dernière position  
échanger (t[pivot], t[dernier])   // j va contenir la position du nouveau pivot  
          j ← premier    // boucle sur toutes les valeurs   
          pour i de premier à dernier-1     
         // si une valeur est plus petite que l'actuel pivot     
         // elle est échangée avec le nouveau pivot temporaire     
         si t[i] < t[dernier] alors échanger (t[i], t[j])        
                   // on avance le nouveau pivot      
                    j ← j + 1    
         finsi   
fin pour   // échange entre l'ancien et le nouveau pivot   
échanger (t[dernier], t[j])    // retour du nouveau pivot  
retourner j
fin


Si vous aviez un morceau de code similaire svp ou en m'aidant en apportant des modifications sur mon code précédent, ça m'aiderais beaucoup

merci

C'est un exercice de TP de mon fascicule
0
jojol_8144 Messages postés 132 Date d'inscription   Statut Membre Dernière intervention   3
 
Up
0
quent217 Messages postés 420 Date d'inscription   Statut Membre Dernière intervention   347 > jojol_8144 Messages postés 132 Date d'inscription   Statut Membre Dernière intervention  
 
Le code que vous montrez ici correspond à peu près à la fonction partitionner que vous avez montrer au début. Le code est légèrement différent mais il fait la même chose donc je ne comprends pas vraiment ce que vous voulez.
Vous avez parler d'entrée / sortie et, à moins que je n'ai pas compris de quoi il s'agit, sinon je vous ai expliqué que ce n'est pas possible Python.
Essayez d'expliquer votre demande plus clairement sinon je vais avoir du mal à vous aider.
0

Discussions similaires

Qui sont les personnes dans mon ajout rapide de Snapchat ?
lobino68 -
m_manolo25 -

21 réponses
Pourquoi des inconnus bizarres m'ajoutent sur snap ?
FrelX_ -
Leo -

1 réponse
Ajout rapide snap
Bobo -
Utilisateur anonyme -

1 réponse
Ajout rapide
Lie -
Doucesensible -

2 réponses