Hello again,
I do some tests and i don't undersrand the results, i used the merge sort algorithm described here :
Mergesort For Linked Lists
And compared it to an insertion sort algorithm :
merge sort algorithm :
Code:
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#define FALSE 0
#define TRUE 1
struct element {
struct element *next, *prev;
int i;
};
int cmp(struct element *a, struct element *b) {
return a->i - b->i;
}
struct element* listsort(struct element *list) {
struct element *p, *q, *e, *tail, *oldhead;
int insize, nmerges, psize, qsize, i;
/*
* Silly special case: if `list' was passed in as NULL, return
* NULL immediately.
*/
if (!list)
return NULL;
insize = 1;
while (1) {
p = list;
oldhead = list; /* only used for circular linkage */
list = NULL;
tail = NULL;
nmerges = 0; /* count number of merges we do in this pass */
while (p) {
nmerges++; /* there exists a merge to be done */
/* step `insize' places along from p */
q = p;
psize = 0;
for (i = 0; i < insize; i++) {
psize++;
q = q->next;
if (!q) break;
}
/* if q hasn't fallen off end, we have two lists to merge */
qsize = insize;
/* now we have two lists; merge them */
while (psize > 0 || (qsize > 0 && q)) {
if (psize == 0) {
/* p is empty; e must come from q. */
e = q; q = q->next; qsize--;
} else if (qsize == 0 || !q) {
/* q is empty; e must come from p. */
e = p; p = p->next; psize--;
} else if (cmp(p,q) <= 0) {
/* First element of p is lower (or same);
* e must come from p. */
e = p; p = p->next; psize--;
} else {
/* First element of q is lower; e must come from q. */
e = q; q = q->next; qsize--;
}
/* add the next element to the merged list */
if (tail) {
tail->next = e;
} else {
list = e;
}
tail = e;
}
/* now p has stepped `insize' places along, and q has too */
p = q;
}
tail->next = NULL;
/* If we have done only one merge, we're finished. */
if (nmerges <= 1) /* allow for nmerges==0, the empty list case */
return list;
/* Otherwise repeat, merging lists twice the size */
insize *= 2;
}
}
struct element *addnode(int number, struct element *next)
{
struct element *tnode;
tnode = (struct element*)malloc(sizeof(struct element));
if(tnode != NULL) {
tnode->i = number;
tnode->next = next;
}
return tnode;
}
int main(void) {
struct element *head;
struct element *current;
struct element *next;
int j;
struct timeval tbegin,tend;
double texec=0.;
// Start timer
gettimeofday(&tbegin,NULL);
head = NULL;
/* insert some numbers into the linked list */
for (j = 1000001; j >= 0; j--)
head = addnode(j, head);
head = listsort(head);
/* print the list */
printf(" before after\n"), j = 1000001;
for(current = head; current != NULL; current = current->next)
printf("%4d\t%4d\n", j--, current->i);
/* free the list */
for(current = head; current != NULL; current = next)
next = current->next, free(current);
// End timer
gettimeofday(&tend,NULL);
// Compute execution time
texec=((double)(1000*(tend.tv_sec-tbegin.tv_sec)+((tend.tv_usec-tbegin.tv_usec)/1000)))/1000.;
printf("Elapsed time = %f\n", texec);
/* done... */
return 0;
}
The insertion sort code :
Code:
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
struct node {
int number;
struct node *next;
struct node *prev;
};
struct node *head = NULL;
/* insert a node directly at the right place in the linked list */
void insert_node(int value);
int main(void) {
struct node *current = NULL;
struct node *next = NULL;
int i = 0;
struct timeval tbegin,tend;
double texec=0.;
// Start timer
gettimeofday(&tbegin,NULL);
/* insert some numbers into the linked list */
for(i = 100001; i >= 0 ; i--)
insert_node(i);
/* print the list */
printf(" before after\n"), i = 100001;
for(current = head; current != NULL; current = current->next)
printf("%4d\t%4d\n", i--, current->number);
/* free the list */
for(current = head; current != NULL; current = next)
next = current->next, free(current);
// End timer
gettimeofday(&tend,NULL);
// Compute execution time
texec=((double)(1000*(tend.tv_sec-tbegin.tv_sec)+((tend.tv_usec-tbegin.tv_usec)/1000)))/1000.;
printf("Elapsed time = %f\n", texec);
return 0;
}
void insert_node(int value) {
struct node *new_node = NULL;
struct node *cur_node = NULL;
struct node *last_node = NULL;
int found;
new_node = (struct node *)malloc(sizeof(struct node ));
if(new_node == NULL) {
printf("memory problem\n");
}
new_node->number = value;
/* If the first element */
if (head == NULL) {
new_node->next = NULL;
new_node->prev = NULL;
head = new_node;
}
else if (new_node->number < head->number) {
new_node->next = head;
head->prev = new_node;
new_node->prev = NULL;
head = new_node;
}
else {
cur_node = head;
found = 0;
while (( cur_node != NULL ) && ( found == 0 )) {
if( new_node->number < cur_node->number )
{
found = 1;
}
else
{
last_node = cur_node;
cur_node = cur_node->next;
}
}
if( found == 1 )
{
new_node->prev = cur_node->prev;
new_node->next = cur_node;
cur_node->prev->next = new_node;
cur_node->prev = new_node;
}
else
{
last_node->next = new_node;
new_node->next = NULL;
new_node->prev = last_node;
}
}
}
and on my machine :
Code:
./insertion_sort
Elapsed time = 0.940000
./merge_sort
Elapsed time = 9.445000
Can someone explain to me this results thanks.
Regards.
Originally Posted by iMalc
.
