Sorting list performances

This is a discussion on Sorting list performances within the C Programming forums, part of the General Programming Boards category; Originally Posted by iMalc MergeSort is certainly very good for lists, better than quicksort really since that cant tend towards ...

  1. #16
    Registered User
    Join Date
    Feb 2010
    Posts
    72
    Quote Originally Posted by iMalc View Post
    MergeSort is certainly very good for lists, better than quicksort really since that cant tend towards O(n^2).
    However the killer is BucketSort. Merge Sort is a long way ahead of most other algorithms for linked-list sorting and then BucketSort is light-years ahead of that.
    The catch of course is that your key needs to support being split into buckets, as well as just being directly comparable. In your case you are using ints for which it is fine.
    Thanks iMalc, i've never heard about BucketSort, can you give some links? in my case MergeSort is about O(n*log(n)), what about BucketSort?

    Regards.

  2. #17
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,751
    Quote Originally Posted by evariste View Post
    Thanks iMalc, i've never heard about BucketSort, can you give some links? in my case MergeSort is about O(n*log(n)), what about BucketSort?

    Regards.
    Bucket sort is just a sort where you separate the data into buckets, sort the buckets, and then rebuild a new sorted data structure. One example is here.

  3. #18
    Registered User
    Join Date
    Feb 2010
    Posts
    72
    Quote Originally Posted by whiteflags View Post
    Bucket sort is just a sort where you separate the data into buckets, sort the buckets, and then rebuild a new sorted data structure. One example is here.
    Tnakyou very much whiteflags .

    Regards.

  4. #19
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,114
    Quote Originally Posted by manasij7479
    Insertion sort is O(n^2) only when each insertion is linear.
    That is generally not the case in lists. (I'm not very sure about this point, especially in this context)
    Insertion sort on an array has O(n^2) time complexity because the insertion takes linear time even though finding the insertion point can be done in O(log n) time. Insertion sort on a linked list would still have O(n^2) time complexity because while the insertion takes constant time, finding the insertion point takes linear time.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #20
    Registered User
    Join Date
    Feb 2010
    Posts
    72
    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.

  6. #21
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,114
    When testing merge sort, you insert 1000002 elements into the linked list; when testing with insertion sort, you insert 100002 elements into the linked list.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #22
    Registered User
    Join Date
    Feb 2010
    Posts
    72
    Quote Originally Posted by laserlight View Post
    When testing merge sort, you insert 1000002 elements into the linked list; when testing with insertion sort, you insert 100002 elements into the linked list.
    Really thanks laserlight , apologize.

    Many regards.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with list sorting
    By dnguyen1022 in forum C++ Programming
    Replies: 1
    Last Post: 04-23-2009, 11:46 PM
  2. Replies: 16
    Last Post: 08-26-2008, 12:08 AM
  3. help with sorting a list :(
    By Axel in forum C Programming
    Replies: 54
    Last Post: 10-16-2006, 08:10 AM
  4. Compiler performances...
    By lyx in forum C++ Programming
    Replies: 2
    Last Post: 09-21-2003, 01:38 PM
  5. std::list<*> sorting
    By ziruz in forum C++ Programming
    Replies: 18
    Last Post: 06-25-2003, 04:23 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21