Пузырьковая сортировка по книге Р. Лафоре

Есть реализация пузырьковой сортировки по книге Лафоре "Структуры данных и алгоритмы JAVA":

class ArrayBub {
private long[] a;
private int nElems;
public ArrayBub(int max) {
    a = new long[max];
    nElems = 0;
}
public void insert(long value) {
    a[nElems] = value;
    nElems++;
}
public void display() {
    for(int j=0; j<nElems; j++)
        System.out.print(a[j] + " ");
    System.out.println("");
}
public void bubbleSort() {
    int out, in;

    for(out=nElems-1; out>1; out--)
        for(in=0; in<out; in++)
            if( a[in] > a[in+1] )
                swap(in, in+1);
}
private void swap(int one, int two) {
    long temp = a[one];
    a[one] = a[two];
    a[two] = temp;
}}

class BubbleSortApp {
public static void main(String[] args) {
    int maxSize = 100;
    ArrayBub arr;
    arr = new ArrayBub(maxSize);

    arr.insert(77);
    arr.insert(99);
    arr.insert(44);
    arr.insert(55);
    arr.insert(22);
    arr.insert(88);
    arr.insert(11);
    arr.insert(00);
    arr.insert(66);
    arr.insert(33);

    arr.display();
    arr.bubbleSort();
    arr.display();
}}

но она не сортирует массив со значениями - [3, 2, 1] - ответ: [2, 3, 1].

Помогите пожалуйста разобраться в чем подвох?


Ответы (1 шт):

Автор решения: Roman C

Для понимания алгоритма можно почитать, что такое Пузырьковая сортировка. Правда там обход массива производится в прямом порядке для каждого элемента, но это не столь важно.

При работе с массивами надо смотреть на значения переменной индекса, правильность границ, инвариантов функции (assert), и т.д., потому что при неверных значениях переменных возникает неверное вычисление.

Как у вас, например сортируется часть массива, а оставшаяся часть не сортируется, т.е. массив остаётся неотсортированным, потому что он отсортирован не полностью.

→ Ссылка