Как я могу использовать Comparator для реализации Bubble сортировки? - PullRequest
Новая
       4

Как я могу использовать Comparator для реализации Bubble сортировки?

1 голос
/ 13 апреля 2011

Как я могу реализовать Bubble sort с помощью Comparator?

Спасибо.

Так выглядит мой компаратор: 

class ColumnSorter implements Comparator {
  int colIndex;

  ColumnSorter(int colIndex) {
    this.colIndex = colIndex;
  }

  public int compare(Object a, Object b) {
  Vector v1 = (Vector) a;
  Vector v2 = (Vector) b;
  Object o1 = v1.get(colIndex);
  Object o2 = v2.get(colIndex);

  if (o1 instanceof String && ((String) o1).length() == 0) {
    o1 = null;
  }
  if (o2 instanceof String && ((String) o2).length() == 0) {
    o2 = null;
  }

  if (o1 == null && o2 == null) {
    return 0;
  } else if (o1 == null) {
    return 1;
  } else if (o2 == null) {
    return -1;
  } else if (o1 instanceof Comparable) {
      return ((Comparable) o1).compareTo(o2);
  } else {
    return o1.toString().compareTo(o2.toString());
 }
}
}

Ответы [ 3 ]

3 голосов
/ 13 апреля 2011

Вы реализуете пузырьковую сортировку, как если бы вы, скажем, <.Затем вы заменяете использование < на someComparator.compare(Object o1, Object o2).

Вот «правило перевода»: 

if (arr[i] < arr[j]) {
    ...
}

становится 

if (someComparator.compare(arr[i], arr[j]) < 0) {
    ...
}

(Если вы использовали>, вы бы использовали > 0 вместо < 0.)

Для получения более подробной информации обратитесь к документации для Comparator.Вот первое предложение:

Сравнивает два аргумента для порядка.Возвращает отрицательное целое, ноль или положительное целое число, поскольку первый аргумент меньше, равен или больше второго.

1 голос
/ 13 апреля 2011

Я предполагаю, что вы знаете, как кодировать Bubble Sort, и проблема в том, как использовать Comparator.

На каждой итерации в пузырьковой сортировке вы должны сравнить два элемента, чтобы решить, в каком порядке они должны быть. Где бы вы сказали:

if item1 < item2 then

Вы сейчас пишете:

if( comparator.compare(item1,item2) < 0 ) {

Если бы вы сказали:

if item1 > item2 then

тогда пишешь

if( comparator.compare(item1,item2) > 0 ) {

Обратите внимание, что < и > остаются неизменными, и вы сохраняете порядок элементов одинаковым. Если вы придерживаетесь этого правила, сравнение должно работать нормально, так что все, что осталось - это фактическая сортировка пузырьков.

0 голосов
/ 13 апреля 2011

Большой вопрос, почему на земле вы хотели бы реализовать сортировку пузырей самостоятельно. Пузырьковая сортировка - один из самых медленных алгоритмов сортировки.

Использование алгоритма сортировки, предоставленного JDK в java.util.Collections.sort(), будет намного быстрее и сэкономит вам довольно много строк кода. У Collections.sort() есть метод, который принимает Comparator, или метод без него, использующий естественное упорядочение объектов (если они реализуют интерфейс Comparable).

...