Bubble Sort objects

Question

I need to sort my grocery inventory by name by using bubble sort.

Apparently, my code is not sorting the list by name.
BTW, the data stored inventory comes from a file input.

Here is my code.

public void sortInventoryByName() {
    //TODO: use bubble sort and compareTo
    int n = inventory.size();
    GroceryItem temp;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (inventory.get(j).compareTo(inventory.get(j + 1)) > 0) {
                temp = inventory.get(i);
                inventory.set(i, inventory.get(i + 1));
                inventory.set(i + 1, temp);
            }
        }
    }
}

Here is my compareTo method from my superclass (GroceryItem)

@Override
public int compareTo(Object o) {
    if(getClass() != o.getClass()) {
        throw new IllegalArgumentException();
    }
    else {
        GroceryItem other = (GroceryItem) o;
        return (this.name.compareTo(other.name));
    }
}

Answer 1

Looks like you have some mismatch for comparing the right values.

There are two ways of implementing a bubble sort algorithm with two for loops.

Below made the first loop incremented barrier variable and second is decrementing index.

Thus with every iteration of the outer loop, the lowest value will be moved to the first place (like the smallest bubble will be moved first). The next iteration will skip this first element. And it will last till the list full list will be over.

Your example shows opposite behaviour -> with every iteration for the outer loop the highest element in a list is moved to the end.

It isn't so important how exactly do you want to iterate the inner for loop. The final sorted result is our aim.

Code snippet:

public void sortInventoryByName() {
    int n = inventory.size();
    for (int barrier = 0; barrier < n - 1; barrier++) {
        for (int index = n - 2; index >= barrier; index--) {
            if (inventory.get(index).compareTo(inventory.get(index + 1)) > 0) {
                GroceryItem temp = inventory.get(index);
                inventory.set(index, inventory.get(index + 1));
                inventory.set(index + 1, temp);
            }
        }
    }
}

Your implementation of compareTo() should work fine. So, inventory list should be sorted correctly.

A few notices according to your code:

• you don't need to declare temp variable outside of loops. It is just a temporary variable for swapping two values. Inline declaration and usage will be enough.

• would suggest adding more meaningful names for loop variables instead of just i and j. It increases code readability and understanding in the future

• else block is redundant at compareTo()

@Override
public int compareTo(Object o) {
    if (getClass() != o.getClass()) {
        throw new IllegalArgumentException();
    }
    GroceryItem other = (GroceryItem) o;
    return this.name.compareTo(other.name);
}

Answer 2

I filled in the missing parts of your code. You should read How do I ask a good question and also the link to How to create a Minimal, Reproducible Example.

The below code is the GroceryItem class which only contains a single member, i.e. name, which is the name of the grocery item. Since your question only deals with manipulating this member, I did not try to guess what other data the class needs.

Explanations after the code.

import java.util.ArrayList;
import java.util.List;

public class GroceryItem implements Comparable<GroceryItem> {
    private String  name;

    public GroceryItem(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    @Override // java.lang.Comparable
    public int compareTo(GroceryItem other) {
        if (other == null) {
            return 1;
        }
        else {
            String otherName = other.getName();
            if (name == null) {
                if (otherName == null) {
                    return 0;
                }
                else {
                    return -1;
                }
            }
            else {
                if (otherName == null) {
                    return 1;
                }
                else {
                    return name.compareTo(otherName);
                }
            }
        }
    }

    @Override // java.lang.Object
    public boolean equals(Object other) {
        boolean equal = false;
        if (other instanceof GroceryItem) {
            GroceryItem otherItem = (GroceryItem) other;
            if (name == null) {
                equal = otherItem.getName() == null;
            }
            else {
                equal = name.equals(otherItem.getName());
            }
        }
        return equal;
    }

    @Override // java.lang.Object
    public int hashCode() {
        return name == null ? 0 : name.hashCode();
    }

    @Override // java.lang.Object
    public String toString() {
        return name;
    }

    public static void main(String[] args) {
        List<GroceryItem> inventory = new ArrayList<>();
        inventory.add(new GroceryItem("apple"));
        inventory.add(new GroceryItem("pear"));
        inventory.add(new GroceryItem("banana"));
        inventory.add(new GroceryItem("orange"));
        inventory.add(new GroceryItem("beetroot"));
        inventory.add(new GroceryItem("onion"));
        inventory.add(new GroceryItem("lettuce"));
        inventory.add(new GroceryItem("carrot"));
        inventory.add(new GroceryItem("guava"));
        inventory.add(new GroceryItem("lychee"));
        inventory.add(new GroceryItem("kiwi"));

        int n = inventory.size();
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (inventory.get(j).compareTo(inventory.get(j+1)) > 0) {
                    // swap inventory[j+1] and inventory[j]
                    GroceryItem temp = inventory.get(j);
                    inventory.set(j, inventory.get(j+1));
                    inventory.set(j+1, temp);
                }
            }
        }
        System.out.println();
    }
}

The above code creates a List of GroceryItem objects that contains eleven elements. After populating the List, the bubble sort is performed in the two, nested for loops. Finally the sorted List is printed.

Note that class GroceryItem also implements method toString() so as to make the output human-readable when printing an instance of GroceryItem.

If, in future, you need to use GroceryItem as the key for a java.util.HashMap, then GroceryItem will need to override method hashCode() and if a class overrides method hashCode() then it should also override method equals(). Hence that is why the above code includes those overridden methods. Note that none of those methods – equals(), hashCode() and toString() – are required for the bubble sort.

The oputput when running the above code is:

[apple, banana, beetroot, carrot, guava, kiwi, lettuce, lychee, onion, orange, pear]