Thread: iMalc Super Quick Sort

Any one implement iMalc super quick sort and actually get it to be functionall?

I've got some questions for Malcom, If he would be able to spend a moment to assist?

first let me say, I'm trying to implement the sort using standard C.

Code:

#include <stdio.h>
#include <unistd.h>

typedef struct node {
     struct  node* prev;
     struct  node* next;
      void  *data;
} node_t;

void* node_get(node_t* n) {
       return (n->data);
}

static void
list_partition( node_t *start
              , node_t *split
              , node_t *less_n
              , node_t *grtr_n
              , int  comp(const void *, const void *) ) {

    do {
        node_t *next  = start->next;
        if ( comp(node_get(start), node_get(split))  < 0 ) {
            start->next = less_n;
            less_n = start;
        } else {
            start->next = grtr_n;
            grtr_n =  start ;
        }
        start = next;
    } while (start != NULL );

    return ;
}


static  node_t *
list_SQsortAux( node_t *head
              , int  comp(const void *, const void *) ) {
   node_t *first = head;
   node_t *second = head->next;
   node_t *less = NULL, *center = NULL, *greatereq = NULL ;

 if(second != NULL ) {
      do {     /* find a splitter node - the first whose next item is smaller */
         if (comp(node_get(second), node_get(first)) < 0 ) {  /* Splitter found */
            greatereq = center = first ;
            first->next = NULL;
            less = head;

            /* Partition the list   */
            list_partition(second, center, less, greatereq, comp );
            node_t *const join = list_SQsortAux(less, comp );
            node_t *const last = list_SQsortAux(greatereq, comp );

            /* join the two sorted lists */
            head = less ;
            join->next = greatereq ;

            return last;
         }
         /* Still searching for splitter  */
         first = second;
         second = second->next;
      }while( second != NULL )  ;
   }

   /* Already sorted, No split node found */
   return first ;
}

void
list_SQsort(node_t *ll, int  comp(const void *, const void *) ) {

    if (ll != NULL ) {
       list_SQsortAux(ll, comp );
    }

}

Within the aux function: what is the point of the *prev ? its not used ?

I think there is a flaw in the design.. Consider the following added to a list,
50, 20, 10, 15, 55

The Spitt node is found for 50, this is also becomes the head, first, center and greater.
And the partitioning when it encounters 55 will be incorrect as it will attempt to add it to the same stack as less, except less ptr has now moved.

Any ideas on how to resolve this? Any Improvements for a double linked list, where a sentinel node is used ?

Thanks

Hi bean66

First, here's my implementation for reference:

Code:

//Gives a fake node pointer where only the 'next' member is valid (non-standard)
#define fakePrev(T, H, N) (T*)(((size_t)&H) + ((size_t)H) - ((size_t)&H->N))

template <class TItem>
inline void SuperQuickSort(TItem *&head) {
    if (head != NULL)
        SuperQuickSortAux(head);
}

template <class TItem>
TItem *SuperQuickSortAux(TItem *&head) {
    TItem *prev, *first = head, *second = head->next, *less, *center, *greatereq;
    if (second != NULL) {
        prev = fakePrev(TItem, head, next);
        do { //find a spliter - choose the first item whose next item is smaller
            if (*second < *first) { //Splitter found
                greatereq = center = first;
                prev->next = first->next = NULL;
                less = head;
                //partition the list
                Partition(second, *center, less, greatereq);
                //recursive calls
                TItem *const join = SuperQuickSortAux(less);
                TItem *const last = SuperQuickSortAux(greatereq);
                //join the sorted lists
                head = less;
                join->next = greatereq;
                return last;
            }
            //still looking for splitter
            prev = first;
            first = second;
            second = second->next;
        } while (second != NULL);
    }
    //already sorted (we never found a splitter)
    return first;
}

template <class TItem, class TKey>
void Partition(TItem *headIn1, const TKey &splitter, TItem *&headOut1, TItem *&headOut2) {
	assert(headIn1 != NULL);
	do {
		TItem *next = headIn1->next;
		if (*headIn1 < splitter) {
			headIn1->next = headOut1;
			headOut1 = headIn1;
		} else {
			headIn1->next = headOut2;
			headOut2 = headIn1;
		}
		headIn1 = next;
	} while (headIn1 != NULL);
}

Direct link:
http://homepages.ihug.co.nz/~aurora7...t%20Techniques

The implementation I have of this on my website was actually for a singly-linked list, though I've also got an implementation of it for a doubly-linked list. The above implementation therefore does not require a structure with a prev pointer.
The prev local variable I declare above is used for cutting the list once the splitter has been found.
fakePrev is just a hackish way of avoiding the common code fore dealing with the special case of removing the first node from a list. There becomes no need for special case code for removing from the start of the list e.g.

Code:

if (prev == NULL) head = curr->next; else prev = curr->next;

Oh, I should also mention that the Aux function always returns the tail of the list it sorted. Missing that comment in the code above.

One of the things I've done with the implementation I posted is that the code that performs the search for the splitter actually contains the recursive calls directly within the if-statement in the loop, where it finds the splitter, after which it always returns. I possibly should have made the recursive calls later from outside the loop, but the effect is the same.

In the example you give, 50 will be found as the splitter, so the algorithm's strengths do not become obvious here. The less-than list will start empty and the greater-than-or-equal list will contain just 50.
Ah drat I just noticed I appear to have missed out the partition function from the web page. I've added it above. Will update my site with it shortly
Then the partition continues as per normal ater which the two lists will be as follows:
15, 10, 20
55, 50
A recursive call sorts out each of these lists, and they are then concatenated giving:
10, 15, 20, 50, 55
In this example the list is small enough to not bennefit from the modifications over the quicksort algorithm.

The algorithm does work correctly, as I maintain a number of unit test within the SortingDemo program in the zip file on that page. It is fairly trivial to show how it takes O(n) time for a sorted or reverse sorted list. However, make no mistake, like ordinary quicksort, it has its O(n*n) case. Best case is O(n), average case is O(nlogn), worst case is O(n*n).
It's just that it is about as unlinkely to occur in practice as it is for an array, which is the main advantage. To others: It's best to read the link above for a description of how the algorithm varies from normal quicksort.

The above algoirthm should work as-is in C++ on a list with a 'next' pointer member in the node structure, and a less-than operator defined. For C you need to remove the template (obviously) and replace the call to the less-than operator, with a call to a compare function.
Actually I've been tempted to implement this particular algorithm in other languages such as prolog

I've updated my linked-list sorting page with an example of sorting using this algorithm. Hopefully it should clarify things immensely.

Hmm, the doubly-linked list implementation I have is actually for a ring-list (last node points back to the first). I'll post it anyway:

Code:

template <class TItem, class TKey>
void Partition(TItem *headIn1, const TKey &splitter, TItem *&headOut1, TItem *&headOut2) {
	while (headIn1 != NULL) {
		TItem *temp = Pop(headIn1);
		if (*temp < splitter)
			Push(headOut1, temp);
		else
			Push(headOut2, temp);					
	}
}
template <class TItem>
void SuperQuickSort(TItem *&head) {
	if ((head != NULL) && (head->next != head)) { //Must be at least 2 items
		TItem *first = head, *second = head->next, *less, *center, *greatereq, *curr;
		do { //find a spliter - choose the first item whose next item is smaller
			if (*second < *first) { //Splitter found
				less = greatereq = NULL;
				if (first != head) {
					//use passed items as less-than list.
					//this actually splits the list in two!
					less = SplitJoinNonEmptyLists(head, first);
					head = first;
				}
				curr = head;
				center->prev = center->next = center = Pop(curr);
				//partition the list
				Partition(curr, *center, less, greatereq);
				//recursive calls
				SuperQuickSort(less);
				SuperQuickSort(greatereq);
				//join the sorted lists
				head = SplitJoinNonEmptyLists(less, ConcatLists(center, greatereq));
				break;
			}
			//still looking for splitter
			first = second;
			second = second->next;
		} while (second != head);
	}
}

template <class TItem>
TItem *SplitJoinNonEmptyLists(TItem *head1, TItem *head2) {
	assert(head1 != NULL && head2 != NULL);
	TItem *prev1 = head1->prev;
	TItem *prev2 = head2->prev;
	prev1->next = head2;
	head1->prev = prev2;
	prev2->next = head1;
	head2->prev = prev1;
	return head1;
}

template <class TItem>
TItem *ConcatLists(TItem *head1, TItem *head2) {
	//if either list is NULL return the other list
	if (head1 == NULL) return head2;
	if (head2 == NULL) return head1;
	return SplitJoinNonEmptyLists(head1, head2);
}

As you can see I did things slightly diferently with this version when I wrote it long ago. I still need to go back and tidy it up to put center in the greatereq list like the singly-linked list version. Will do this shortly, I just don't have time to test it right now.

Other things you need to take care of to use this:
Doubly-linked list Push and Pop functions - should be easy.

Yeah I always forget about C not having references. Gets me every time. Sorry bout that.

Yup, prev->next is really the head when we want to cut the list off before the first node. To not use that sneaky trick, you'd just need to check for prev still being NULL, and use head instead of prev->next. However you can't easily use the trick for doubly-linked lists, because only the 'next' member of prev is valid to use, unless you are rather careful and clever in your doubly-linked list class definition.

Whether it treats a doubly-linked list as a singly-linked one (fixing afterwards), or it treats it as an actual doubly-linked list only really differs in terms of what Push and Pop do. The Push and Pop I have maintain the prev pointers as well.

Nice to see some timings. I usually just check the comparison counts etc.
I presume that the smaller numbers are the list lengths, and the larger ones are the number of iterations?
The case you describe is pretty much the ideal scenario for using this algorithm, so it should work well.
If the lists were a lot longer, then bucketsort would be better for the random case, but the best-case of the algorithm discussed here is really as fast as determining if a list is sorted (no nodes get modified at all), for which there isn't really anything that could be any faster.