Сортировка массива int с помощью BubbleSort

Ответ 1

Для реализации Bubble Sort вам нужны две петли.

Пример кода:

public static void bubbleSort(int[] numArray) {

    int n = numArray.length;
    int temp = 0;

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

            if (numArray[j - 1] > numArray[j]) {
                temp = numArray[j - 1];
                numArray[j - 1] = numArray[j];
                numArray[j] = temp;
            }

        }
    }
}

Ответ 2

Вы делаете только один проход через свой массив! Сортировка Bubble требует, чтобы вы продолжали цикл, пока не обнаружили, что вы больше не выполняете обмен; следовательно, время работы O (n ^ 2).

Попробуйте следующее:

public void sortArray(int[] x) {
    boolean swapped = true;
    while (swapped) {
       swapped = false;
       for(int i=1; i<x.length; i++) {
           int temp=0;
           if(x[i-1] > x[i]) {
               temp = x[i-1];
                x[i-1] = x[i];
                x[i] = temp;
                swapped = true;
            }
        }
    }
}

После swapped == false в конце цикла вы сделали полный проход, не найдя никаких экземпляров, где x[i-1] > x[i] и, следовательно, вы знаете, что массив отсортирован. Только тогда вы можете прервать алгоритм.

Вы также можете заменить внешний цикл while на цикл for n+1 итераций, который гарантирует, что массив в порядке; однако, цикл while имеет преимущество раннего завершения в сценарии, отличном от худшего.

Ответ 3

Ваша логика сортировки неверна. Это псевдокод для сортировки пузырьков:

for i = 1:n,
    swapped = false
    for j = n:i+1, 
        if a[j] < a[j-1], 
            swap a[j,j-1]
            swapped = true
    → invariant: a[1..i] in final position
    break if not swapped
end

Смотрите сортировочный веб-сайт для хорошего руководства по всем различным методам сортировки.

Ответ 4

Это не алгоритм сортировки пузырьков, вам нужно повторить, пока вам нечего менять:

public void sortArray(int[] x) {//go through the array and sort from smallest to highest
  for(;;) {
      boolean s = false;
      for(int i=1; i<x.length; i++) {
         int temp=0;
         if(x[i-1] > x[i]) {
            temp = x[i-1];
            x[i-1] = x[i];
            x[i] = temp;
            s = true;
         }
      }
      if (!s) return;
  }
}

Ответ 5

Вложенные петли типа Bubble должны быть написаны следующим образом:

int n = intArray.length;
int temp = 0;

for(int i=0; i < n; i++){
   for(int j=1; j < (n-i); j++){                        
       if(intArray[j-1] > intArray[j]){
            //swap the elements!
            temp = intArray[j-1];
            intArray[j-1] = intArray[j];
            intArray[j] = temp;
       }                    
   }
}

Ответ 6

public static void BubbleSort(int[] array){
        boolean swapped ;
        do {
            swapped = false;
            for (int i = 0; i < array.length - 1; i++) {
                if (array[i] > array[i + 1]) {
                    int temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    swapped = true;
                }
            }
        }while (swapped);
    }

Ответ 7

public class SortingArray {
public static void main(String[] args) {

int[] a={3,7,9,5,1,4,0,2,8,6};
int temp=0;

boolean isSwapped=true;


System.out.println(" before sorting the array: ");

for(int i=0;i<a.length;i++)
{
    System.out.print(a[i]);
}
System.out.println("");

do
{

isSwapped=false;

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

{

    if(a[i]>a[i+1])

    {

        temp=a[i];

        a[i]=a[i+1];

        a[i+1]=temp;

    }



}


}while(isSwapped);


System.out.println("after sorting the array: ");

    for(int array:a)

    {

        System.out.print(array);


    }
  }
}

Ответ 8

public class BubbleSort {

    public void sorter(int[] arr, int x, int y){

            int temp = arr[x];
            arr[x] = arr[y];
            arr[y] = temp;

    }

    public void sorter1(String[] arr, int x, int y){

        String temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;

    }

    public void sertedArr(int[] a, String[] b){
        for(int j = 0; j < a.length - 1; j++){
            for(int i = 0; i < a.length - 1; i++){
                if(a[i] > a[i + 1]){
                    sorter(a, i, i + 1);
                    sorter1(b, i, i + 1);
                }
            }
        }
        for(int i = 0; i < a.length; i++){
            System.out.print(a[i]);
        }
        System.out.println();
        for(int i = 0; i < b.length; i++){
            System.out.print(b[i]);
        }
        // 
    }
    public static void main(String[] args){
        int[] array = {3, 7, 4, 9, 5, 6};
        String[] name = {"t", "a", "b", "m", "2", "3"};
        BubbleSort bso = new BubbleSort();
            bso.sertedArr(array, name);
    }
}

Ответ 9

java code

public void bubbleSort(int[] arr){   

    boolean isSwapped = true;

    for(int i = arr.length - 1; isSwapped; i--){

        isSwapped = false;

        for(int j = 0; j < i; j++){

            if(arr[j] > arr[j+1]}{
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                isSwapped = true;
            }
        }

    }

}

Ответ 10

Стандартная реализация сортировки Bubble в Java:

//Time complexity: O(n^2)
public static int[] bubbleSort(int[] arr) {

    if (arr == null || arr.length <= 1) {
        return arr;
    }

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

    return arr;
}