# How to sort doubly-linked list? BFP

Discussion in 'C' started by duffer, Sep 1, 2007.

1. ### dufferNew Member

Joined:
Sep 1, 2007
Messages:
3
Likes Received:
0
Trophy Points:
0
My first post! Congratulations
BFP = Big F**king Problem

First...I'm sorry if my English is wrong!(I'm from Bulgaria)
Second: Please don't delete my Post! I've read at least 20 sites with google search and in a lot of forums to understand and repair my problem! So just please help.
Third: Before one week, I know only few about Programming in C, some arrays, basic things, the loops, but my source is over 1200 lines, so help me to finish it, please.

I'm trying to sort a doubly-linked list without any success for 3 days! Please help me, I know, that you can.
So...
The idea is to sort the first two elements, than to compare the next two and something like that...Yet I'm very very CONFUSED.

this is my struct for an element of the doubly-linked list:

Code:
```struct element
{
struct worker a;
struct element *next;
struct element *previous;
};
typedef struct element element;
element *head, *tail;```
In struct worker, I must sort the workers in a firm by the length of service (in increasing) in that firm, I know the date of the appoin for every worker I added in the list.
For Example:
I must sort that dates:
11.11.2003
11.12.2003
11.11.2006
11.11.2004
11.11.2005
11.11.2007
like that: 11.11.2007>11.11.2006>11.11.2005>11.11.2004>11.12>2003>11.11.2003
Important: We don't know the number of the workers, and when we sort the list, we can add more workers, and than we must sort with the new again for example.

in that code, I add workers to the list:
Code:
```void createElement(struct worker a)
{
element *newElement;

if (head == NULL)
{
newElement=(struct element *)malloc (sizeof(struct element));
newElement->a=a; //tuk vlizat proverenite danni i ukazatelq gi izvlicha
head=newElement;
newElement->previous = NULL;
}
else
{
newElement = (struct element *)malloc (sizeof(struct element));
newElement->a=a;
tail->next=newElement;
newElement->previous=tail;
}
tail = newElement;
newElement->next=NULL;
}```
and the dates of elements (workers) are like the example before...in that row.

FOR SORT:
I tried lot of ways, but nothing work!!!

like that for example:

Code:
```void sortWorkers()
{
element *findElement;
int f=1;

findElement=head;
while(findElement!=NULL)
{
while(f!=0)
{
if(strcmp(head->a.date, findElement->next->a.date)>0)
{
head=findElement;
head->previous->next=findElement->next;
head->next->previous=findElement->previous;
findElement=findElement->next;
f=0;
}
/*	else if(strcmp(findElement->a.date, findElement->next->a.date)<0)
{
head=findElement;
head->previous->next=findElement->next;
head->next->previous=findElement->previous;
findElement=findElement->next;
f=0;
} */
else if(strcmp(head->a.date, findElement->next->a.date)<=0)
{
f=0;
}
}findElement=findElement->next;
f=1;
}
}```
or:
Code:
```void sortWorkers()
{
element *find;
element *temp;

find=head;
do
{
if(strcmp(find->a.date, find->next->a.date)<0)
{
temp=find->next->previous;
temp->next->next->previous=find->next->previous;
temp->next=find->next->previous;
temp->next->previous=find->previous;
temp->next->next=find->next->next;
find=temp;
}
else if(strcmp(find->a.date, find->next->a.date)>=0)
{
find=find->next;
}
}while(find->next!=NULL);
}```
or other ways, that I haven't yet, but they don't work.

THANKS A LOT!

Last edited by a moderator: Sep 1, 2007
2. ### DaWeiNew Member

Joined:
Dec 6, 2006
Messages:
835
Likes Received:
5
Trophy Points:
0
Occupation:
Semi-retired EE
Location:
Texan now in Central NY
Home Page:
http://www.daweidesigns.com
Sorry, that pale colored text is too hard to read. Further, you haven't put the code inside tags to preserve it's indentation. Let me recommend you read the "BEFORE you make a query" thread. You'll find a link in the upper right corner of this page.

Don't know why you would want to make it difficult for potential helpers, but there you have it.

3. ### dufferNew Member

Joined:
Sep 1, 2007
Messages:
3
Likes Received:
0
Trophy Points:
0
Sorry, but for now, you can just select the text with the mouse. I thought that this colors are the formated C-code...like in other posts :| Sorry again!

4. ### shabbirAdministratorStaff Member

Joined:
Jul 12, 2004
Messages:
15,358
Likes Received:
383
Trophy Points:
83
You don't need to be doing that manually and in the code block you can specify the language of the code and if its a known language it will be formatted automatically and right now I have done that for you.

5. ### dufferNew Member

Joined:
Sep 1, 2007
Messages:
3
Likes Received:
0
Trophy Points:
0
Thanks, for next I would know that.
P.S. Now I test to have two temp elements for each element that will be swapped, but something don't work.
Can anyone help, just to say, can I do that, that I want, is it possible as a logical idea?
Thanks

6. ### DaWeiNew Member

Joined:
Dec 6, 2006
Messages:
835
Likes Received:
5
Trophy Points:
0
Occupation:
Semi-retired EE
Location:
Texan now in Central NY
Home Page:
http://www.daweidesigns.com
swap (a, b) => move a to temp, move b to a, move temp to b.

7. ### shabbirAdministratorStaff Member

Joined:
Jul 12, 2004
Messages:
15,358
Likes Received:
383
Trophy Points:
83
I have not gone through the complete thread but just from the title it seems Sort Linked List article would interest you.

8. ### DaWeiNew Member

Joined:
Dec 6, 2006
Messages:
835
Likes Received:
5
Trophy Points:
0
Occupation:
Semi-retired EE
Location:
Texan now in Central NY
Home Page:
http://www.daweidesigns.com
Let me point out that there are at least 3 ways to sort a linked list. Suppose that your inspection of the variables used in the sort criteria indicate that you should swap elements 2 and 7.

You can exchange all the data for elements 2 and 7, except for the links.

You can exchange the links for elements 2 and 7.

You can establish an array of pointers to the elements and merely swap the pointers in the array.