Пузырьковая сортировка 2D ArrayList - PullRequest
Новая
       29

Пузырьковая сортировка 2D ArrayList

0 голосов
/ 21 января 2019

Я пытаюсь пузырьковой сортировки 2d ArrayList, который имеет 7 столбцов во внутреннем списке. Третий столбец - цена. Я пытаюсь сравнить столбец цен строк и поменять местами строку с большей ценой на строку с меньшей ценой. Это означает, что в конце ArrayList должен иметь строки в порядке возрастания цены.

Но каждый раз при замене строк все элементы в большей строке заменяются на те же элементы, которые находятся в меньшей строке. Ниже приведен код. 

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

Исходный список массивов: 

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

После сортировки: 

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

Ответы [ 2 ]

0 голосов
/ 21 января 2019

Давайте начнем с самого эффективного способа поменять два элемента в 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);
}

Это эффективно, потому что оно никак не касается элементов, а просто перемещает ссылки. Он использует set, поэтому никакие элементы в списке никогда не сдвигаются и ничего не перераспределяется.

Теперь давайте посмотрим, как написан ваш своп: 

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

Цикл for пытается скопировать данные одного списка в другой, что не является оптимальным для начала. Реальная проблема в том, что вы не используете временную переменную для хранения свопа (обратите внимание, как я это делал в своей функции выше). Давайте посмотрим, что происходит с k элементом данных во время обмена:

  1. Начните с smaller.get(k) -> «A» и greater.get(k) -> «B»
  2. После list.get(i).set(k, smaller.get(k)); вы получите smaller.get(k) -> «A» и greater.get(k) -> «A», начиная с list.get(i) == greater.
  3. list.get(i + 1).set(k, greater.get(k)); просто переназначает "A" обратно на smaller, так как первая строка перекрыла все, что было изначально в greater.

Чтобы это исправить, вам нужно сначала сохранить исходное значение greater.get(k) во временной переменной: 

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);
}
0 голосов
/ 21 января 2019

В вашем случае вы не создаете новый список.Вместо этого вы используете ссылки из своих списков.Поэтому: 

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

Давайте посмотрим, что происходит в цикле: 

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"

Когда вы изменили элемент первого списка, значение greater также изменится, потому что greater и list.get(0) - это один и тот же объект, а не копии друг друга.Вам нужно создать еще один массив, а затем скопировать значения.Или вы всегда можете поменять списки массивов напрямую, используя временную переменную, например :: 

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