FANDOM


QuestionEdit

Write an implementation of bubblesort (in your language of choice).

  1. What is the time complexity?
  2. Is your implementation a stable sort?
  3. Can your implementation be optimized? If so, how?

AnswerEdit

(Paper, not compiler tested)

public static int[] bubblesort(int[] a) {
    int swaps = 0;
    do {
        swaps = 0;
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] > a[i + 1]) {
                int temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
                swaps++;
            }
        }
    } while (swaps > 0);
}
  1. We need to iterate over the entire array for a single pass, and n such passes may be needed, so the time complexity is n^2, where n is size of the array.
  2. Yes, this bubblesort will preserve the order of equal elements, so it is stable.
  3. Yes. The nth pass puts the nth largest number into it's final resting position. So after n passes, we don't need to consider the last n elements in the array, as they are already in their final location:
public static int[] bubblesort(int[] a) {
    int iterations = 0; // optimization
    int swaps = 0;
    do {
        swaps = 0;
        for (int i = 0; i < a.length - 1 - iterations; i++) {
            if (a[i] > a[i + 1]) {
                int temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
                swaps++;
            }
        }
        iterations++;
    } while (swaps > 0);
}

What's missing?Edit

After running the code through a compiler, did you find any mistakes?

The return value is missing:

    return a;

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.