Почему этот метод пузырьковой сортировки не работает? Зачем ему нужен еще один цикл for?

#java #arrays #sorting

#java #массивы #сортировка

Вопрос:

У меня проблема с 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]

Ответ №1:

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

 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;
            }
        }
    }
}

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

1. Я не понял код, сэр. Было бы здорово, если бы вы могли объяснить мне код, если вы не возражаете. Разве цикл for не проверяет все элементы, не сравнивает их и не сортирует из первого цикла for?

2. @ThisuraThenuka добавил некоторое объяснение, надеюсь, оно более понятное;)

Ответ №2:

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

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;
             }
         }
     }
 }