Phân loại bong bóng được tối ưu hóa (Java)

Question

Tôi muốn biết cách khác để tối ưu hóa sắp xếp bong bóng để nó xem các yếu tố đã được sắp xếp, ngay cả sau lần vượt qua đầu tiên.

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

Chúng tôi nhận thấy rằng [4,5,6] đã được sắp xếp theo thứ tự, làm cách nào để sửa đổi mã của tôi để xem 3 phần tử này trong lần vượt qua tiếp theo? (có nghĩa là sắp xếp sẽ hiệu quả hơn?) Bạn có đề xuất phương pháp đệ quy không?

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

Cảm ơn bạn đã dành thời gian!

Answer 1

Trước hết, bạn có quyền truy cập out-of-bounds:

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

cho j == a.length-1, vì vậy điều kiện vòng lặp nên thà làm j < a.length-1.

Nhưng, trong Bubble sort, bạn biết rằng sau khi k đèo, các k yếu tố lớn nhất đều được sắp xếp tại các mục cuối cùng k của mảng, do đó Bubble sort thường sử dụng

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

Bây giờ, mà có thể vẫn thực hiện nhiều lần lặp không cần thiết khi mảng có đuôi được sắp xếp dài của các phần tử lớn nhất, giả sử bạn có k,k-1,...,1 là các phần tử k đầu tiên và k+1 đến 100000000 theo thứ tự sau đó. Loại Bubble tiêu chuẩn sẽ vượt qua k lần thông qua (gần như) toàn bộ mảng.

Nhưng nếu bạn nhớ nơi bạn đã thực hiện hoán đổi cuối cùng của bạn, bạn biết rằng sau khi chỉ số đó, có những yếu tố lớn nhất trong trật tự, vì vậy

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

sẽ sắp xếp các ví dụ trên chỉ với một đường chuyền thông qua toàn bộ mảng, và phần còn lại chỉ đi qua một tiền tố (ngắn).

Tất nhiên, nói chung, điều đó sẽ không mua cho bạn nhiều, nhưng sau đó tối ưu hóa một loại Bubble là một bài tập khá vô ích anyway.

Answer 2

bạn nên sử dụng biến "kích thước" cho vòng lặp bên trong và thay đổi thành phần tử được hoán đổi mới nhất trong mỗi chu kỳ.Đây là cách vòng lặp bên trong của bạn chuyển đến phần tử "hoán đổi" mới nhất và chuyển phần còn lại không được thay đổi (aka trong chính xác của họ). tức là

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

tôi nghĩ ra một phương pháp làm giảm số lần lặp lại bằng cách loại trừ các bộ phận ở đầu và cuối của mảng đã được sắp xếp theo vòng trước.

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

Nhưng khi @Daniel Fischer nói trong một cuộc trả lời trước đó, it doesn't do a lot with larger arrays.