C Programming
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me

The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.

Go Back   Dev Shed ForumsProgramming LanguagesC Programming

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread Dev Shed Forums Sponsor:
  #1  
Old September 20th, 2012, 11:31 PM
ccsr ccsr is offline
Registered User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Sep 2012
Posts: 13 ccsr User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 3 h 34 m 57 sec
Reputation Power: 0
Linked list sorting

Code:
Gll * fun_s(Gll* node,comp_fun comp )
{
    if(!node || !(node -> next) ){
        printf("less than two node in the list\n");
        return node;
    }
    //int ints[] = {12,2,3,4,5,6,1,8,9,10,11,7};
    //int ints[] = {1,12,2,3,5,8,4,9,6,10,11,7};
    while ( 1 ){

        Gll *prev,*curr,*nxt ;
        int swap = 0;
        prev = curr = node ;
        nxt = curr->next;
        while( nxt ) {
            if ( (*comp)(curr->data ,nxt->data) > 0) {
                curr -> next = nxt -> next;
                nxt -> next = curr;
                if(curr == node){
                    prev = node = nxt;
                }else{
                    prev -> next = nxt;
                    prev = nxt ;
                }
                swap = 1;
            }else {
                prev = curr;
            }
            curr = prev -> next ;
            nxt = curr -> next;

        }
        if(!swap)
            break;
    }
        return node;
}

This is program which sorts a linked lists if its unsorted and retains
the same if its sorted.

But the program is not so efficient in the sense that its kind of bubble
sort.In every iteration the next highest element will get sorted out.
But i am not able have a mechanism which can reduce the no of iterations.
That means there is no need to check for already sorted elements.

Please suggest if any other best or optimised mechanism is available.

Also please let me know if you find any problem( does not work for any combination of input)

Reply With Quote
  #2  
Old September 21st, 2012, 01:04 AM
Lux Perpetua Lux Perpetua is offline
Contributing User
Dev Shed Intermediate (1500 - 1999 posts)
 
Join Date: Feb 2004
Location: San Francisco Bay
Posts: 1,936 Lux Perpetua User rank is General 5th Grade (Above 100000 Reputation Level)Lux Perpetua User rank is General 5th Grade (Above 100000 Reputation Level)Lux Perpetua User rank is General 5th Grade (Above 100000 Reputation Level)Lux Perpetua User rank is General 5th Grade (Above 100000 Reputation Level)Lux Perpetua User rank is General 5th Grade (Above 100000 Reputation Level)Lux Perpetua User rank is General 5th Grade (Above 100000 Reputation Level)Lux Perpetua User rank is General 5th Grade (Above 100000 Reputation Level)Lux Perpetua User rank is General 5th Grade (Above 100000 Reputation Level)Lux Perpetua User rank is General 5th Grade (Above 100000 Reputation Level)Lux Perpetua User rank is General 5th Grade (Above 100000 Reputation Level)Lux Perpetua User rank is General 5th Grade (Above 100000 Reputation Level)Lux Perpetua User rank is General 5th Grade (Above 100000 Reputation Level)Lux Perpetua User rank is General 5th Grade (Above 100000 Reputation Level)Lux Perpetua User rank is General 5th Grade (Above 100000 Reputation Level)Lux Perpetua User rank is General 5th Grade (Above 100000 Reputation Level)Lux Perpetua User rank is General 5th Grade (Above 100000 Reputation Level) 
Time spent in forums: 1 Month 1 Week 2 h 12 m 42 sec
Reputation Power: 1312
Bubblesort is one of the worst sorting algorithms, either for arrays or for linked lists. Mergesort, on the other hand, is a pretty good option for sorting a linked list:

- doesn't require random access
- O(n*log(n)) worst case
- doesn't require allocating extra memory

The algorithm:

1. Divide the list in the middle into two lists of close-to-equal size.
2. Recursively sort the two lists.
3. Merge the sorted lists into a single sorted list.

Reply With Quote
  #3  
Old September 21st, 2012, 04:03 AM
bdb bdb is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Aug 2012
Posts: 156 bdb User rank is Sergeant Major (2000 - 5000 Reputation Level)bdb User rank is Sergeant Major (2000 - 5000 Reputation Level)bdb User rank is Sergeant Major (2000 - 5000 Reputation Level)bdb User rank is Sergeant Major (2000 - 5000 Reputation Level)bdb User rank is Sergeant Major (2000 - 5000 Reputation Level)bdb User rank is Sergeant Major (2000 - 5000 Reputation Level) 
Time spent in forums: 1 Week 15 h 48 m 11 sec
Reputation Power: 32
One option is to copy the list to an array, sort the array (using qsort), and copy back to the list.

Reply With Quote
  #4  
Old September 22nd, 2012, 08:38 PM
ccsr ccsr is offline
Registered User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Sep 2012
Posts: 13 ccsr User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 3 h 34 m 57 sec
Reputation Power: 0
Thanks for the replies.
Yeah, i understand.
Before asking here i just googled, many people suggested only these two methods.

I am going to try for any one of these methods.

Reply With Quote
Reply

Viewing: Dev Shed ForumsProgramming LanguagesC Programming > Linked list sorting

Developer Shed Advertisers and Affiliates



Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.

© 2003-2013 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap