CODEWITHSUNDEEP
javabubble-sort
krisha mahat
krisha mahat

Reputation: 69

Bubble sorting a 2D ArrayList

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]]

Upvotes: 6

Views: 362

Answers (2)

Mad Physicist
Mad Physicist

Reputation: 114320

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);
}

Upvotes: 1

Yamuk
Yamuk

Reputation: 769

In your case, you are not creating a new list. Instead you are using the references of your lists. Therefore:

greater = list.get(i);  //here greater _references_ the i'th element
                        //[1, sagarmatha, 5000, 7000, Two-Star, Two-Person-Room, 2, Resturant]

smaller = list.get(i+1); //here greater _references_ the i+1'th element
                         //[2, barahi, 4000, 4000, Three-Star, One-Person-Room, 1, Free-WIFI]

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

Let's see what happens in the loop:

when k = 0: 
before assignment: list.get(i).get(0) = greater.get(0) = 1
                   list.get(i+1).get(0) = smaller.get(0) = 2

after assignment: list.get(i).get(0) = greater.get(0) = 2 which is the value of "smaller"

When you changed the element of the first list, greater's value is changed as well because greater and list.get(0) are basically the same object, not copies of each other. You need to create another array and then copy the values afterwards. Or you can always swap the array lists directly using a temporary variable, like::

private void swap (ArrayList list, int index1, int index2) {
    object temp = ArrayList[index1];
    ArrayList[index1] = ArrayList[index2];
    ArrayList[index2] = temp;
}

Upvotes: 0

Related Questions