algorithm
Tri à bulles
Recherche…
Paramètres
Paramètre | La description |
---|---|
Stable | Oui |
En place | Oui |
Meilleure complexité de cas | Sur) |
Complexité moyenne des cas | O (n ^ 2) |
La pire complexité | O (n ^ 2) |
Complexité de l'espace | O (1) |
Tri à bulles
BubbleSort
compare chaque paire successive d'éléments dans une liste non ordonnée et inverse les éléments s'ils ne sont pas dans l'ordre.
L'exemple suivant illustre le tri à bulles sur la liste {6,5,3,1,8,7,2,4}
(les paires comparées à chaque étape sont encapsulées dans '**'):
{6,5,3,1,8,7,2,4}
{**5,6**,3,1,8,7,2,4} -- 5 < 6 -> swap
{5,**3,6**,1,8,7,2,4} -- 3 < 6 -> swap
{5,3,**1,6**,8,7,2,4} -- 1 < 6 -> swap
{5,3,1,**6,8**,7,2,4} -- 8 > 6 -> no swap
{5,3,1,6,**7,8**,2,4} -- 7 < 8 -> swap
{5,3,1,6,7,**2,8**,4} -- 2 < 8 -> swap
{5,3,1,6,7,2,**4,8**} -- 4 < 8 -> swap
Après une itération de la liste, nous avons {5,3,1,6,7,2,4,8}
. Notez que la plus grande valeur non triée dans le tableau (8 dans ce cas) atteindra toujours sa position finale. Ainsi, pour être sûr que la liste est triée, nous devons itérer n-1 fois pour les listes de longueur n.
Graphique:
Implémentation en Javascript
function bubbleSort(a)
{
var swapped;
do {
swapped = false;
for (var i=0; i < a.length-1; i++) {
if (a[i] > a[i+1]) {
var temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
swapped = true;
}
}
} while (swapped);
}
var a = [3, 203, 34, 746, 200, 984, 198, 764, 9];
bubbleSort(a);
console.log(a); //logs [ 3, 9, 34, 198, 200, 203, 746, 764, 984 ]
Implémentation en C #
Le tri à bulles est également connu sous le nom de tri descendant . Il s’agit d’un algorithme de tri simple qui parcourt de manière répétée la liste à trier, compare chaque paire d’éléments adjacents et les échange s’ils sont dans le mauvais ordre.
Implémentation de Bubble Sort
J'ai utilisé le langage C # pour implémenter un algorithme de tri par bulles
public class BubbleSort
{
public static void SortBubble(int[] input)
{
for (var i = input.Length - 1; i >= 0; i--)
{
for (var j = input.Length - 1 - 1; j >= 0; j--)
{
if (input[j] <= input[j + 1]) continue;
var temp = input[j + 1];
input[j + 1] = input[j];
input[j] = temp;
}
}
}
public static int[] Main(int[] input)
{
SortBubble(input);
return input;
}
}
Implémentation en C & C ++
Un exemple d'implémentation de BubbleSort
en C++
:
void bubbleSort(vector<int>numbers)
{
for(int i = numbers.size() - 1; i >= 0; i--) {
for(int j = 1; j <= i; j++) {
if(numbers[j-1] > numbers[j]) {
swap(numbers[j-1],numbers(j));
}
}
}
}
C Implémentation
void bubble_sort(long list[], long n)
{
long c, d, t;
for (c = 0 ; c < ( n - 1 ); c++)
{
for (d = 0 ; d < n - c - 1; d++)
{
if (list[d] > list[d+1])
{
/* Swapping */
t = list[d];
list[d] = list[d+1];
list[d+1] = t;
}
}
}
}
Tri à bulles avec pointeur
void pointer_bubble_sort(long * list, long n)
{
long c, d, t;
for (c = 0 ; c < ( n - 1 ); c++)
{
for (d = 0 ; d < n - c - 1; d++)
{
if ( * (list + d ) > *(list+d+1))
{
/* Swapping */
t = * (list + d );
* (list + d ) = * (list + d + 1 );
* (list + d + 1) = t;
}
}
}
}
Implémentation en Java
public class MyBubbleSort {
public static void bubble_srt(int array[]) {//main logic
int n = array.length;
int k;
for (int m = n; m >= 0; m--) {
for (int i = 0; i < n - 1; i++) {
k = i + 1;
if (array[i] > array[k]) {
swapNumbers(i, k, array);
}
}
printNumbers(array);
}
}
private static void swapNumbers(int i, int j, int[] array) {
int temp;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
private static void printNumbers(int[] input) {
for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + ", ");
}
System.out.println("\n");
}
public static void main(String[] args) {
int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
bubble_srt(input);
}
}
Implémentation Python
#!/usr/bin/python
input_list = [10,1,2,11]
for i in range(len(input_list)):
for j in range(i):
if int(input_list[j]) > int(input_list[j+1]):
input_list[j],input_list[j+1] = input_list[j+1],input_list[j]
print input_list