Ottimizzazione Bubble Sort (Java)

Question

Vorrei sapere in che modo è possibile ottimizzare l'ordinamento delle bolle in modo che trascuri elementi già ordinati, anche dopo il primo passaggio.

Eg. [4, 2, 3, 1, 5, 6] --> [2, 3, 1, **4, 5, 6**] 

Osserviamo che [4,5,6] sono già in modo ordinato, come si può modificare il mio codice in modo che si affaccia questo 3 elementi nel passaggio successivo? (il che significa che l'ordinamento sarebbe più efficiente?) Suggerite un metodo ricorsivo?

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; j++) { 
     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; 
    } 
} 

Grazie per il vostro tempo!

Answer 1

Prima di tutto, si ha un out-of-bounds accesso:

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

per j == a.length-1, quindi la condizione del ciclo dovrebbe piuttosto essere j < a.length-1.

Ma, in bubble sort, si sa che dopo k passaggi, il più grande k elementi sono ordinati alle ultime k voci della matrice, in modo convenzionale bubble sort utilizza

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

Ora, che sarebbe ancora fare un sacco di iterazioni inutili quando l'array ha una lunga coda ordinata di elementi più grandi, diciamo che hai k,k-1,...,1 come i primi elementi e k+1 a 100000000 in seguito. Lo standard Bubble sort passerà k volte (quasi) all'intero array.

Ma se vi ricordate dove è stato effettuato l'ultimo di swap, si sa che dopo tale indice, ci sono gli elementi più grandi in ordine, in modo

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

sarebbe sorta l'esempio precedente, con un solo passaggio attraverso l'intero array, e il resto passa solo attraverso un prefisso (breve).

Ovviamente, in generale, questo non ti comprerà molto, ma l'ottimizzazione di un Bubble sort è comunque un esercizio piuttosto futile.

Answer 2

dovresti usare una "dimensione" variabile per il ciclo interno e cambiarla all'ultimo elemento scambiato in ogni ciclo. In questo modo il tuo ciclo interno sale all'ultimo elemento "scambiato" e passa il resto che non sono stati rimossi (alias nel loro posto corretto). cioè

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

Answer 3

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

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

Answer 5

ho ideato un metodo che riduce il numero di iterazioni escludendo parti all'inizio e alla fine della matrice che sono stati ordinati in cicli precedenti.

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

Ma, come @Daniel Fischer detto in una precedente risposta, it doesn't do a lot with larger arrays.