최적화 된 버블 정렬 (Java)

Question

버블 정렬을 최적화 할 수있는 방법을 알고 싶습니다. 이미 정렬 된 요소를 간과 할 수 없으므로 첫 번째 전달 후에도 마찬가지입니다.

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

우리는 다음 패스에서이 3 개 요소를 내려다 있도록하는 방법을 내 코드를 수정할 수 있습니다, [4,5,6]가 정렬 된 순서에 이미있는 것을 관찰? (이는 정렬이 더 효율적이라는 것을 의미합니까?) 재귀 적 방법을 제안합니까?

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

감사합니다. 모든

Answer 1

먼저, 당신은 범위를 벗어날 액세스 있습니다 j == a.length-1에 대한

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

를, 그래서 루프 조건은 오히려 j < a.length-1해야한다.

하지만, 버블 정렬, 당신은 k 패스 후, 가장 큰 k 요소가 배열의 k 마지막 항목으로 분류되어 있음을 알고, 그래서 기존의 버블 정렬은 여전히 ​​것, 이제

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

전체를 통해 하나 개의 패스 위의 예를 정렬 할 것이다, 그 인덱스 이후 가장 큰 요소 순서가 있다는 것을 알고 배열이고 나머지는 (짧은) 접두사를 통해서만 전달됩니다.

물론, 일반적으로 많이 구매하지는 않지만 버블 정렬을 최적화하는 것은 다소 쓸데없는 운동입니다.

Answer 2

내부 루프에 "size"변수를 사용하고 각 사이클에서 가장 최근에 스왑 된 요소로 변경해야합니다. 이렇게하면 내부 루프가 최신 "스왑 된"요소까지 올라가고 스왑되지 않은 나머지 부분은 전달됩니다 일명 정확한 위치에 있음). 내가 이전 루프에서 주문 된 배열의 시작과 끝 부분을 제외하여 반복의 수를 감소하는 방법을 고안

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

즉.

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 같은

는