Оптимизированная сортировка пузырьков (Java)

Ответ 1

Прежде всего, у вас есть доступ к ограничениям:

    for(int j=0; j<a.length; j++) {
      if(a[j] > a[j+1]) {

для j == a.length-1, поэтому условие цикла должно быть j < a.length-1.

Но в Bubble sort вы знаете, что после прохождения k наибольшие элементы k сортируются в k последних элементах массива, поэтому обычная сортировка Bubble использует

public static void bubblesort(int[] a) {
  for(int i=1; i<a.length; i++) {
    boolean is_sorted = true;

    for(int j=0; j < a.length - i; j++) { // skip the already sorted largest elements
      if(a[j] > a[j+1]) {
         int temp = a[j];
         a[j] = a[j+1];
         a[j+1] = temp;
         is_sorted = false;
      }
    }

    if(is_sorted) return;
  }
}

Теперь это все равно сделает много ненужных итераций, когда массив имеет длинный отсортированный хвост самых больших элементов, например, у вас есть k,k-1,...,1 как первые k элементы и k+1 до 100000000 в порядке после что. Стандартная сортировка Bubble пройдет через k раз (почти) весь массив.

Но если вы помните, где вы сделали свой последний своп, вы знаете, что после этого индекса есть самые большие элементы в порядке, поэтому

public static void bubblesort(int[] a) {
  int lastSwap = a.length-1;
  for(int i=1; i<a.length; i++) {
    boolean is_sorted = true;
    int currentSwap = -1;

    for(int j=0; j < lastSwap; j++) {
      if(a[j] > a[j+1]) {
         int temp = a[j];
         a[j] = a[j+1];
         a[j+1] = temp;
         is_sorted = false;
         currentSwap = j;
      }
    }

    if(is_sorted) return;
    lastSwap = currentSwap;
  }
}

сортирует приведенный выше пример только с одним проходом через весь массив, а остальные пропускаются только через (короткий) префикс.

Конечно, в общем, это не будет покупать вас много, но тогда оптимизация типа Bubble в любом случае является довольно бесполезным.

Ответ 2

 public static Integer[] optimizedbubbleSort(Integer[] input){
    long startTime = System.nanoTime();
    boolean swapped = true;
    for(int pass=input.length-1; pass>=0 && swapped; pass--){
        swapped = false;
        for(int i=0; i<pass; i++){
            if(input[i]>input[i+1]){
                int temp = input[i];
                input[i] = input[i+1];
                input[i+1] = temp;
                swapped = true;
            }
        }
    }
    System.out.println("Time taken for OPTIMIZED bubbleSort: "+(System.nanoTime() - startTime));
    return input;
}

Ответ 3

вы должны использовать переменную "размер" для внутреннего цикла и изменить ее на последний измененный элемент в каждом цикле. Таким образом, ваш внутренний цикл переходит к последнему "замененному" элементу и передает оставшиеся, которые не отслаиваются (aka в их правильном месте). то есть

do {
        int newsize =0;
        for (int i = 1; i < size; i++) {
            if (a[i - 1] > a[i]) {
                int temp;
                temp = a[i - 1];
                a[i - 1] = a[i];
                a[i] = temp;
                newsize =i;
            }
        }
        size = newsize;
   } while (size > 0);

Ответ 4

    public static void BubbleSorter(params int[] input){
        int newSize = input.Length-1, size = 0;
        bool swap;
        do
        {
            swap = false;
            for (int j = 0; j < newSize; j++)
            {
                if (input[j] > input[j + 1])
                {
                    int temp = input[j + 1];
                    input[j + 1] = input[j];
                    input[j] = temp;
                    swap = true;
                    size = j;
                }
            } newSize = size;
        } while (swap);

        DisplayArrayElements(input);
    }

Ответ 5

Я разработал метод, который уменьшает количество итераций, исключая части в начале и конце массива, которые были упорядочены в предыдущих циклах.

static int[] BubbleSortOptimized(int arr[]) {
    int start = 0, stop = arr.length - 1, control = 0;
    boolean ordered, nsCaught;
    while (true){
        ordered = true;
        nsCaught = false;
        for (int i = start; i < stop; i++) {
            if (i > 1) {
                if (!nsCaught && arr[i-2] > arr[i-1]){
                    ordered = false;
                    start = i-2;
                    nsCaught = true;
                }
            }
            if (arr[i] > arr[i+1]){
                int hold = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = hold;
                control = i;
            }
        }
        System.out.println(Arrays.toString(arr));
        if (ordered) return arr;
        stop = control;
    }
}

Но как @Daniel Fischer сказал в более раннем ответе, он не делает много с большими массивами.

Ответ 6

В приведенном выше примере массив отсортирован после 3-го прохода, но мы все равно продолжим с 4-го, 5-го прохода. Предположим, что если массив уже отсортирован, то перестановки не будет (потому что смежные элементы всегда в порядке), но мы все равно продолжим проходы, и все равно будет (n-1) проходов.

Если мы можем определить, что массив отсортирован, то мы должны остановить выполнение дальнейших проходов. Это оптимизация по сравнению с оригинальным алгоритмом сортировки пузырьков.

Если в конкретном проходе нет перестановки, это означает, что массив отсортирован, поэтому мы не должны выполнять дальнейшие проходы. Для этого у нас может быть переменная флага, которая устанавливается в true перед каждым проходом и становится ложной, когда выполняется свопинг.

void bubbleSort(int *arr, int n){
for(int i=0; i<n; i++)
{  
  bool flag = false;
   for(int j=0; j<n-i-1; j++)
   {
      if(array[j]>array[j+1])
      {
        flag = true;
         int temp = array[j+1];
         array[j+1] = array[j];
         array[j] = temp;
      }
   }
  // No Swapping happened, array is sorted
  if(!flag){ 
     return; 
  }}}

Ответ 7

public class Tester {
    static boolean bubbleFlag = true;

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

    private static void bubbleSort(int...array) {
        System.out.println("Before Sorting: " + Arrays.toString(array));

        for (int i = 0; i < array.length - 1; i++) {
            if (i > 0) if (bubbleFlag) break;

            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) array = swap(j, j + 1, array);
                System.out.println("Iteration " + i + " :" + Arrays.toString(array));
            }
            bubbleFlag = true;
        }
    }

    private static int[] swap(int i1, int i2, int...is) {
        bubbleFlag = false;
        is[i1] = is[i1] + is[i2];
        is[i2] = is[i1] - is[i2];
        is[i1] = is[i1] - is[i2];
        return is;
    }
}

Ответ 8

Я думаю, что это то, что вам нужно. Ключ должен рассматривать массив только до индекса, где произошел последний обмен (newn).

public static void bubblesort(int[] a) {
  int i, n, newn;
  n = a.length;

  while (n > 0) {
      newn = 0;
      for (i = 1; i < n; i++) {
          if (a[i - 1] > a[i]) {
              temp = a[i];
              a[i] = a[i - 1];
              a[i - 1] = temp;
              newn = i;
          }
      }
      n = newn;
    }

    return a;
}

Ответ 9

Вот самый простой, лучший и оптимальный алгоритм пузырьковой сортировки с использованием цикла while. Сортирует числа в заданной форме массива слева направо в порядке возрастания. Это очень просто понять и легко реализовать.

private static int[] bubbleSort(int[] array) {

        int length = array.length - 1;
        int index = 0;

        while ( index < length) {

            if (array[index] > array[index + 1]) {
                swap(array, index, index + 1);
            }
            index++;

            if (index == length) {
                index = 0;
                length--;
            }
        }
        return array;
    }

    private static void swap(int[] array, int index1, int index2) {

        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

Ответ 10

Оптимизированная сортировка пузырьков с помощью только 1 для цикла

/*Advanced BUBBLE SORT with ONE PASS*/
/*Authored by :: Brooks Tare  AAU*/

public class Bubble {

    public int[] bubble(int b[]){ 
    int temp,temp1; 

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

            if(b[i]>b[i+1] ){
                ///swap(b[i],b[i+1]);

                temp=b[i];
                b[i]=b[i+1];
                b[i+1]=temp;

    /*Checking if there is any number(s) greater than 
      the current number. If there is swap them.*/
                while(i>0){


                    if(b[i]<b[i-1]){
                    ///swap(b[i]<b[i-1])

                        temp1=b[i];
                        b[i]=b[i-1];
                        b[i-1]=temp1;
                        i--;
                    }
                    else if(b[i]>b[i-1]){i--;}
                }
            }
            else{continue;}

        }



        return b;
    }
///the following is a function to display the Array 
        public void see(int []a){
            for(int j=0;j<a.length;j++){
                System.out.print(a[j]+",");
            }
        }



    public static void main(String []args){
        ///You can change the Array to your preference.. u can even make it dynamic 

        int b[]={5,1,4,2,0,3}; 
        int v[]=new int[100]; 
        Bubble br=new Bubble();
        v=br.bubble(b);
        br.see(v);

    }
}