Recursive parameters for quicksort

Question

I'm trying to implement a simple Quicksort Algorithm (Doubly Linked List, circular). The Algorithm works pretty well, but it's much too slow, because of the following operation: iEl = getListElement(l); jEl = getListElement(r); On very long input-list I have to constantly go through the whole list, to find iEl and jEl, which is ultra-slow.

The solution would be (I think), to pass those two Elements as Parameters to the partition Function. Problem is, I can't find the correct Elements for this. I've tried to output a lot of possibilities, but they just don't fit correctly.

Here's the code:

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, ???, ???);
        }
    }
}

The function starts with: partition(0, numOfElements - 1, list.first, list.first.prev);

I've tried a couple of variants for these two parameters (iEl, iEl.prev, jEl, jEl.next, ...), but none seem to fit correctly.

As I said, the function works, but its very slow. Is this even possible, to speed up the function, by passing these two parameters? If so, what parameters would I have to use?

Answer 1

I don't see how "elements as parameters" is going to help much. The problem is having to walk the list to get elements, isn't it?

Why not make an array out of your list for the duration of the sort? Walk the list once, put a reference to each element in an array, and then do what I think of as a more normal quicksort partitioning the array and moving your elements there. Of course, when you move an element in the array, you will also have to rearrange its next/previous pointers so that your linked list is intact when you're done, but you have to do that anyway. This will save you walking the list to get elements. Just discard the array (or ArrayList) when done.