Alg.5 Bubble Sort

From algoexpert.io

Bubble Sort is probably the first sorting algorithm we learned when we study algorithm. In this problem, we will use Bubble Sort to sort the given arrays. What’s more, we will find potential method to make Bubble Sort more efficient.

First, in this problem and future problems which are related to sorting algorithm, we may need to swap elements.

private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

Then, we will apply Bubble Sort to solve this problem. Basically, in Bubble Sort, we need to iterate the original array n times which is its length to determine each element’s position. Here, we will use a little trick to end some unnecessary iterations. In a certain iteration, if there is no swap, it means all the elements are in the expecting positions.

public static int[] bubbleSort(int[] array) {
    // Write your code here.
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = true;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    flag = false;
                }
            }
            if (flag) return array;
      }
    return array;
    }

Time complexity: O(n^2); Space complexity: O(1)

Donate