Двунаправленная пузырьковая сортировка на 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

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

//-------------------------------------------//
//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 случайно выбранных элементов стандартные пузырьковые сортировки завершаются за 410 мс, а двунаправленная пузырьковая сортировка за 319 мс

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

    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;


           }