Optimized Bubble Sort (Java)

Question

Ich würde gerne wissen, wie sonst kann ich Bubble-Sort zu optimieren, so dass es Elemente überblickt, die bereits sortiert wurden, auch nach dem ersten Durchlauf.

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

Wir beobachten, dass [4,5,6] sind bereits in sortierter Reihenfolge, wie kann meinen Code so ändern, dass es diese 3 Elemente in dem nächsten Durchgang mit Blick auf? (was bedeutet, dass die Sortierung effizienter wäre?) Schlagen Sie eine rekursive Methode vor?

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

Vielen Dank für Ihre Zeit!

Answer 1

Zunächst einmal haben Sie einen Out-of-bounds Zugang:

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

für j == a.length-1, so dass die Schleifenbedingung eher j < a.length-1 sein sollte.

Aber in Bubble-Art, wissen Sie, dass nach k Pässe, die größten k Elemente an den k letzten Einträge des Arrays sortiert werden, so dass die herkömmliche Blase Art verwendet

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

Nun, das wäre noch Führen Sie viele unnötige Iterationen durch, wenn das Array einen langen sortierten Schwanz von größten Elementen hat, sagen Sie, dass Sie k,k-1,...,1 als die ersten k Elemente und k+1 bis 100000000 in Reihenfolge haben. Die Standard Bubble Sortierung wird k mal durch (fast) das gesamte Array passieren.

Aber wenn Sie sich erinnern, wo Sie Ihre letzte Swap gemacht, wissen Sie, dass nach diesem Index gibt die größten Elemente in Ordnung sind, so

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

das obige Beispiel mit nur einem Durchlauf durch die gesamte sortieren würde Array, und der Rest geht nur durch ein (kurzes) Präfix.

Natürlich, im Allgemeinen wird das nicht viel kaufen, aber dann Optimierung einer Bubble-Art ist sowieso eine ziemlich sinnlose Übung.

Answer 2

Sie sollten eine Variable "size" für die innere Schleife verwenden und sie in jedem Zyklus zum zuletzt getauschten Element ändern. Auf diese Weise geht Ihre innere Schleife auf das neueste "swapped" Element und übergibt den Rest, der nicht gewatet ist (aka an ihrem richtigen Platz). d.h

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

ich eine Methode entwickelt, die die Anzahl der Iterationen reduziert durch Teile am Anfang und Ende des Arrays ohne die in früheren Schleifen bestellt wurde.

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

Aber wie @Daniel Fischer sagte in einer früheren Antwort, it doesn't do a lot with larger arrays.