2
\$\begingroup\$

I've become a bit rusty in Java. This is an attempt at brushing up my skills.

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list.

Code

import java.util.Comparator;
import java.util.Objects;

public class Sorting {
    /**
     * Day 07 - Bubble Sort
     * In place sort given array with bubble sort algorithm
     *
     * @param data       array
     * @param comparator implementation of comparator for given data type
     * @param ascending  sort order
     * @param <T>        data type of array elements
     * @return sorted data array
     */
    public static <T> T[] bubbleSort(T[] data, Comparator<T> comparator, boolean ascending) {
        Objects.requireNonNull(data);
        int len = data.length;
        if (len <= 0) return data;
        T temp;
        boolean swapped;
        for (int i = 0; i < len - 1; i++) {
            swapped  = false;
            for (int j = 0; j < len - 1 - i; j++) {
                if ((comparator.compare(data[j], data[j + 1]) * (ascending ? 1 : -1)) > 0) {
                    temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
        return data;
    }
}

Test cases

import org.testng.Assert;
import org.testng.annotations.Test;


public class TestSorting {
    @Test
    public void testBubbleSort() {
        Assert.assertEquals(asc(1, 2, 3), ar(1, 2, 3));
        Assert.assertEquals(asc(3, 2, 1), ar(1, 2, 3));
        Assert.assertEquals(asc(2, 0, -1, 2, 1), ar(-1, 0, 1, 2, 2));

        Assert.assertEquals(dsc(1, 2, 3), ar(3, 2, 1));
        Assert.assertEquals(dsc(3, 2, 1), ar(3, 2, 1));
        Assert.assertEquals(dsc(2, 0, -1, 2, 1), ar(2, 2, 1, 0, -1));

        Assert.assertEquals(asc(2, 1), ar(1, 2));
        Assert.assertEquals(asc(1), ar(1));
        Assert.assertEquals(asc(), ar());
        Assert.assertEquals(dsc(1), ar(1));
        Assert.assertEquals(dsc(), ar());
    }

    @Test(expectedExceptions = {NullPointerException.class})
    public void testNullExcept() {
        Sorting.bubbleSort(null, Integer::compare, true);
    }

    private static Integer[] ar(Integer... objects) {
        return objects;
    }

    private static Integer[] asc(Integer... objects) {
        return Sorting.bubbleSort(objects, Integer::compare, true);
    }

    private static Integer[] dsc(Integer... objects) {
        return Sorting.bubbleSort(objects, Integer::compare, false);
    }
}
\$\endgroup\$
3
\$\begingroup\$

Your code looks generally OK in my book (i.e. not being that rusty ;-))

A few pointers though:

  • Generally keep variable scope as low as possible. T temp and boolean swapped can be declared at the place where they are needed initially.
  • Though I see the idea of multiplying with 1 or -1, the expression looks too "magic" for me. As Comparators have a reversed() method these days, I recommend to use that.

Putting this advice to use:

public static <T> T[] bubbleSort(T[] data, Comparator<T> comparator, boolean ascending) {
    Objects.requireNonNull(data);
    int len = data.length;
    if (len <= 0) return data;
    Comparator<T> actualComparator = ascending ? comparator : comparator.reversed();

    for (int i = 0; i < len - 1; i++) {
        boolean swapped  = false;
        for (int j = 0; j < len - 1 - i; j++) {
            if (actualComparator.compare(data[j], data[j + 1]) > 0) {
                T temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
    return data;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks mtj, :) had no idea bout the .reversed() construct. \$\endgroup\$ – bhathiya-perera Dec 13 '19 at 13:41
1
\$\begingroup\$
        int len = data.length;
        if (len <= 0) return data;

While this will of course work, it seems unnecessary. You could just say

        if (data.length <= 0) {
          return data;
        }

There is no efficiency or readability reason to make the other name. In fact, you actively harm readability by using the extraneous variable. Readers have to remember that len is the same thing as data.length. If you just used data.length, we wouldn't have to make that link.

        T temp;
        boolean swapped;
        for (int i = 0; i < len - 1; i++) {
            swapped  = false;
            for (int j = 0; j < len - 1 - i; j++) {

You use i for one purpose and one purpose only. That is to subtract from len - 1. You could just say

        for (int i = data.length - 1; i > 0; i--) {
            boolean swapped = false;
            for (int j = 0; j < i; j++) {

Then you don't have to write the length as much, so it matters even less to make a short alias for it.

This also saves two math operations per iteration. Although the compiler might remove that for you anyway.

It doesn't help to declare the variables outside the loop and it may hurt. It hurts readability in that it moves the declaration and use farther apart. So readers have to look at more code to find declaration, initialization, and use.

It also may hurt in that if the variable is actually stored in memory rather than just register, it's going to take longer to access. Hopefully the compiler will realize that they don't need the larger scope. But that optimization wouldn't be necessary if you'd given them minimal scope in the first place.

\$\endgroup\$
  • \$\begingroup\$ This is very useful. :) \$\endgroup\$ – bhathiya-perera Dec 14 '19 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.