Bubble sorting a 2D ArrayList

Question

I am trying to bubble sort a 2d ArrayList which has 7 columns in the inner list. The third column is the price. I am trying to compare the price column of the rows and swap the row having the greater price with the row having the smaller price. It means in the end the ArrayList should have rows in ascending order of price.

But every time while swapping the rows all the elements in the greater row are changed to the same elements that are in the smaller row. Below is the code.

boolean found = true;
do{
    found = false;
    for(int i = 0; i <= rc; i++) {
        if(i + 1 <= rc) {
            if(Integer.parseInt(list.get(i).get(3)) > Integer.parseInt(list.get(i + 1).get(3))) {
                ArrayList<String> greater = list.get(i);
                ArrayList<String> smaller = list.get(i + 1);
                for(int k = 0; k <= 7; k++) {
                    list.get(i).set(k, smaller.get(k));
                    list.get(i + 1).set(k, greater.get(k));
                }   
                found = true;
            }
        }
    }
} while(found == true);

Original array list:

[[1, sagarmatha, 5000, 7000, Two-Star, Two-Person-Room, 2, Resturant],
 [2, barahi, 4000, 4000, Three-Star, One-Person-Room, 1, Free-WIFI]]

After Sorting:

[[2, barahi, 4000, 4000, Three-Star, One-Person-Room, 1, Free-WIFI],
 [2, barahi, 4000, 4000, Three-Star, One-Person-Room, 1, Free-WIFI]]

Answer 1

Let's start with the most efficient way to swap two elements in an ArrayList:

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

This is efficient because it doesn't touch the elements in any way, just moves the references around. It uses set, so no elements in the list are ever shifted and nothing gets reallocated.

Now let's take a look at how your swap is written:

ArrayList<String> greater = list.get(i);
ArrayList<String> smaller = list.get(i + 1);
for(int k = 0; k <= 7; k++) {
    list.get(i).set(k, smaller.get(k));
    list.get(i + 1).set(k, greater.get(k));
}

The for loop attempts to copy the data of one list into the other, which is not optimal to begin with. The real issue is that you aren't using a temporary variable to hold the swap (notice how I did it in my function above). Let's take a look at what happens to the kth element of the data during your swap:

1. Start with smaller.get(k) -> "A" and greater.get(k) -> "B"
2. After list.get(i).set(k, smaller.get(k));, you end up with smaller.get(k) -> "A" and greater.get(k) -> "A" since list.get(i) == greater.
3. list.get(i + 1).set(k, greater.get(k)); just reassigns "A" back to smaller since the first line clobbered whatever was originally in greater.

To fix this, you need to first store the original value of greater.get(k) into a temporary variable:

ArrayList<String> greater = list.get(i);
ArrayList<String> smaller = list.get(i + 1);
for(int k = 0; k <= 7; k++) {
    String temp = greater.get(k);
    greater.set(k, smaller.get(k));
    smaller.set(k, temp);
}