Bidirectionnal Bubble Сортировать по Java?

Question

Мне нужно реализовать двунаправленную сортировку пузырьков в моем коде.

Иными словами, in будет идти слева направо, перенося наибольшее значение.

Но когда оно достигает out, оно должно быть обратным и идти справа налево, перенося наименьшее значение.

Я рекомендую ввести еще один индекс out, кроме того, текущий.

Это то, что у меня есть до сих пор - всего 2 петли. Я предполагаю, что мне нужно как-то их объединить?

public void bubbleSort() { 
    int out, in; // nElems in my case is 4, because I have 4 elements in my array 

    for(out=nElems-1; out>1; out--) // outer loop backward 
     for(in=out; in>1; in--) // inner loop backward 
      if(a[in] < a[in-1]) 
       swap(in, in-1); 

    for(out=0; out<nElems; out++) // outer loop forward 
     for(in=0; in<out; in++) // inner loop forward 
      if(a[in] > a[in+1]) 
       swap(in, in+1); 

Answer 1

public void bidirectionalBubbleSort() 
    { 
     int left = 0, right = a.length-1; 
     while (left < right) 
     { 
      for (int pos = left; pos < right; pos++) 
      { 
      if (a[pos] > a[pos+1]) 
       swap(pos, pos+1); 
      } 
      right--; 


      for (int pos = right; pos > left; pos--) 
      { 
      if (a[pos] < a[pos-1]) 
       swap(pos, pos-1); 
      } 
      left++; 
     } 
    } 

Answer 2

Я рекомендую вам разделить метод на куски, которые вы можете постигнуть, как:

public static boolean swap(int[] numbers, int i, int j) { 
    int temp = numbers[i]; 
    numbers[i] = numbers[j]; 
    numbers[j] = temp; 
    return true; 
} 

static boolean leftSide(int[] numbers, int i, int j) { 
    boolean swapped = false; 
    for (int k = i; k < j; k++) 
     if (numbers[k] > numbers[k + 1]) 
      swapped = swap(numbers, k, k + 1); 
    return swapped; 
} 

static boolean rightSide(int[] numbers, int i, int j) { 
    boolean swapped = false; 
    for (int k = j; k > i; k--) 
     if (numbers[k] < numbers[k - 1]) 
      swapped = swap(numbers, k, k - 1); 
    return swapped; 
} 

public static void cocktailSort(int[] numbers) { 
    boolean swapped = true; 
    int i = -1; 
    int j = numbers.length - 1; 

    while (i++ < j && swapped) 
     if (swapped = leftSide(numbers, i, j)) 
      swapped = rightSide(numbers, i, j--); 
} 

И проверить:

public static void main(String[] args) { 
    int x[] = new int[] { 2, 6, 3, 7, 8, 3, 7, 5, 4 }; 
    cocktailSort(x); 
    System.out.println(java.util.Arrays.toString(x)); 
} 

Выход:

[2, 3, 3, 4, 5, 6, 7, 7, 8] 

Answer 3

boolean f1 = false, f2 = false; 
    outer: 
    for (int i=0; i < arr.length-1; i++) 
      for (int j=i; j< arr.length - i -1; j++) { 

       if(arr[j] >= arr[j+1]){ 
        f1 = true; 
        int t = arr[j]; 
        arr[j] = arr[j+1]; 
        arr[j+1] = t; 
       } 

       if(arr[arr.length - j -1] <= arr[arr.length - j - 2]){ 

        f2 = true; 
        int t = arr[arr.length - j -2]; 
        arr[arr.length - j -2] = arr[arr.length - j -1]; 
        arr[arr.length -j -1] = t; 
       } 

       /** 
       * @param k: iterator variable thats prints each pass..(optional) 
       */ 
       for (int k:arr) 
        System.out.print(" "+k); 
       System.out.println(" "+i); 

       //Ultimate break condition 
       if(j == arr.length - j -2 && (!f1 && !f2)) 
        break outer; 


      } 

Answer 4

Двунаправленный пузыря Сортировка с использованием только 2 петли & 2 индексные переменные.

public void bubbleSort(){ 
    for(int out=0;out<nElems/2;out++){ 
     boolean forward = true; 
     for (int in = out;in !=(forward ? out-1 : out) 
         ;in = forward ? in + 1 : in - 1) 
     { 
      if (in == nElems - (out + 1)) 
       forward = false; 
      if (a[forward ? in + 1 : in] < a[forward?in:in-1]) 
       swap(forward ? in + 1 : in - 1, in); 
     } 
    } 
} 

Answer 5

Двунаправленная пузырьковая сортировка, сортировка переменный: массив []

//-------------------------------------------// 
//biderctioanal bubble sort - coctail sort 
public void bidirBubbleSort(){ 
    for(int i=1; i<length/2; i++){ 
     for(int j=0; j<length-i; j++) 
      if(array[j]>array[j+1]) 
       swap(j, j+1); 
     for(int j=length-i; j>=i; j--) 
      if(array[j]<array[j-1]) 
       swap(j, j-1); 
    } 
} 
//-------------------------------------------// 
//swap 2 elements 
public void swap(int index1, int index2){ 
    int temp=array[index1]; 
    array[index1]=array[index2]; 
    array[index2]=temp; 
} 
//-------------------------------------------// 

На 10_000 случайным образом выбранные элементы, стандартный пузырь сорта завершаются в 410ms и двунаправленная пузырьковая сортировка в 319ms