L'agorithmie, base de tri

Méthode a bulle, shaker et quick sort

algorithmie

Un ordinateur est bête !

Le noyeau de l'ordinateur ne peux pas faire de tâche complexe.

  • un bug = un problème lié à l'incompréhension d'un humain face à la machine
  • un ordibnateur ne calcule que la memoire alloué.
  • Nous sommes capable de reconnaître nos amis, notre famille de dos, car nous exécution pas comme un ordinateur, mais plus complexe. Un ordinateur est incapable de reconnaître un visage (l'inteligence artificiel n'utilise pas l'algorithmie pour la reconnaissance).

Exemple :

  • Il ne peux pas faire de multiplication
  • si 5*3 l'ordinateur ferra 5+5+5

Pour comprendre un ordinateur il faut être bête !

⚠ Un algorithme n'est pas une équation, mais une suite d'intruction

Algorithmie très vieux datant du 8e siècle qui se nomme AL KARWAZI qui donne Algorithmie. Turing a imaginé la machine de Turing qui permet de résoudre pleins de problème mathématique. Les ordinateur ce sont basé sur les machines de Turing avec des case d'instruction, de case et d’exécution.
Pour intervertir des valeurs je suis obligé d'utiliser une 3e variable.

Un trie en quick sort, est un trie rapide qui se base sur plusieurs fonction, de processus ce basant sur une médiane distribué à chaque fonction jusqua avoir une valeur par fonction.

Cas pratique

Pouvoir créer des sortes de recettes pour executer une tâche. Turing a Imaginer une machine :

  • Des cases

Trier un jeu de carte :

3 méthodes proposé :

Proposition quick sort :
effectué plusieurs tâche en parallèle Valeur médianne entre 1-5 et 5-10 le procésseur va donner la carte a que

Démontrer en Code

Méthode de Aimé :

pseudo code :

carte_trier[10] ={0,0,0,0,0,0,0,0,0,0}
carte_non_trier[10] = {7,6,10,9,3,4,2,1,5,8}

for i = 0 to i = 9 
    i++
    carte_a_placer = carte_non_trier[i]
    carte_a_trier[carte_a_placer - 1] = carte_a_la_place


# output
# 1ère iteration
# {0,0,0,0,0,0,7,0,0,0}

Pratique :

Méthode a bulle

Le tri à bulles ou tri par propagation1 est un algorithme de tri. Il consiste à comparer répétitivement les éléments consécutifs d'un tableau, et à les permuter lorsqu'ils sont mal triés. Il doit son nom au fait qu'il déplace rapidement les plus grands éléments en fin de tableau, comme des bulles d'air qui remonteraient rapidement à la surface d'un liquide.

def venant de wikipedia

python :

carte = [4,9,2,10,3,7,6,1,5,8]

def algo(i):
    first_local = carte[i]
    second_local = carte[i+1]
            
    if first_local > second_local :
        carte[i] = second_local
        carte[i+1] = first_local
    else:
            carte[i] = first_local
    i = i + 1

if __name__ == '__main__':
    while carte != [1,2,3,4,5,6,7,8,9,10]:
        for i in range(0,9):
                algo(i)
        print(carte)

Corection du professeur

Tableau_trier(taille_tableau)
    je commence avec i = 0 et tant que i < taille_tableau alors incremente i de 1
        case = tableau[i]
        case_au _dessus = tabelau[i+1]
        si case > case_au_dessus 
            alors retourne pas_trier
        retourne tableau_trier

tant que Tableau_trier est faux 
    case_a_analyser = 0
    je commence avec case_a_analyser = 0 et tant que i < taille_tableau alors incrémente i de 1
    premiere_case = tableau[case_a_analyser]
    deuxieme_case = tableau[case_a_analyser + 1]
    si premiere_case > deuxieme_case
        intervertir(premiere_case avec deuxieme_case) # on sais pas encore le faire


Méthode shaker

La différence entre cet algorithme et le tri à bulles est qu'il exécute un tri dans chaque direction à chaque passe le long de la liste à trier2. Cet algorithme de tri n'est que légèrement plus difficile à comprendre et à mettre en œuvre que le tri à bulles, et il résout en partie le problème des tortues du tri à bulles (les tortues sont les petits éléments situés près de la fin de la liste d'origine, qui ne remontent que très lentement, un emplacement par itération, vers leur emplacement définitif).

def venant de wikipedia

python :


carte = [4,9,2,10,3,7,6,1,5,8]

def up(i, y):
    if carte[i] > carte[i+y] :
        first_local = carte[i]
        second_local = carte[i+y]
        carte[i] = second_local
        carte[i+y] = first_local

    i = i + y
def down(i, y):      
    if carte[i] < carte[i+y] :
        first_local = carte[i]
        second_local = carte[i+y]
        carte[i] = second_local
        carte[i+y] = first_local

    i = i + y

if __name__ == '__main__':
    i = 0
    while carte != [1,2,3,4,5,6,7,8,9,10]:
        while i < 9:
            up(i, 1)
            i = i + 1
        while i > 0:
            down(i, -1)
            i = i - 1
        
    print(carte)


Correction professeur

pseudo code

caseEnCours = 0
caseSuivante = 0
caseAuBout = Faux

//je veux intervir deux case array[indice1] et array[indice2]
Fonction intervertir(array[],indice1,indice2)
    temp = array[indice1]
    array[indice1] = array[indice2]
    array[indice2] = temp 

//je parcours le tableau mais je ne peux pas sortir du tableau
Fonction parcoursTableau(array[] , step)  //
    caseAuBout = Faux
    caseEnCours = caseEnCours + step  //caseEnCours = caseEnCours + 1 = 1 
    si caseEnCours > taille(array[]) -1  
        caseEnCours = taille(array[]) -1 
        caseAuBout = Vrai
    si caseEnCours < 0
        caseEnCours = 0 
        caseAuBout = Vrai

//je remonte la carte la plus haute
Fonction remonteCartePlusHaute(array[])  {1,5,7,2}
X   Tant que caseAuBout = Faux  //tant que je n'ai pas parcouru tout mon tableau
X       indice1 = caseEnCours
        parcoursTableau(array, 1)             //caseEnCours = 1
        indice2 = caseEnCours
V       si array[indice1]  >  array[indice2] alors
            intervertir(array,indice1 , indice2 )

//je redescend la carte la plus base
Fonction redescendCartePlusBasse(array[])
Tant que caseAuBout = Faux  //tant que je n'ai pas parcouru tout mon tableau
X       indice1 = caseEnCours
        parcoursTableau(array, -1)            //caseEnCours = 1
        indice2 = caseEnCours
V       si array[indice1]  < array[indice2] alors
            intervertir(array,indice1 , indice2 )

//Est-ce que mon tableau est trier?
Fonction isArraySorted(array[])
    tableauTrier = Vrai
    Tant que caseAuBout = Faux 
        indice1 = caseEnCours
        parcoursTableau(array, 1)             //caseEnCours = 1
        indice2 = caseEnCours
        si array[indice1]  >  array[indice2] alors
                tableauTrier = Faux
                exit


//Je veux trier un jeu de carte
Fonction sort(array[])
    //Est-ce que mon tableau est trier?
    sorted = isArraySorted(array)
    //tant que mon tableau est pas trier alors
    tant que pas sorted 
        remonteCartePlusHaute(array)
        redescendCartePlusBasse(array)
    //j'affiche mon tableau


Méthode quick sort

Pour trier chaque carte nous créeon un arbre binaire. Le principe est de séparer chaque partie en la médiane (la moitier de chaque nombre). Puis nous repartissons chaque partie encore en la médianne.

-> jeux de couloir

av logo

© 2021 Gilles Avraam. Tous droits réservés.