Bidirectional Bubble Sort

Question

I have to solve the following problem. So initially i had a bubble sort and now i modified it to make it bidirectional. The following is my solution.

public void bubbleSort() {
    int temp;
    int out;
    int outNew = 0;
    int in;

    for (out = nElems - 1; out > outNew; out--) {

        for (in = 0; in < out; in++) {

            if (a[in] > a[in + 1]) {
                temp = a[in + 1];
                a[in + 1] = a[in];
                a[in] = temp;
            }
        }

        for (int j = in - 1; j > outNew; j--) {

            if (a[j] < a[j - 1]) {
                temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
            }

        }

        outNew++;

    }

}

When i call my bubble sort to sort few random numbers in an array i created it seems to be sorting fine. My question is rather to all you developers whether my solution is satisfying the question posted above and also what could i have done differently to make this solution more effective (if possible) . I am sorry if this is a little open question , i am usually on here looking for hints and suggestions rather than code as it helps me learn better. I appreciate all answers and am open to any suggestions.

Answer 1

Your first inner loop seems a bit inefficient, since your array will be partially sorted at both ends. After the first round (one time incrementing the index, one time decreasing it) the first and the last element will already be correct, hence no need to start at index 0 (and the task/exercise requires that btw).

The following ASCII art demonstrates, on which indices the algorithm should operate on at the example of a array with 9 elements (including the indices reached with in+1 and j-1; all indices between the | should be considered):

position:   0    1    2    3    4    5    6    7    8
------------------------------------------------------------
          |                   ->                       |
          |                   <-                 |
               |              ->                 |
               |              <-             |
                    |         ->             |
                    |         <-        |
                         |    ->        |
                         |    <-   |

But what your algorithm does is:

position:   0    1    2    3    4    5    6    7    8
------------------------------------------------------------
          |                     ->                     |
          |                     <-                     |
          |                     ->                |
               |                <-                |
          |                     ->           |
                    |           <-           |
          |                     ->      |
                         |      <-      |

You'll have to fix the the initial index of the first inner for loop.

Answer 2

In short, I don't think you can me more effective AND answer the question at the same time. It's pretty explicit in that you have to carry your item to the right until you find one smaller, then take that slightly smaller than the last you carried and bring it up. I don't think there's any performance gain from the regular unidirectional bubble sort but if you're going to make it bidirectional, then this is the way to do it.

How can you tell? Well since there's no performance gain/deterioration to get, the left->right code and the right->left code should be perfectly symmetrical (since they're identical in performance terms). In your case, there are so I'd say it looks good.

Thinking a bit deeper, there's probably some slight optimization to get from being bidirectional, just because you're getting an item you just looked at so you know you can bring to the left from it's initial position, skipping the right side of the array. But in the end, it's negligible and it's still O(n²) performance, no matter how you slice it.