Codecademy Logo

Bubble Sort

Bubble Sort Algorithm

The Bubble Sort algorithm is a simple algorithm to sort a list of N numbers in ascending order. Bubble sort works by iterating through a list and checking whether the current element is larger or smaller than the next element.

This algorithm consists of an outer iteration and an inner iteration. In the inner iteration, the first and second elements are first compared and swapped so that the second element has a higher value than the first. This is repeated for the subsequent second and third element pairs and so forth until the last pair of (N-2, N-1) elements is compared. At the end of the inner iteration, the largest element appears last. This is repeated for all elements of the list in the outer iteration.

Bubble Sort Algorithm for inner iteration.

Bubble Sort Swapping Variables

The Bubble Sort algorithm requires swapping of variables in order to sort them. The swapping algorithm is dependent on the programming language. For most languages, a temporary variable is needed to hold one of the values being swapped:

temp_variable = number_1
number_1 = number_2
number_2 = temp_variable

For others, the swapping can be done in a single assignment:

number_1, number_2 = number_2, number_1
Swapping variables used in Bubble Sort

Swapping in Sorting Algorithms (Java)

Certain sorting algorithms like Bubble sort and Quicksort require swapping two elements in an array without creating a new copy of the array. To do so, we can implement the following Java function:

public static void swap(int[] arr, int indexOne, int indexTwo) {
    int temp = arr[indexTwo];
    arr[indexTwo] = arr[indexOne];
    arr[indexOne] = temp;
}

This function uses a temporary variable to store the value of one of the elements during the swap.

Bubble Sort In Java General

Bubble sort is an algorithm that sorts elements of a list in ascending order. Bubble sort works by iterating through an array and checking whether the current element is larger or smaller than the next element. If the current element is larger, then they swap. If the current element is smaller, then it stays in place. Then, the pointer moves to the next index. The algorithm typically iterates through the array numerous times, while no more elements are able to “bubble” up. The Java implementation looks like this:

    public int[] bubbleSort(int input[]) {
        boolean swapping = true;
        while (swapping) {
            swapping = false;
            for (int i = 0; i < input.length - 1; i++) {
                if (input[i] > input[i+1]) {
                    swap(input, i, i+1);
                    swapping = true;
                }
            }
        }


        return input;
    }

Quick Sort Java implementation

The Java implementation of quicksort is as follows:

    public int[] quicksort(int[] arr, int start, int end) {
        if (start == end) {
            return arr;
        }
        int index = partition(arr, start, end);
        if (start < index - 1) {
            quicksort(arr, start, index - 1);
        }
        if (index < end) {
            quicksort(arr, index, end);
        }
        return arr;
    }


    public int partition(int[] arr, int leftIndex, int rightIndex) {
        int pivot = arr[Math.floorDiv((leftIndex + rightIndex), 2)];
        System.out.println("The pivot value is: " + pivot);


        while (leftIndex <= rightIndex) {
            while (arr[leftIndex] < pivot) {
                leftIndex++;
            }
            while (arr[rightIndex] > pivot) {
                rightIndex--;
            }
            if (leftIndex <= rightIndex) {
                swap(arr, leftIndex, rightIndex);
                System.out.println("Swapping " + arr[leftIndex] + " and " + arr[rightIndex]);
                leftIndex++;
                rightIndex--;
            }
        }
        return leftIndex;
    }

Bubble Sort Big-O Runtime

The Bubble Sort algorithm utilizes two loops: an outer loop to iterate over each element in the input list, and an inner loop to iterate, compare and exchange a pair of values in the list. The inner loop takes (N-1) iterations while the outer loop takes N iterations. Hence, the Big-O runtime for the algorithm is the product of O(N) and O(N-1), which is O(N^2).

Next

Learn more on Codecademy