Mise en œuvre du tri à bulles en Java (BubbleSort)

Lorsque j'ai surfé sur le net, j'ai trouvé l'URL suivante, donc Je voulais étudier le tri des bulles.

URL:http://www.mkyong.com/java/java-bubble-sort-example/

Définition du tri à bulles écrite par le propriétaire du blog:

Bubble sort is the simplest sorting algorithm, it compares the first two elements, if the first is greater than the second, swaps them, continues doing (compares and swaps) for the next pair of adjacent elements. It then starts again with the first two elements, compares, swaps until no more swaps are required.

Définition du tri à bulles trouvé par google,

-> Comparez les valeurs de deux éléments adjacents dans le tableau Algorithme d'alignement qui échange selon les conditions (que la valeur soit grande ou petite)

Par exemple Si l'entrée est 1597253, La sortie est 1235579 selon le programme qui met en œuvre le tri des bulles.

J'ai pensé à l'algorithme que j'allais implémenter, Premier, Comparez la taille du premier nombre et du deuxième nombre du côté gauche, Si le nombre à gauche est grand -> Échangez la position avec le nombre à droite Si le nombre de droite est grand -> vous n'avez pas à le remplacer

Aussi, Comparez la taille du deuxième et du troisième, Décidez si vous souhaitez remplacer le poste ou non, De la même manière 3e VS 4e, 4e VS 5e. .. .. Par rapport aux 6e et 7e tailles, le premier tour est terminé.

Et Le deuxième tour commence. Comparez la taille avec le premier et le second, Comparez les tailles du deuxième et du troisième. .. .. De la même manière, comparez la taille avec les 6e et 7e, Le deuxième tour est terminé.

Dans le même flux En l'état, le troisième tour et le quatrième tour. .. .. Le dernier est le sixième tour

J'ai pensé à l'algorithme et je l'ai implémenté

public class BubbleSort {

public static void main(String[] args) {
    int[] test = new int[]{2, 1, 3, 2, 5, 4};

    int[] a= sort(test);
    for(int t:a){
        System.out.print(t);
    }

}

static int[] sort(int[] input){

int length = input.length; // Longueur du tableau // IF Numéro avant> Numéro après //数字の位置を交換する際、前の数字を暫く保存するためのVariable int temp;

//配列の中各数字を比べる必要があり、 // Vous devez également exécuter chaque tour écrit ci-dessus et écrire une double boucle for(int i=0;i<length;i++){

        for(int j=0;j<length-1;j++){

// si avant> après la position d'échange if(input[j]>input[j+1]){

temp = input [j]; // Enregistrer le numéro précédent dans la variable pendant un moment input [j] = input [j + 1]; // Déplacer le dernier numéro à la position du numéro précédent input [j + 1] = temp; // Déplacer le numéro précédent (enregistré dans Variable) vers l'arrière

            }

        }

    }
    return input;
}

}

résultats de test:

122345, précis

Considérez le nombre d'échanges

Calculez le nombre d'échanges de nombres en procédant comme suit ・ Calculez et imprimez le nombre de fois pour échanger la position des nombres ・ Imprimez la matrice de remplacement

static int[] sort(int[] input){

	int count = 0;
	int length = input.length;
    int temp;
    
    for(int i=0;i<length;i++){    	
    	
    	for(int j=0;j<length-1;j++){
    	   
    	   if(input[j]>input[j+1]){
    		   
    		  temp = input[j];
    		  input[j] = input[j+1];
    		  input[j+1] = temp; 
    		  count++;

//交換後の配列の元素をプリント System.out.print("count:" + count + " "); for(int a:input){ System.out.print(a); } System.out.println();

    	   }

    	}
    	
    }
	System.out.println(count);
	return input;
}

Output:

count:1 123254 count:2 122354 count:3 122345

3 = Nombre d'échanges:

Au pire des cas, L'ordre des nombres dans le tableau est 543221, et il est toujours échangé lors de la comparaison de la taille des nombres. Puisqu'il y a 6 nombres dans le tableau, le nombre d'échanges est Premier tour: 5 Deuxième tour: 4 Troisième tour: 3 Quatrième tour: 2 Cinquième tour: 1 Total: 15

Au fait, Dans ce cas, le nombre de comparaisons et le nombre d'échanges sont les mêmes.

Réglage du programme

J'en ai remarqué un ici, Le programme que j'ai écrit ci-dessus est en fait inefficace.

La cause est Bien que la séquence soit déjà dans l'ordre croissant Il est encore possible de comparer la taille des nombres.

Vous pouvez le savoir en calculant le nombre de comparaisons.

public class BubbleSort {

public static void main(String[] args) {
    int[] test = new int[]{2, 1, 3, 2, 5, 4};

    int[] a= sort(test);
    for(int t:a){
        System.out.print(t);
    }

}

static int[] sort(int[] input){

int length = input.length; // Longueur du tableau // IF Numéro avant> Numéro après //数字の位置を交換する際、前の数字を暫く保存するためのVariable int temp;

//比較回数を計算用 int count = 0;

//配列の中各数字を比べる必要があり、 //上記書いた各ラウンドも実行する必要があり二重ループを書く for(int i=0;i<length;i++){

        for(int j=0;j<length-1;j++){

//数字大きさ比較する際、配列の元素をプリント count++; System.out.print("count:" + count + " "); for(int a:input){ System.out.print(a); } System.out.println();

// si avant> après la position d'échange if(input[j]>input[j+1]){

temp = input [j]; // Enregistrer le numéro précédent dans la variable pendant un moment input [j] = input [j + 1]; // Déplacer le dernier numéro à la position du numéro précédent input [j + 1] = temp; // Déplacer le numéro précédent (enregistré dans Variable) vers l'arrière

            }

        }

    }
    return input;
}

}

Output:

count:1 213254 count:2 123254 count:3 123254 count:4 122354 count:5 122354 count:6 122345 count:7 122345 count:8 122345 count:9 122345 count:10 122345 count:11 122345 count:12 122345 count:13 122345 count:14 122345 count:15 122345 count:16 122345 count:17 122345 count:18 122345 count:19 122345 count:20 122345 count:21 122345 count:22 122345 count:23 122345 count:24 122345 count:25 122345 count:26 122345 count:27 122345 count:28 122345 count:29 122345 count:30 122345 122345

Même si les séquences sont déjà dans l'ordre croissant après avoir comparé trois fois Le programme est toujours en cours et inefficace.

La solution est Vérifiez si le tableau est dans l'ordre croissant.

Vérifiez la méthode avec URL, Variable avec booléen is_sorted; a été utilisée.

En regardant l'explication, // is sorted? then break it, avoid useless loop. Si la situation est triée, terminez le programme et Évitez les boucles inutiles.

public class BubbleSort {

public static void main(String[] args) {
    int[] test = new int[]{2, 1, 3, 2, 5, 4};

    int[] a= sort(test);
    for(int t:a){
        System.out.print(t);
    }

}

static int[] sort(int[] input){

int length = input.length; // Longueur du tableau // IF Numéro avant> Numéro après //数字の位置を交換する際、前の数字を暫く保存するためのVariable int temp;

//比較回数を計算用 int count = 0;

    Boolean is_sorted;

//配列の中各数字を比べる必要があり、 //上記書いた各ラウンドも実行する必要があり二重ループを書く for(int i=0;i<length;i++){

//ラウンドが始まる前にTrueに設定、もし比較する行為をしない場合ループ終止 is_sorted = true;

        for(int j=0;j<length-1;j++){

//数字大きさ比較する際、配列の元素をプリント count++; System.out.print("count:" + count + " "); for(int a:input){ System.out.print(a); } System.out.println();

// si avant> après la position d'échange if(input[j]>input[j+1]){

temp = input [j]; // Enregistrer le numéro précédent dans la variable pendant un moment input [j] = input [j + 1]; // Déplacer le dernier numéro à la position du numéro précédent input [j + 1] = temp; // Déplacer le numéro précédent (enregistré dans Variable) vers l'arrière

//交換行為をしたらFalseに変更、 //配列がまだ昇順になってないとのこと is_sorted = false;

            }

        }

        if (is_sorted) break;

    }
    return input;
}

}

Output: count:1 213254 count:2 123254 count:3 123254 count:4 122354 count:5 122354 count:6 122345 count:7 122345 count:8 122345 count:9 122345 count:10 122345 122345

Complexité temporelle

S'il y a N nombres Au moins N comparaisons au premier tour Le nombre de comparaisons au deuxième tour est d'au moins N fois

Pire cas = O (n²)

Autres: Si l'expression japonaise est étrange parce que je suis étranger Je vous serais reconnaissant si vous pouviez me le dire.

2019/2/16 Correction de la complexité temporelle et du nombre de comparaisons de nombres avec l'algorithme auquel j'ai pensé.

Recommended Posts

Mise en œuvre du tri à bulles en Java (BubbleSort)
Mise en œuvre du tri Stuge dans Python 3 (tri à bulles et tri rapide)
Tri à bulles en Python
Implémentation de l'algorithme de "Algorithm Picture Book" en Python3 (Bubble Sort)
Tri à bulles
Tri à bulles
Modèle de façade en Java
Motif singleton en Java
Modèle de poids mouche en Java
Modèle d'observateur en Java
Autorisations Linux sur Java
Utiliser DataFrame en Java
Implémentation de SimRank en Python
Modèle d'itérateur en Java
Implémentation hard-swish avec Keras
Modèle de décorateur en Java
Tri à bulles sans utiliser le tri
Tri personnalisé en Python3
Modèle de prototype en Java
Implémentation de Shiritori en Python
Modèle de proxy en Java
Implémentation de l'algorithme «Algorithm Picture Book» en Python3 (tri sélectif)
Trier naturellement le chemin en Python
Tri décroissant avec mongodb en python
Les débutants en Python organisent des sortes de bulles
Implémentation de Supreme Solver dans Python 3
Modèle de méthode de modèle en Java
Tri à bulles avec animation moelleuse
Trier par date en python