12
votes

Tri de la matrice INT avec seulement 3 éléments

J'ai ce tableau: xxx

Quel est le moyen optimal de trier ce tableau, en pseudocode?

Merci!

algorithm optimization sorting pseudocode

3 commentaires

trié (a) avec mon pseudo trié fonction qui trie en place :)


                                        
                                                                            Beaucoup de doublons, par exemple  Stackoverflow.com/questions/3319993/... 
                                        
                                                                            EASY:  int [] myarray = {6, 8, 17};  :)



                                    
                    4 Réponses :
                    
                                            
                            
                                
                                    22
 votes
                                
                            
                            
                                
                                     Je pense que cela devrait être assez rapide (ordre croissant):  xxx                                  

                                                                    
                                    
                                    
                                        1 commentaires
                                        
                                                                                            
                                                    Votre bulle classique déroulée tri :-) +1.                                                
                                                
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    13
 votes
                                
                            
                            
                                
                                     Ce code fait 2 ou 3 comparaisons et 4 enregistrements de mémoire dans le pire des cas, par opposition à une autre réponse (toujours 3 comparaisons et 9 enregistrements de mémoire dans le pire des cas). 
if a[0] < a[1]:
    if a[1] > a[2]:
        if a[0] < a[2]:
            temp = a[1]
            a[1] = a[2]
            a[2] = temp
        else:
            temp = a[0]
            a[0] = a[2]
            a[2] = a[1]
            a[1] = temp
    else:
        # do nothing
else:
    if a[1] < a[2]:
        if a[0] < a[2]:
            temp = a[0]
            a[0] = a[1]
            a[1] = temp
        else:
            temp = a[0]
            a[0] = a[1]
            a[1] = a[2]
            a[2] = temp
    else:
        temp = a[0]
        a[0] = a[2]
        a[2] = temp

                                

                                                                    
                                    
                                    
                                        4 commentaires
                                        
                                                                                            
                                                    Je vais vous donner +1 pour ça, Adamax. Bien que ce soit des fesses laids à lire, la question  a fait  demander optimal et la vôtre semble satisfaire que :-)                                                

                                                
                                                                                            
                                                    Votre algorithme donne un résultat incorrect avec {2, 3, 1} matrice.                                                
                                                
                                                                                            
                                                    @ionree sûr, j'ai corrigé le code. Si vous jetez un coup d'œil à  Le code d'origine , vous verrez que le chemin d'exécution finit par éteindre deux éléments pendant que chaque élément a être déplacé.                                                
                                                
                                                                                            
                                                    Légère optimisation: remplacement du premier  << / code> Comparaison avec  = << / code> éviterait un échange inutile si  a [0]  == A [1] `.                                                

                                                
                                                                                    

                                    

                                                            

                        

                        
                                            
                            
                                
                                    11
 votes
                                
                            
                            
                                
                                     version légèrement plus efficace que le tri des bulles déroulées, pas optimal, mais toujours assez simple  xxx                                  

                                                                    
                                    
                                    
                                        1 commentaires
                                        
                                                                                            
                                                    Je ne peux pas croire que quelqu'un a voté cela. C'était à -1. Je viens de la monter et maintenant c'est à 0.                                                
                                                
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    5
 votes
                                
                            
                            
                                
                                     mai  Ce graphique  montrant un arbre de décision pour Tri de trois éléments aide:
                                 

                                                                    
                                    
                                    
                                        3 commentaires
                                        
                                                                                            
                                                    De quel livre est-ce?                                                
                                                
                                                                                            
                                                    Cela vient de "GRUNDLEGENDE ALGORITHMEN" ( www14.in.tum.de/~ga  ) de Volker Heun - malheureusement en allemand seulement. Une figure très similaire peut être trouvée dans "Introduction aux algorithmes" de Cormen et al. ( MitPress.mit .edu / livres / introduction-algorithmes ).                                                
                                                
                                                                                            
                                                    Je savais que je l'ai vu quelque part ... Peut-être que c'est dans le livre de Sedgewick, aussi? Mais pour que quiconque se demandait, il est en effet dans les CLRS, sous "Tri de temps linéaire". Merci!

Articles qui pourrait vous intéresser : Calculer la différence dans l'échelle d'évaluation alphabétique Complexité de Trouver tous les multiples de 3 et 5 entre 1 et 10 000 000 Ma vérification pour savoir si un graphique est un arbre binaire renvoie toujours faux Comment trouver le nombre d'itérations de l'algorithme de recherche binaire?