CODEWITHSUNDEEP
javaalgorithmsortingbubble-sort
Sahat Yalkabov
Sahat Yalkabov

Reputation: 33624

Bidirectionnal Bubble Sort in Java?

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

Upvotes: 0

Views: 4545

Answers (5)

Shone
Shone

Reputation: 11

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

Upvotes: 0

viktor
viktor

Reputation: 1

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

Upvotes: 0

Arun Dutta
Arun Dutta

Reputation: 119

    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;


           }

Upvotes: 0

Margus
Margus

Reputation: 20038

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]

Upvotes: 1

jlewis42
jlewis42

Reputation: 923

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

Upvotes: 4

Related Questions