quicksort с использованием arraylist java

Я написал quicksort для arraylist, и, поскольку он стоит, логика кажется звуковой. Проблема, которую я испытываю, заключается в замене элементов. То, что, кажется, происходит, а не заменяет элементы, метод заменяет существующий элемент на тот, который должен быть заменен. пример запускается со списком, например [happy, apples, eat, food], а после сортировки он выходит [счастливый, счастливый, счастливый, еда]. Я уверен, что моя ошибка проста, но я слишком долго смотрел на нее и нуждался в новых глазах. Вот мой код. Заранее спасибо!quicksort с использованием arraylist java

String pivot = list.get(0); // Choose the first element as the pivot 
     int low = first + 1; // Index for forward search 
     int high = last; // Index for backward search 

     while (high > low) 
     { // Search forward from left 
      while (low <= high && list.get(low).compareTo(pivot) <= 0) 
      { 

       low++; 
      } 
     // Search backward from right 
     while (low <= high && list.get(high).compareTo(pivot) > 0) 
     { 
      high--; 
     } 
     // Swap two elements in the list 
     if (high > low) 
     { 

      String temp = list.get(high); 
      list.set(high,list.get(low)); 
      list.set(low,temp); 

     } 
    } 
    while (high > first && list.get(high).compareTo(pivot) <= 0) 
    { 

     high--; 
    } 
    // Swap pivot with list[high] 
    if (list.get(high).compareTo(pivot) < 0) 
    { 
     list.set(first, list.get(high)); 
     list.set(high,pivot); 
     return high; 
    } 
    else 
    { 
     return first; 
    } 
    }

источник

2013-04-30 Justin Ertley

'String pivot = list.get (0); // Выберите первый элемент как свод' <-, который должен быть 'list.get (first)'. –

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

Проблема (после фиксации выбора поворота использовать list.get(first)) является

while (high > first && list.get(high).compareTo(pivot) <= 0)

В этот момент все элементы до (включительно) индекс high (лексикографически) меньше или равно оси. Таким образом,

в то время (высокого> первого & & list.get (высокий) .compareTo (поворот) < = 0) {

high--; 
}

может быть сокращено до high = first.

Это объясняет дублирование первого элемента с выбором поворота на

String pivot = list.get(0);

, потому что в вашем примере элемент с индексом 0 является самым крупным, следовательно

if (list.get(high).compareTo(pivot) < 0) 
{ 
    list.set(first, list.get(high)); 
    list.set(high,pivot); 
    return high; 
}

филиал берется, list.set(first, list.get(high)); ничего не делает, потому что high == first, а затем list.set(high,pivot); копирует стержень в индекс high (== first).

Что вам нужно в проблематичной линии

if (list.get(high).compareTo(pivot) > 0) { 
    --high; 
}

Если после первого цикла разделения элемента по индексу high больше, чем стержень, один перед тем меньше или равна оси. В противном случае high является наибольшим индексом элемента, не большего, чем точка поворота.

источник

2013-04-30 04:14:25

Да, я думаю, что ошибка проста. Попробуйте это

String tempHigh = list.get(high); 
String tempLow = list.get(low); 
list.set(high, tempLow); 
list.set(low, tempHigh);

Потому что в назначении java делается ссылка. В вашем коде вы просто устанавливаете высокое значение как на высокие & низкие позиции. То же самое происходит, когда вы обменивать стержень со списком [высокого]

источник

2013-04-30 03:14:28 JavaKB

Я пробовал этот подход и, к сожалению, он не исправил мою проблему. Моя проблема может быть больше, чем я думал изначально. –

quicksort с использованием arraylist java

ответ

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