---
# System prepended metadata

title: Trier et organiser et trier des données
tags: [algorithmie]

---

---
title: Trier et organiser et trier des données
tags: algorithmie
robots: noindex, nofollow
author: Julien Noyer
---

# Trier et organiser des données

![](https://i.imgur.com/SAjkSYC.png)


Un **algorithme de tri** en informatique permet d'organiser une collection de données selon un ordre déterminé au préalable comme par _ordonner des entiers du plus grand au plus petit_. **Les algorithmes de tri** sont utilisés dans de très nombreuses situations et ils sont en particulier utiles à de nombreux algorithmes plus complexes comme certains _algorithmes de recherche_ ou dans des _réseaux de neurones_ informatiques. Ils peuvent également servir pour mettre en forme des données afin de les rendre plus lisibles pour l'utilisateur.

---

<br><br><br><br>

# Le tri a bulle


![Tri à bulle : <https://www.youtube.com/watch?v=lyZQPjUT5B4>](https://i.imgur.com/I4ZYbp4.png)

> Lien https://www.youtube.com/watch?v=lyZQPjUT5B4&t=147s


**Le tri à bulle** consiste à parcourir le tableau en permutant toutes les paire d’éléments consécutifs non ordonnés. Après le premier parcours, le plus grand élément se retrouve dans la deuxième case du tableau, il reste donc à appliquer la même procédure sur les autres données en plaçant les plus grandes données vers la droite.

```bash
Tableau au début [12, 0, 7, 29, 3]

[0, 12, 7, 29, 3]
[0, 7, 12, 29, 3]
[0, 7, 12, 3, 29]
[0, 7, 3, 12, 29]

Tableau à la fin [0, 3, 7, 12, 29]
```

Cet algorithme de tri est très simple à comprendre, on peut voir son fonctionnement qui permet de faire "descendre" le plus petit chiffre vers la gauche. Nous allons voir à présent comment écrire cet algorithme en pseudo-code.

<br><br>

## Pseudo-code

```bash
ALGO bubble_sorting
    data: ARRAY<NUMBER>
    dataSize: NUMBER
    sorted: BOOLEAN
    i: NUMBER
    tmp: NUMBER
  

START
  data <- [12, 0, 7, 29, 3]
  dataSize <- data.LENGTH
  sorted <- False
  
  WHILE sorted == False
      sorted <- True

      FOR i FROM 0 TO dataSize [ i <- i + 1 ] 
        IF data[i] > data[i + 1] THEN
          tmp <- data[1 +1]
          data[i + 1] <- data[i]
          data[i] <- tmp
          sorted <- False
        END IF
      END FOR

      dataSize <- dataSize - 1
    END WHILE

END ALGO
```

## Questions

- Estimez-vous cette algorithme rapide ? Très rapide ?
- Cette algorithme est-il efficace sur des grandes collections de données ?
- Pourquoi prendre la dance pour illustrer un algorithme ?

---

<br><br><br><br>

# Le tri par selection

![](https://i.imgur.com/w91gmrb.png)


> Lien https://www.youtube.com/watch?v=Ns4TPTC8whw

**Le tri par sélection** consiste à trouver dans le tableau le numéro de l’élément le plus petit, c’est-à-dire l’entier minimum. Une fois ce numéro trouvé, les éléments sont échangés puis la même procédure est appliquée sur la suite d’éléments.

```bash
ALGO selectSorting
  data: ARRAY<NUMBER>
  dataSize: NUMBER
  i: NUMBER
  j: NUMBER
  tmp: NUMBER

START
  FUNCTION sort(data)
      dataSize <- data.LENGTH

    START
      FOR i FROM 0 TO dataSize [ i <- i + 1 ] 
        FOR j FROM i + 1 TO dataSize [ j <- j + 1 ] 
          IF data[j] < data[i] THEN
            tmp <- data[i]
            data[i] <- data[j]
            data[j] <- tmp
          END IF
        END FOR
      END FOR
    END FUNCTION
END ALGO
```

---

<br><br><br><br>

# Exercices

Nous passons à présent à la pratique, vous devez réaliser un pseudo-code et la version Javascript pour répondre aux problèmes suivants : 

**Savoir si les nombres d'un tableau sont pair ou non.**
- Entrée = `[65, 2, 87, 30, 16, 5, 14, 67, 56, 8]`  
- Sortie = `[65 != pair, 2 = pair, ...]`

**Calculer la moyenne des chiffres d'un tableau.**
- Entrée = `[65, 2, 87, 30, 16, 5, 14, 67, 56, 8]`
- Sortie = `Moyenne 35 - Plus petit = 2, Plus grand = 87`

**Additionner les chiffres d'un nombre.**
- Entrée = `123456789`
- Sortie = `1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45`