开发者

Bidirectionnal Bubble Sort in Java?

开发者 https://www.devze.com 2023-01-18 10:32 出处:网络
I need to implement the bidirectional bubble sort in my code. In other words in will go from left to right first carrying the largest value.

I need to implement the bidirectional bubble sort in my code.

In other words in will go from left to right first carrying the largest value.

But when it reaches out, it should reverse and go from right to left carrying the smallest value.

I am advised to to implement another out index in addition the current one.

This is what I have so far - just 2 loops. I am guessing I have to combine them somehow?

    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; o开发者_JS百科ut<nElems; out++) // outer loop forward
        for(in=0; in<out; in++) // inner loop forward
            if(a[in] > a[in+1])
                swap(in, in+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++;
       }
   }  


I recommend you split the method up for chunks that you can comprehend, like:

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

And to test it:

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

Output:

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


    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;


           }


Bidirectional Bubble Sort using only 2 loops & 2 index variables.

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


Bidirectional bubble sort, sorting variable: array[]

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

On 10_000 randomly selected elements, standard bubble sorts completes in 410ms and bidirectional bubble sort in 319ms

0

精彩评论

暂无评论...
验证码 换一张
取 消