En İyileştirilmiş Kabarcık Sırala (Java)

Question

Kabarcık sıralamasını nasıl optimize edebileceğimi daha iyi bilmek isterim, böylece ilk geçişten sonra bile daha önce sıralanmış olan öğelere bakar.

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

Biz önümüzdeki geçişte bu 3 unsurları bakan böylece nasıl kodumu değiştirebilir, [4,5,6] sıralanmış sırada zaten olduklarını gözlemlemek? (yani sıralama daha verimli olur mu?) Yinelemeli bir yöntem önerir misiniz?

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

Zaman ayırdığınız için teşekkürler! Her şeyden

Answer 1

Birincisi, bir-dışı sınırları erişebilir: j == a.length-1 için

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

, böylece döngü koşulu yerine j < a.length-1 olmalıdır.

Fakat, Kabarcık sıralamada, sen k geçer sonra, büyük k elemanları dizisinin k son girişlerinde sıralanır biliyoruz, bu nedenle geleneksel Kabarcık sıralama hala olur, Şimdi

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

kullanır dizinin en büyük öğelerin uzun sıralanmış kuyruğu olduğunda gereksiz yinelemeler yapın, bundan sonra sırayla k,k-1,...,1 ilk k öğeleri ve k+1100000000 var. Standart Kabarcık sıralaması, tüm diziden (neredeyse) k kez geçecektir. Eğer son takas yapılmış nerede hatırlarsanız

Fakat, bunu

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

entire yalnız bir kez geçmek ile yukarıdaki örneği sıralamak istiyorum, bu dizin sonra, büyük elemanları sırayla olduğunu biliyoruz dizi ve kalan sadece bir (kısa) önek ile geçer.

Tabii ki, genel olarak, bu size çok fazla almaz, ama daha sonra bir Kabarcık sıralamasını optimize etmek zaten oldukça boş bir uygulamadır.

Answer 2

İç döngü için bir "boyut" değişkeni kullanmalı ve her döngüdeki en son değiştirilen öğeye değiştirmelisiniz. Bu şekilde iç döngünüz en son "değiştirilmiş" öğeye gider ve geri kalanları geçmeden geçirir (aka doğru yerlerinde). Önceki döngülerde sipariş edilmiş olan dizinin başında ve sonunda parçaları hariç tutarak yineleme sayısını azaltan bir yöntem tasarlamışlardır

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

yani.

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

Ama @Daniel Fischer olarak