Bonjour je réalise un exercice dont le but est de trier une liste par ordre croissant sans utiliser de méthodes, mais même après avoir lu ceci:

http://www.siteduzero.com/forum-83-568 [...] ne-liste.html

Je n'arrives pas à crée un algorithme qui fait ce que je lui demande, le code de fred1599 me plaît bien:

def sorting(liste):
    for i in range(0, len (liste)):
        mini=i
        for j in range(i+1, len (liste)):
            if liste[j]<liste[mini] :
                mini=j
            liste[i], liste[mini] = liste[mini], liste[i]
    return liste

mais il fonctionne ou pas suivant l'ordre de mes chiffres dans ma liste.

Alors je souhaiterais savoir comment faire en sorte qu'il marche ou alors avoir une piste pour un autre algorithme, j'ai regardé sur le web mais tout ça m'a l'air bien compliqué...

Merci à vous

Citation

Je n'arrives pas à crée un algorithme qui fait ce que je lui demande, le code de fred1599 me plaît bien:

Mouais, j'ai pas été très inspiré ce jour là

J'aurais pu utiliser enumerate() plutôt que range-len, et de loin comme ça je dirais qu'il poserait problème si je met des nombres négatifs.

Citation : Asimoov

Je n'arrives pas à crée un algorithme qui fait ce que je lui demande, le code de fred1599 me plaît bien:

def sorting(liste):
    for i in range(0, len (liste)):
        mini=i
        for j in range(i+1, len (liste)):
            if liste[j]<liste[mini] :
                mini=j
            liste[i], liste[mini] = liste[mini], liste[i]
    return liste

C'est censé être un tri par sélection. Voir le tuto de bluestorm.

Citation : fred1599

J'aurais pu utiliser enumerate() plutôt que range-len, et de loin comme ça je dirais qu'il poserait problème si je met des nombres négatifs.

Tu es très très loin du compte. Ton code est faux parce que l'échange des indices ne doit pas être fait dans la 2ème boucle for mais dans la première. Par ailleurs, tu devrais savoir que

range(0, len (liste))

s'écrit

range(len (liste))

Je te laisse le soin de corriger à l'intention du PO.

Edit : voilà la modif...

def sorting(liste):
    for i in range(len (liste)):
        mini=i
        for j in range(i+1, len (liste)):
            if liste[j]<liste[mini] :
                mini = j
        liste[i], liste[mini] = liste[mini], liste[i]
    return liste

Citation : fred1599

Edit : voilà la modif...

OK.


Autant en C qui est assez pauvre, cela a un sens de coder des algorithmes "triviaux" comme des tris quadratiques autant en Python, je trouve qu'il est dommage et même artificiel voire incompréhensible de coder de tels algorithmes dans la mesure où le langage Python dispose de tout ce qu'il faut nativement pour s'en dispenser (mais je sais que ce point de vue est discutable).


D'autre part, je trouve ton code vraiment trop près du code C correspondant lequel a du mal à rendre l'idée du tri par sélection. Le tri par sélection est un tri immédiat qui consiste pour trier une liste à extraire d'une liste son plus petit élément, à le retirer et à recommencer avec la nouvelle liste, autrement dit :

def trier(liste):
    r=[] 
    while liste:
        mini=min(liste)
        liste.remove(mini)
        r.append(mini)
    return r

    
print trier([41,17,3,4,17,51])

[3, 4, 17, 17, 41, 51]

Je trouve que cela apparait peu clairement dans le code que tu donnes. Je préférerais peut-être le code suivant même s'il est sans doute moins facile à comprendre que le tien pour un débutant :

def trier(liste):
    r=[]
    while liste:
        mini=liste[0]
        for z in liste:
            if z < mini:
                mini=z
        liste.remove(mini)
        r.append(mini)
    return r


    
print trier([41,17,3,4,17,51])

[3, 4, 17, 17, 41, 51]

Citation

Autant en C qui est assez pauvre, cela a un sens de coder des algorithmes "triviaux" comme des tris quadratiques autant en Python, je trouve qu'il est dommage et même artificiel voire incompréhensible de coder de tels algorithmes dans la mesure où le langage Python dispose de tout ce qu'il faut nativement pour s'en dispenser (mais je sais que ce point de vue est discutable).

+1

Citation

D'autre part, je trouve ton code vraiment trop près du code C correspondant lequel a du mal à rendre l'idée du tri par sélection. Le tri par sélection est un tri immédiat qui consiste pour trier une liste à extraire d'une liste son plus petit élément, à le retirer et à recommencer avec la nouvelle liste, autrement dit :

Arf ouais, c'est vrai ! Je suis à fond dans le C/C++ ça tombe bien

C'est vrai que c'est proche et trouve surprenant que le PO s'en inspire.

Citation

Je trouve que cela apparait peu clairement dans le code que tu donnes. Je préférerais peut-être le code suivant même s'il est sans doute moins facile à comprendre que le tien pour un débutant :

Mais non il est pas moins facile à comprendre, J'ai voulu refaire mon code de tri par sélection justement dans ce style, que je trouve nettement plus compréhensible.

Par contre, la méthode naïve sort() doit être une voir la plus efficace de tous, donc pourquoi s'en priver?

Citation : fred1599

Par contre, la méthode naïve sort() doit être une voir la plus efficace de tous, donc pourquoi s'en priver?

C'est sûr qu'une fois acquis le fait que l'algorithme du quicksort est implémenté nativement en Python, on peut se demander l'intérêt d'en faire d'autres (à part pour s'entraîner à l'algorithmique), qui seront nécessairement plus lents.

Citation : NoHaR

C'est sûr qu'une fois acquis le fait que l'algorithme du quicksort est implémenté nativement en Python,

Hum, j'avais crû comprendre que ce n'était pas un quicksort mais (je crois) un timsort, algo maison créé par un développeur du langage.

exact

Citation : candide

Citation : NoHaR

C'est sûr qu'une fois acquis le fait que l'algorithme du quicksort est implémenté nativement en Python,

Hum, j'avais crû comprendre que ce n'était pas un quicksort mais (je crois) un timsort, algo maison créé par un développeur du langage.

Ah oui en effet, je viens de lire ceci :

Citation : doc python

Starting with Python 2.3, the sort() method is guaranteed to be stable.

Ce qui exclut quicksort.
Enfin quoi qu'il en soit ça revient un peu au même. Je pense que pour battre cette fonction en termes de perfs, il faut implémenter la fonction en C, de façon assez générique, et la binder ensuite dans un module Python, sans parler de la recherche de l'algo qui ira bien…

Merci à vous pour vos réponses et pour les liens que vous me suggérés , je vais regarder cela plus en détail ce soir.
Quand je vois les 2 codes de Candide je me dis que j'aurais pu faire un effort pour trouver tout seul

Effectivement la méthode sort() est sans doute plus appropriée mais l'intitulé de l'exercice stipulait de ne pas l'utiliser.

J'aurais aussi une question subsidiaire qui n'a rien à voir avoir le sujet:
Qu'est ce qu'un PO ?

Je vous remercie encore. Bonne soirée à vous.

PO = Posteur Original. La personne qui a démarré le sujet, en somme.

Ah tout bête Merci à toi.