сократить цикл сортировки пузырьков

Question

Я изменил свою пузырьковую сортировку от реализации приложения, пересекающего весь список во время каждого шага сортировки.

В этом нет необходимости, поскольку после первого обхода самый маленький элемент будет в конце списка.и после второго обхода второй наименьший элемент будет в правильном положении (2-й последний) и так далее.Я немного не уверен, что именно нужно изменить.

Мне нужно изменить сортировку пузырьков, чтобы она не выполняла ненужных сравнений.

   private void bubbleSort() {
      int currentCount = 0;
      showStatus("Sorting ...");
      boolean swap = true;
      while (swap) {
         swap = false;
         for (int i = 0; i < items.length - 1; i++) {
            if (greaterThan(items[i], items[i + 1])) {
               swapItems(items[i], items[i + 1]);
               swap = true;
               currentCount++;
            }
         } // for
      } // while
      showStatus("Sort complete, number of swaps = " + currentCount);
   } // bubbleSort   private void bubbleSort() {

Answer 1

Прежде всего, в конце первой итерации цикла for самый большой элемент будет находиться в конце массива, а не наименьшим.

Если вы хотите изменитьВаш код для сохранения ненужного сравнения вы можете проверить последнее сравнение и использовать в качестве конца следующего цикла for.

Рассмотрим следующий код: (я надеюсь java разрешить, пока (int) - я не java эксперт ...)

integer swap = items.length - 1;
while (swap) {
    swap = 0;
    integer lastSwap = swap ;
    for (int i = 0; i < lastSwap ; i++) {
        if (greaterThan(items[i], items[i + 1])) {
           swapItems(items[i], items[i + 1]);
           swap = i;
           currentCount++;
        }
     } // for
  } // while

Answer 2

Пузырьковая сортировка будет выполнять ненужные сравнения, поэтому вы не используете ее в производстве для любого набора данных любого приемлемого размера.Что касается вашего кода в частности.Простой взгляд на эталонную реализацию для Rosettacode (потому что я не хочу на самом деле писать это снова, вы делаете это только в школе), показывает, что он делает то же самое количество сравнений.Если вам нужен действительно хороший алгоритм сортировки для достаточно большого N, попробуйте сортировку слиянием.

Ссылка

public static <E extends Comparable<? super E>> void bubbleSort(E[] comparable) {
    boolean changed = false;
    do {
        changed = false;
        for (int a = 0; a < comparable.length - 1; a++) {
            if (comparable[a].compareTo(comparable[a + 1]) > 0) {
                E tmp = comparable[a];
                comparable[a] = comparable[a + 1];
                comparable[a + 1] = tmp;
                changed = true;
            }
        }
    } while (changed);
}