Рекурсивные параметры для быстрой сортировки

Question

Я пытаюсь реализовать простой алгоритм быстрой сортировки (двусвязный список, циклический). Алгоритм работает довольно хорошо, но он слишком медленный из-за следующей операции: iEl = getListElement(l);jEl = getListElement(r);В очень длинном списке ввода я должен постоянно просматривать весь список, чтобы найти iEl а также jEl, который является ультра-медленным.

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

Вот код:

public void partition(int l, int r, ListElement lEl, ListElement rEl) {
    if (r > l) {
        ListElement p, iEl, jEl;
        int i, j, x;
        i = l;
        j = r;

        // These two lines are very slow with long input-lists
        // If I had the two correct parameters lEL and rEl, this would be much faster
        iEl = getListElement(l);
        jEl = getListElement(r);
        // getListElement walks through x-elements (l and r) of the list and then returns the element on that position 

        // If I had the correct Elements rEl and lEl, I could directly use these Elements, instead of going all the way through the list. Something like this:
        // iEl = lEl;
        // jEl = rEl;


        x = (int) Math.floor((j + i) / 2);
        p = getListElement(x);


        while (i <= j) {

            while (iEl.getKey() < p.getKey() && i < r) {
                i++;
                iEl = iEl.next;
            }

            while (jEl.getKey() > p.getKey() && j > l) {
                j--;
                jEl = jEl.prev;
            }

            if (i <= j) {
                if (iEl != jEl) {
                    swap(iEl, jEl);
                }
                ++i;
                --j;
                break;
            }
        }

        if (l < j) {
            // Here I need the two correct parameters
            partition(l, j, ???, ???);
        }

        if (i < r) {
            // Here I need the two correct parameters
            partition(l, j, ???, ???);
        }
    }
}

Функция начинается с: partition(0, numOfElements - 1, list.first, list.first.prev);

Я пробовал пару вариантов для этих двух параметров (iEl, iEl.prev, jEl, jEl.next, ...), но, похоже, ни один из них не подходит правильно.

Как я уже сказал, функция работает, но очень медленно. Возможно ли вообще ускорить функцию, передав эти два параметра? Если да, то какие параметры мне нужно использовать?

Answer 1

Я не понимаю, как "элементы как параметры" могут сильно помочь. Проблема в том, что нужно пройтись по списку, чтобы получить элементы, не так ли?

Почему бы не сделать массив из вашего списка на время сортировки? Пройдите по списку один раз, поместите ссылку на каждый элемент в массиве, а затем сделайте то, что я считаю более нормальной быстрой сортировкой, разбивающей массив и перемещающей туда ваши элементы. Конечно, когда вы перемещаете элемент в массиве, вам также нужно будет переставить его следующий / предыдущий указатели, чтобы ваш связанный список не был поврежден, но вы все равно должны это сделать. Это избавит вас от прогулки по списку, чтобы получить элементы. Просто удалите массив (или ArrayList), когда закончите.