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/
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.
-> 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
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
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.
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
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