Улучшение сортировки Bubble за счет уведомления о месте последнего обмена - PullRequest
Новая
       11

Улучшение сортировки Bubble за счет уведомления о месте последнего обмена

0 голосов
/ 09 июня 2018

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

public static <T extends Comparable<? super T>> void bubbleSort(T[] a) {
    for (int i = a.length - 1; i > 0; --i) {
        for (int j = 0; j < i; ++j) {
            numComp++;
            if (a[j].compareTo(a[j + 1]) > 0) {
                numAsgn += 3;
                T temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
            }
        }
        if (tracing) {
            System.out.println("one more bubbled up: "
                    + Arrays.toString(a));
        }
    }
}

Это моя попытка. 

 public static <T extends Comparable<? super T>> void bubbleSort(T[] a) {
    boolean swap = false;
    for (int i = a.length - 1; i > 0;) {
        for (int j = 0; j < i; ++j) {
            numComp++;
            if (a[j].compareTo(a[j + 1]) > 0) {
                numAsgn += 3;
                T temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
                swap = true;
            }
            if (swap) {
                i = j;
            } else {
                i = 0;
            }
        }
        if (tracing) {
            System.out.println("one more bubbled up: "
                    + Arrays.toString(a));
        }
    }
}

Код, который печатает мойвывод выглядит следующим образом: 

 bubbleSort(check);
    System.out.printf("%1$-19s %2$10d %3$19d %4$19d", "Bubble", numComp, numAsgn, numComp + numAsgn);
    System.out.println();
    resetCounts(); //resets numComp and numAsgn to 0

Пример ввода: [2, 5, 5, 3, 1, 3, 4, 4, 3, 4]

Выход:

enter image description here

1 Ответ

0 голосов
/ 09 июня 2018

Возможно, что-то вроде этого: 

public static <T extends Comparable<? super T>> void bubbleSort(T[] a) {
    int lastSwap = a.length - 1, i;
    for (i = lastSwap; i > 0;) {
        for (int j = 0; j < i; ++j) {
            numComp++;
            if (a[j].compareTo(a[j + 1]) > 0) {
                numAsgn += 3;
                T temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
                lastSwap = j;
            }
        }
        if(i == lastSwap) {
            //sorted
            break;
        }
        i = lastSwap;
        if (tracing) {
            System.out.println("one more bubbled up: "
                    + Arrays.toString(a));
        }
    }
}

Это должно дать вам некоторое улучшение, но наихудший случай останется таким же, как и ожидалось.

...