Почему этот метод bubbleSort не работает? Зачем нужен еще один цикл?

Question

У меня проблема с bubbleSort () в Java. Что не сортирует массив

import java.util.*;

public class Example {
    public static void bubbleSort(int[] x){
        for(int i=0; i<x.length-1; i++){
            if(x[i]>x[i+1]){
                int t=x[i];
                x[i]=x[i+1];
                x[i+1]=t;
            }
        }
    }
    public static void main(String[] args) {
        int[] xr={99,78,67,12,65,54,43,23,67,11};
        System.out.println(Arrays.toString(xr)); //99,78,67
        bubbleSort(xr);
        System.out.println(Arrays.toString(xr)); //11, 12, 23, 43, 
    }
}

Это вывод данного кода:

[99, 78, 67, 12, 65, 54, 43, 23, 67, 11] [78, 67, 12, 65, 54, 43, 23, 67, 11, 99]

Answer 1

Прочитайте сортировку пузырьков еще раз.

https://www.tutorialspoint.com/data_structures_algorithms/bubble_sort_algorithm.htm

for(int i=0; i<x.length-1; i++)

Ваш цикл будет проходить через массив только один раз.

                int t=x[j];
                x[j]=x[j+1];
                x[j+1]=t;
            }```
Within the loop, you are just swapping sibilling two elements as lower first if first one higher than the next one.

This will just bring the highest value to end of the array. Then what about the next highest value?. To sort completely, you need to do this swapping array element count number of times. O(n2)
https://en.wikipedia.org/wiki/Bubble_sort

so it should be like,

public static void bubbleSort(int[] x){
 for(int j=0; j<x.length-1; j++){
         for(int i=0; i<x.length-1; i++){
             if(x[i]>x[i+1]){
                 int t=x[i];
                 x[i]=x[i+1];
                 x[i+1]=t;
             }
         }
     }
 }

Answer 2

Вы проходите только один раз. Вам придется сделать это еще пару раз:

public static void bubbleSort(int[] x){
    for(int i=x.length - 1; i>0; i--){
        for(int j=0; j<i; j++){
            if(x[j]>x[j+1]){
                int t=x[j];
                x[j]=x[j+1];
                x[j+1]=t;
            }
        }
    }
}

Он проверяет только смежные значения, поэтому, когда минимальным является последнее значение, после одного прогона оно будет на второй последней позиции (только одна проверка и смена позиции). Поэтому вам нужно делать это столько раз, сколько элементов в массиве, но не всегда для всего набора (после первого запуска максимальный элемент будет на последней позиции и т. Д.).