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.

iMalc:
Thanks for the response.
Would you post your double link list implementation ?

I agree that the algorithm does work and works as you describe, I'm just having a bit of a struggle getting my implementation in C functional. I guess the fakePrev is a little odd to me. Where is the prev used ? I dont see where it's accessed ?

One other thing I'm missing. Is the partition designed to build to seperate lists or to re-locate into 2 new lists (less, greatereq) ??? I'm confused since the less/greatereq are assigned to existing list elelments.

In the example i gave: 50, 20, 10, 15, 55 (and in my code version)
After the split is picked at 50. The less list is also set at node 50 greatereq at 20 resulting in an interlinked set of pointers after partition returned
Less: 15->10->20->50
great: 55->20

Should the routine set the less than to NULL? and greater to 50?

Code:

                prev->next = first->next = NULL;
                less = head;

I think that is what I missed.. the prev->next is really the head when the split is the first node?

I can't use that technique in my version since the fakePrev will not work due to my node structure.

For my purposes, I'll often have a mostly sorted input or a reversed input. Usuall of short amounts of data. For those cases I can hand the sorting off to an insertion sort. But there are occasional inputs of a large amount of data.

Thanks,
Ken

I just saw your updated we page. That clarifies things...

This is a very unique sorting routine to say the least. I've not seen that techniqe used elsewhere either.

Thanks again.
Ken

I've managed to get this working, a few things, different in C.

the declarations *&.. needed to be changed to **,

Code:

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

    do {
        node_t *next  = start->next;

        if ( comp(lnode_get(start), lnode_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( list_t  *list
              , node_t **head
              , int32_t  comp(const void *, const void *) ) {
   assert (head != NULL );
   node_t *prev  = NULL;
   node_t *first = *head;
   node_t *second = (*head)->next;
   node_t *center = NULL;
   node_t *less=NULL, *greatereq =NULL;


   if(second != NULL ) {
      prev =  fakePrev (lnode_t, (*head), next );
      /* find a splitter node - the first whose next item is smaller   */
      do {
         if (comp(lnode_get(second), lnode_get(first)) < 0 ) {
            /* Splitter found, first  */
            /*
            ** 1. Set center and greatereq to splitter
            ** 2. disconnect the spliter from list
            ** 3. disconnect the prior list from splitter
            ** 4. less than is head, can be null if splitter == head
            ** 5. remaining list is second
            */
            greatereq = center = first ;  /* 1 */
            first->next = NULL;              /* 2 */
            prev->next = NULL;            /* 3 */
            less = *head ;

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

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

            return last;  /* Return the tail end of the list */
         }

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

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

Thanks for your help and detailed explenation. Once I got my head around the fact that partitioning and SortAux list pointers were actually ** that made life a lot easier!

Now to implement using doubly linked lists.

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.

iMalc,

Thanks posting the double linked code... Yes, reference pointer logic does get a bit tricky, usually freaks out new coders.

I hacked my implementation to set the last nodes next to null and the first nodes prev to null. Then simply passed in the first node.
When finished, traversed the list setting the curr->prev = prev. And a few other pointer manipulations and voila...

I think that maybe that method (treating a doubly linked as a simple single ) is quicker than maintaining doubly linked lists for the sort. It does have the disadvantage of being O(n * log n) + c*n.

My list implementation uses a sentinel node that is never NULL. If the list is empty its prev/next point back onto itself. This makes the code super easy to insert/delete a new node entry. Traversal is also equally easy, just stop at the sentinel node. Push/pop are trivial as are enque/deque.

Here are some timing numbers the for various sorts against a doubly linked dist.

Sort inner loop outer loop data Optimized
InsertSort 5 10000000 Random 2.73
InsertSort 5 10000000 Sorted 2.24
InsertSort 5 10000000 reversed 1.81

Sqsort 5 10000000 Random 3.14
Sqsort 5 10000000 Sorted 1.28
Sqsort 5 10000000 reversed 1.62

InsertSort 10 5000000 Random 2.6
InsertSort 10 5000000 Sorted 2.67
InsertSort 10 5000000 reversed 1.76

Sqsort 10 5000000 Random 2.71
Sqsort 10 5000000 Sorted 1.3
Sqsort 10 5000000 reversed 1.89

MergeSort 10 5000000 Random 3.6
MergeSort 10 5000000 Sorted 3.6
MergeSort 10 5000000 reversed 5.96

InsertSort 100 500000 Random 6.97
InsertSort 100 500000 Sorted 20.66
InsertSort 100 500000 reversed 1.76

Sqsort 100 500000 Random 4.94
Sqsort 100 500000 Sorted 1.3
Sqsort 100 500000 reversed 1.57

MergeSort 100 500000 Random 6.8
MergeSort 100 500000 Sorted 4.39
MergeSort 100 500000 reversed 4.8


Interesting to note that it beats insertion sort for short ordered lists, just what I was looking to do! In general my lists will be only 1 or 2 nodes. But occasionaly more and ordering will typically be ordered(70&#37, reversed(20%) or mixed(10%).

Thanks again for your assistance in understanding the algorithm.

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.

iMalc,

Yes the smaller numbers are for an inner loop, ie the number of nodes inserted into the list. The outer loop is an iteration over the inner.
OuterLoop
Inner loop
add nodes to list.
end loop

Sort
Free Nodes
End Loop

I'll probably build the In place version as well instead of a post processing one just to compare the timings.

I'm surprised that the merge sort was so slow. I think it was due to the List Transfer and merge processes that were written.

Thanks again.
Ken