Partition Sort for single linked list to double linked list

[nowy20180820]

I have code for partition sort for single linked list
It sorts next pointers correctly but i want that this function be able to sort
double linked list also
Sorting function should also set previous pointers
but where and how

  typedef struct node node;
 
struct node {
	int data;
	node * next;
        node * prev;
};

node *getTail(node *first)
{
	node *x;
	if(first == NULL) {
		x = NULL;
	} else {
		x = first;
		while(x->next != NULL) {
			x = x->next;
		}
	}
	return x;
}
 
void tailins(node *r,node **first,node **last)
{
	if((*first) == NULL)
		(*first) = r;
	else
		(*last)->next = r;
	(*last) = r;
}
 
node *sort(node *r,node **last)
{
	node *result;
	node *lowf,*lowl,*midf,*midl,*highf,*highl;
	if(r == NULL) {
		(*last) = NULL;
		result =  r;
	} else {
		lowf = NULL;
		midf = NULL;
		highf = NULL;
 
		tailins(r,&midf,&midl);
		r = r->next;
		while(r != NULL) {
			if(r->data < midf->data)
				tailins(r,&lowf,&lowl);
			else if(r->data == midf->data)
				tailins(r,&midf,&midl);
			else
				tailins(r,&highf,&highl);
			r = r->next;
		}
		if(lowf != NULL) {
			lowl->next = NULL;
			result = sort(lowf,last);
			(*last)->next = midf;
		} else
			result = midf;
		if(highf != NULL)
			highl->next = NULL;
		midl->next = sort(highf,last);
		if((*last)==NULL)
			(*last) = midl;
	}
	return result;
}

I know how to set prev pointers outside the sorting function
but in my opinion it would be better if setting prev pointers was written
inside sorting function

[tpb]

Since this is a C++ site you should specifically mention that your code is C (you are typedefing struct node to node and using NULL, and I assume you use malloc elsewhere in your code).

Your code looks a little strange to me but maybe I'm just not use to sorts on lists. It would be better if you posted a full runnable program that makes a list, prints it, sorts it, and prints it again.

One way to keep your pointers correct is to only swap the data and leave all the pointers alone, but maybe that's not possible in your case.

[Duthomhas]

C is a subset of C++, so the code is acceptable either way.

The two primary functions when moving nodes is extracting (or "unlinking") a node from a list, and inserting a node into a list.

These are the only two operations that will be significantly different between singly-linked and doubly-linked sort functions.

That said, it is usually just a good idea to write different sort functions for each list type.

Hope this helps.

[tpb]

I didn't mean to imply that the code wasn't acceptable, but if you don't specify C then people will usually post a C++ solution.

And moving the data is usually better than fiddling with the links, although some applications don't want the addresses of the data changed, so it depends.

[nowy20180820]

Code that can be compiled to executable can be found on ideone
https://ideone.com/uT1WvV
It works only for singly linked list
The goal of this task is to set previous poiners in that way
the function will be able to sort doubly linked list
I tried to do this on my own but i failed

I changed insert function

void tailins(node *r,node **first,node **last)
{
	if((*first) == NULL)
		(*first) = r;
	else
        {
		(*last)->next = r;
                r->prev = (*last)
        }
	(*last) = r;
}

and tried to insert instruction

    if(x->next != NULL)
        x->next->prev = x;

in different places in the code
but it does not work correctly

Duthomhas it looks like you dont want help me
(and others when they will have the same problem)
The only one thing we should do is to set prev pointers correctly
so why rewrite code once again

"And moving the data is usually better..."

Not true , it is visible especially if we have many fields in the data part of the node
If we allow moving data you will be able to copy and paste geeks solution

[icy1]

why the inserts, if that's what they really are? Shouldn't you just be swapping nodes (or in this case, simplest to just swap the integers contained in node.data) ?

Your prev and next links could remain unchanged...

[tpb]

I didn't realize you were a dick. Sorry for trying to help. All you had to say is "I want to adjust the links". I never said that you couldn't do that, just that moving the data is simpler.

If we allow moving data you will be able to copy and paste geeks solution

I have no idea what a "geeks" solution is! Am I a "geek"? Is that what you're saying? Geez!

[dhayden]

C is a subset of C++

Only sort of. There are things you can do in C that won't compile in C++. As I recall, a very common difference is that C lets you automatically convert void* to another type of pointer. In C++, the cast must be explicit.

moving the data is usually better than fiddling with the links

In this case, where the data is just an int, that's true, but in general I think it's better to twiddle the links. The data could be huge.

i want that this function be able to sort double linked list also

Sort based on the forward links only. When you're done, make one pass through the list to set the reverse links. In other words, something like:

node *newsort(node *head, node **tail)
{
    head = sort (head, tail);
    // code to fix the reverse links
    return head;
}

You can do this rather than just fix up tailins() because tailins() is such a specialized part of sort(). In other words, it seems unlikely that you'd use this implementation of tailins() for anything else. It's specialized because it leaves r->next unchanged and sort() relies on that behavior.

[nowy20180820]

I think i did it on my own
I tested it on random linked lists and it works
Question which might help
How to concatenate two doubly linked lists
whith assumption that each list has pointers to head and tail node
dhayden yes I did it but i want to fix these links inside sort function
without writing another one
Your idea could be acceptable but i had done it before i wrote this thread
but in main function
I could not set prev pointers inside sort function
dhayden i like your answer

[dhayden]

Untested, but I think this might work. Note that I'm passing head1 and tail1 by reference

// Concatenate two lists. Head1 and tail1 point to the head & tail of
// the first list. Head2/tail2 point to the head/tail of the second.
// Update head1 and tail1 to point to the head & tail of the
// concatenated list
void concat(node * &head1, node * &tail1, node *head2, node *tail2)
{
    if (tail1) {
        tail1->next = head2;
    } else {
        head1 = head2;
    }
    if (head2) {
        head2->prev = tail1;
        tail1 = tail2;
    }
}

[nowy20180820]

Lets analyze this algorithm

First we choose pivot
(we have fastest access to these nodes for which we remember the pointer
usually it is head or tail)
Then we insert nodes of our list to three sublists
First sublist contains nodes with keys less than pivot key (let call it L)
Second sublist contains nodes with keys equal to the pivot key (let call it E)
Third sublist contains nodes with keys grater than pivot key (let call it G)
We sort recursively sublists L and G
Finally we concatenate sublist L and E and G

Worst case time complexity is O(n^2)
and worst case occurs more frequently then for arrays

[dhayden]

and worst case occurs more frequently then for arrays

How so?

[nowy20180820]

node *getTail(node *head)
{
    node *tail = head;
    while(tail != NULL && tail->next != NULL)
        tail = tail->next;
    return tail;
}

void tailins(node *rec,node **first,node **last)
{
    if((*first)==NULL)
    {
        (*first) = rec;
    }
    else
    {
        (*last)->next = rec;
        rec->prev = (*last);
    }
    (*last) = rec;
}

node *quickSort(node *r,node **last)
{
    node *lowf,*lowl,*midf,*midl,*highf,*highl;
    node *result;

    if(r == NULL)
    {
        (*last) = NULL;
        result = r;
    }
    else
    {
        lowf = NULL;
        midf = NULL;
        highf = NULL;
        tailins(r,&midf,&midl);
        r = r->next;
        while(r != NULL)
        {
            if(r->key < midf->key)
                tailins(r,&lowf,&lowl);
            else if(r->key == midf->key)
                tailins(r,&midf,&midl);
            else
                tailins(r,&highf,&highl);
            r = r->next;
        }
        if(lowf != NULL)
        {
            lowl->next = NULL;
            result = quickSort(lowf,last);
            if(result->next != NULL)
                result->next->prev = result;
	    (*last)->next = midf;
	    if(midf != NULL)
	       midf->prev = (*last);
	}
	else
	{
	    result = midf;
	    if(result->next != NULL)
		result->next->prev = result;
	}
	if(highf != NULL)
	    highl->next = NULL;
	midl->next = quickSort(highf,last);
	if(midl->next != NULL)
	    midl->next->prev = midl;
	if((*last) == NULL)
	    (*last) = midl;
    }
    if(result != NULL)
	result->prev = NULL;
    return result;
}

I set prev pointers inside sorting function
and it seems to work correctly

[dhayden]

To test it, write a function to print the list using the next pointer, and print it again using the prev pointer. Call the function before and after you sort the list. Then give it several different lists to sort: lists with 0, 1, and 2 elements, a list of random elements, a list that is already sorted, and a list that is already sorted in reverse order.