Menu

Tri rapide en python

Messages postés
74
Date d'inscription
vendredi 8 mars 2019
Statut
Membre
Dernière intervention
16 juin 2019
- - Dernière réponse : jojol_8144
Messages postés
74
Date d'inscription
vendredi 8 mars 2019
Statut
Membre
Dernière intervention
16 juin 2019
- 24 mai 2019 à 12:54
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
Afficher la suite 

1 réponse

Messages postés
326
Date d'inscription
vendredi 25 septembre 2015
Statut
Membre
Dernière intervention
6 mai 2019
76
0
Merci
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]
.
jojol_8144
Messages postés
74
Date d'inscription
vendredi 8 mars 2019
Statut
Membre
Dernière intervention
16 juin 2019
1 -
Et bien en somme j'essaye de faire ça:

def echanger(premier: int, dernier: int, pivot: int, tableau[0:N]):


Mais l'en tête en elle même est souligné avec les erreurs,

J'ai importé
from typing import List


mais j'aurais besoin de votre aide pour adapter mon entête avec le code que j'ai posté en haut svp

Si vous pouviez m'aider pour cela

voici ce que j'ai pour le moment:
"""
from typing import List
 
 
def quicksort(alist: List[int], start: int, end: int):
    """
    Sorts the list from indexes start to end - 1 inclusive.
 
    :param alist:
    :param start:
    :param end:
    :return:
    """
    if end - start > 1:
        p = partition(alist, start, end)
        quicksort(alist, start, p)
        quicksort(alist, p + 1, end)
 
 
def partition(alist: List[int], start: int, end: int):
    """
 
    :param alist:
    :param start:
    :param end:
    :return:
    """
    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
 
 
mylist = input('Enter the list of numbers: ').split()
mylist_toInt = [int(x) for x in mylist]
quicksort(mylist_toInt, 0, len(mylist_toInt))
print('Sorted list: ', end='')
print(mylist_toInt)


Que devrais-je faire svp ? que dois-je corriger selon vous ?
Merci d'avance pour votre patience
quent217
Messages postés
326
Date d'inscription
vendredi 25 septembre 2015
Statut
Membre
Dernière intervention
6 mai 2019
76 > jojol_8144
Messages postés
74
Date d'inscription
vendredi 8 mars 2019
Statut
Membre
Dernière intervention
16 juin 2019
-
Pourquoi voulez-vous à tout prix définir l'entête comme cela ?
Python est un langage qui ne type volontairement pas les paramètres de fonctions. Si vous voulez définir les types des paramètres, vous devriez changer de langage.
Comme je vous l'ai dit, vous pouvez faire si vous voulez
def echanger(valeur1 : int, valeur2 : int):

mais aucune vérification n'est faite. Si vous passer une chaine de caractère en paramètre à la fonction, il n'y aura pas d'erreur et l'execution continuera comme si vous aviez écrit
def echanger(valeur1, valeur2):

J'ai tester rapidement le module typing et il ne fait pas plus de vérification donc je ne vois pas son utilité. Et encore une fois, Python n'est pas fait pour ça, les types ne sont pas vérifiés et c'est volontaire.
Vous pouvez donc écrire si vous voulez
def echanger(premier: int, dernier: int, pivot: int, tableau: List[int]):

mais ça n'a aucun intéret.
Votre ligne
def echanger(premier: int, dernier: int, pivot: int, tableau[0:N]):

ne fonctionne pas car on ne peut pas définir la taille d'une liste de cette manière, et je pense même qu'on ne peut pas du tout le faire. Et de toute façon, on ne le fait pas non plus en C ou dans d'autres langages. On vous a sans doute appris à faire ça en pseudo code pour rendre le code plus clair mais on ne fait pas ça en programmation.

J'ai n'ai aucune idée de pourquoi vous cherchez absolument a déclarer les entête de fonction comme en pseudo code mais ce n'est clairement pas la bonne manière de faire (en tout cas en Python).
jojol_8144
Messages postés
74
Date d'inscription
vendredi 8 mars 2019
Statut
Membre
Dernière intervention
16 juin 2019
1 -
Merci pour ce complément,

Du coup, comment puis-je définir la taille de la liste par la suite (pas dans l'en tête mais dans le corp du programme)

"J'ai n'ai aucune idée de pourquoi vous cherchez absolument a déclarer les entête de fonction comme en pseudo code mais ce n'est clairement pas la bonne manière de faire (en tout cas en Python). "

Après oui, moi je suis les instruction de l'exercice de TP juste

Mais est-ce que mon programme tel qu'il est présenté mtn est correct, ou il y'a des soucis auxquels je n'ai pas fais attention svp ?

Merci
quent217
Messages postés
326
Date d'inscription
vendredi 25 septembre 2015
Statut
Membre
Dernière intervention
6 mai 2019
76 > jojol_8144
Messages postés
74
Date d'inscription
vendredi 8 mars 2019
Statut
Membre
Dernière intervention
16 juin 2019
-
Vous ne pouvez pas vraiment définir la taille de la liste sans la remplir avec des éléments.
Mais quand vous faites
mylist = input('Enter the list of numbers: ').split()
mylist_toInt = [int(x) for x in mylist]

vous créez bien une liste sans définir sa taille avant et ça ne pose pas de problèmes donc que voulez-vous de plus ?

"Après oui, moi je suis les instruction de l'exercice de TP juste"
Est-il écrit dans l'énoncé du TP qu'il faut absolument définir les types des paramètres en Python ? Si oui, c'est vraiment étrange...

Ensuite si vous me demandez si l'algorithme de quicksort fonctionne, oui ça m'a l'air correct.
Si vous me demandez si les entêtes des fonctions son correctes, moi je n'aurai pas préciser les types des paramètres mais ça fonctionne quand même donc on peut dire que c'est bon.
Après il faut voir ce qui est demandé exactement dans l'énoncé pour voir si vous avez oublié quelque chose ou non.
jojol_8144
Messages postés
74
Date d'inscription
vendredi 8 mars 2019
Statut
Membre
Dernière intervention
16 juin 2019
1 -
Bonjour, je reviens ici car j'essaye de faire exécuter mon programme mais j'ai plein d'erreurs soulignés:

<python>
from typing import List


def quicksort(alist: List[int], start: int, end: int):

Sorts
the
list
from indexes start

to
end - 1
inclusive.

:param
alist:
:param
start:
:param
end:
:return:

if end - start > 1:
p = partition(alist, start, end)
quicksort(alist, start, p)
quicksort(alist, p + 1, end)


def partition(alist: List[int], start: int, end: int):


:param
alist:
:param
start:
:param
end:
:return:

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


mylist = input('Enter the list of numbers: ').split()
mylist_toInt = [int(x) for x in mylist]
quicksort(mylist_toInt, 0, len(mylist_toInt))
print('Sorted list: ', end='')
print(mylist_toInt)
</python>

Pourriez-vous m'aider svp ? je suis sous python 3
Commenter la réponse de quent217