Quicksort не работает в некоторых случаях

-1

Поскольку я тестировал свою быструю сортировку, я заметил еще одну проблему. Иногда он упорядочивает массив в алфавитном порядке, а иногда - нет. Например, если у меня есть p, o, j, l как мой массив, он сортирует его до j, o, l, p, что неверно, потому что l должно быть до o Однако, если я добавлю a в массив, он сортирует до a, j, l, o, p, что верно. Почему это происходит?Quicksort не работает в некоторых случаях

Код:

private ArrayList<String> sort(ArrayList<String> ar, int lo, int hi){ 
     if (lo < hi){ 
      int splitPoint = partition(ar, lo, hi); 
      sort(ar, lo, splitPoint); 
      sort(ar, splitPoint +1, hi); 
     } 
     return ar; 
    } 

    private int partition(ArrayList<String> ar, int lo, int hi){ 
     String pivot = ar.get(lo); 
     lo--; 
     hi++; 
     while (true){ 
      lo++; 
      hi--; 
      while (lo<hi && ar.get(lo).compareTo(pivot) < 0){ 
       lo++; 
      } 
      while (hi>lo && ar.get(hi).compareTo(pivot) >= 0){ 
       hi--; 
      } 
      if (lo<hi){ 
       swap(ar, lo, hi); 
      }else { 
       return hi; 
      } 
     } 
    } 

    private ArrayList<String> swap(ArrayList<String> ar, int a, int b){ 
     String temp = ar.get(a); 
     ar.set(a, ar.get(b)); 
     ar.set(b, temp); 
     return ar; 
    }

источник

2014-02-08 Cristian Gutu

Насколько я понимаю, вы не меняете положение поворотного элемента. Вы просто меняете привет.

В конце вы должны поместить стержень в правильное положение, а затем вернуть его.

источник

2014-02-08 16:52:11

Я продолжаю сравнивать и заменять, когда 'lo

Насколько я понимаю, изначально lo == pivot. Следовательно, первое сравнение arr [lo] с arr [pivot] должно быть равно нулю, а lo будет увеличиваться. стержень должен оставаться на своем месте. –

Исправить. Но я не перемещаю стержень, я просто переустанавливаю ценности. Странно, что это работает во всех других случаях, кроме этого. –

Я думаю, что существует опасность в последней итерации вашей петли.

Предположим, у вас был массив 2,1.

Ваш Ось 2.

Индекс ло возрастает до тех пор, пока не найдет элемент выше оси 1 или встречает привет. В этом случае она будет соответствовать привет и как вот и привет будет указывать на 1.

На данный момент ваши перегородки функция возвращает и сообщает, что массив был разбит на:

{2},{1}

Но это неверно, потому что 1 - <, чем точка поворота, поэтому он должен был находиться в первом разделе.

Возможно, когда lo встречает привет, вы должны выполнить дополнительный тест, чтобы увидеть, должен ли элемент hi включаться в левый или правый раздел?

источник

2014-02-08 17:42:12

Quicksort не работает в некоторых случаях

ответ

Смежные вопросы