1 minutes
L'Algorithme de Tri Le Plus Simple Bubble Sort
Dernière mise à jour: 29 septembre, 2022Le tri à bulles (Bubble sort) est probablement le moyen de tri le plus simple auquel vous pouvez penser lors de la création d'un algorithme de tri. L'idée est que vous parcourez l'algorithme en triant les éléments adjacents encore et encore jusqu'à ce que nous ayons un tableau trié.
§Commençons
Le tri à bulles était probablement le premier algorithme de tri que j'ai appris et je savais que nous pouvions probablement créer une algorithme mieux que cela.
Ce n'est peut-être pas l'algorithme le plus rapide, mais il est toujours important de le connaître et de le comprendre. L'une des très bonnes raisons d'apprendre cet algorithme est qu'il s'agit apparemment de l'une des questions d'entretien les plus posées. Alors allons-y.
Comme expliqué ci-dessus, nous parcourons simplement le tableau jusqu'à ce que le tableau soit trié. Nous avons besoin de deux boucles (imbriquées) pour cet algorithme. Dans la première boucle, nous irons du début à la fin et dans la seconde, nous irons du début à la longueur du tableau moins un moins l'index de la première boucle n-1-i. Ceci est important car nous trouvons toujours la plus grande valeur de notre tableau et la portons au dernier index (si nous trions min à max bien sûr). Ainsi, à chaque finalisation de la deuxième boucle, nous portons la plus grande valeur à la fin du tableau et, comme nous en avons fini avec eux, nous n'avons plus besoin de vérifier ces valeurs.
Ok, je sais que c'est plus qu'assez de texte pour un algorithme aussi simple. Nous pouvons commencer avec le code maintenant, je l'ai écrit en python parce que j'aime pratiquer des algorithmes avec python et je pense que c'est beaucoup plus facile que des alternatives (comme Java) :
def bubbleSort(arr, n):
for i in range(n): # Parcourir le tableau
for j in range(0, n-i-1): # Boucle à travers les parties non triées
# À chaque itération, portez le courant max jusqu'au dernier en commutant
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
if __name__ == "__main__":
arr = [2, 3, 5, 1, 7, 6, 4]
length = len(arr)
bubbleSort(arr, length)
print(arr)
§Conclusion et Complexité
Comme nous pouvons le voir, le tri à bulles n'est certainement pas l'algorithme de soting le plus rapide dans la plupart des cas. En raison de la boucle imbriquée et en parcourant le tableau n * n fois, notre pire cas est O(N²). Nous n'aurons pas besoin d'un tableau auxiliaire pour cet algorithme donc notre complexité spatiale est constante (O(1)).
Considérez peut-être cet algorithme lorsque vous avez le temps mais pas l'espace.
Continuez à apprendre!
Ilker AkbiyikTable Des Matières
Articles Similaires
