java - クイックソートの再帰パラメーター

Question

シンプルなクイックソートアルゴリズム（二重リンクリスト、循環）を実装しようとしています。アルゴリズムはかなりうまく機能しますが、次の操作のために遅すぎます: iEl = getListElement(l); jEl = getListElement(r); 非常に長い入力リストでは、iElandを見つけるために常にリスト全体を調べなければならずjEl、これは非常に遅いです。

解決策は (私が思うに)、これら 2 つの要素をパラメーターとしてパーティション関数に渡すことです。問題は、これに適した要素が見つからないことです。多くの可能性を出力しようとしましたが、正しく適合しません。

コードは次のとおりです。

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);

これら 2 つのパラメーター (iEl、iEl.prev、jEl、jEl.next、...) のいくつかのバリアントを試しましたが、正しく適合するものはないようです。

私が言ったように、関数は機能しますが、非常に遅いです。これら2つのパラメータを渡すことで、関数を高速化することは可能ですか? もしそうなら、どのパラメータを使用する必要がありますか?