CODEWITHSUNDEEP
javasortingbubble-sort
ripper234
ripper234

Reputation: 230038

Riddle: Spot the serious bug in this bubble sort implementation

(No, this isn't a homework assignment, I just found the bug and thought it might be useful to share it here)

import java.util.List;

public class BubbleSorter {

    public <T extends Comparable<T>> void sort(List<T> list) {
        while (true) {
            boolean didWork = false;
            for (int i = 0; i < list.size() - 1; ++i) {
                if (list.get(i).compareTo(list.get(i + 1)) > 0) {
                    swap(list, i, i + 1);
                    didWork = true;
                    break;
                }
            }

            if (!didWork)
                return;
        }
    }

    private static <T> void swap(List<T> list, int i, int j) {
        T tmp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, tmp);
    }
}

Upvotes: 2

Views: 493

Answers (2)

Nikita Rybak
Nikita Rybak

Reputation: 68006

Not a bug in the strictest sense, but doing break; when you find inversion gives your sorting O(n^3) complexity, which is hardly desirable. break can just be removed.

Upvotes: 5

Luke Maurer
Luke Maurer

Reputation: 8245

The swap should be setting j, not i+1.

Upvotes: 0

Related Questions