qsort and linked-list

This is a discussion on qsort and linked-list within the C Programming forums, part of the General Programming Boards category; I wonder if someone answers my question, if somebody tried to use qsort to sort link-list?!!...

  1. #1
    Registered User
    Join Date
    Mar 2004
    Posts
    11

    qsort and linked-list

    I wonder if someone answers my question, if somebody tried to use qsort to sort link-list?!!

  2. #2
    ggs
    ggs is offline
    C > C++ duders ggs's Avatar
    Join Date
    Aug 2001
    Posts
    435
    roll your own
    .sect signature

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I suppose you could. Though I really don't see the point. Why not just insert in order when you create the list in the first place? I suppose you could have a list that simply [a][pre]ppends the data, and you want to sort it later. But yes, you could use qsort. Remember that with qsort, you're writing your own compare function for it to use. So yeah, you could get it to work. Again, I'm not really sure why you'd want to. I wouldn't. I'd just write a function to sort the list for me. Basicly just reconstruct the list prepending or appending as needed.

    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    ggs
    ggs is offline
    C > C++ duders ggs's Avatar
    Join Date
    Aug 2001
    Posts
    435
    mergesort is better for list
    .sect signature

  5. #5
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    ... and don't forget the standard implementation of qsort is for arrays only.

    Skip Lists are pretty neat, if you want an alternative.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Hammer
    ... and don't forget the standard implementation of qsort is for arrays only.

    Skip Lists are pretty neat, if you want an alternative.
    That's why you "sort it" into an array of pointers to your nodes.

    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Fair point Kinda defeats the point of having a dynamically sizable list though!
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Hammer
    Fair point Kinda defeats the point of having a dynamically sizable list though!
    Sure, but if you're really fond of qsort...

    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Registered User
    Join Date
    Mar 2004
    Posts
    11
    Thanks for all of you,
    I tried to implement the approach on the following link ( for Kent):

    http://www.experts-exchange.com/Prog..._20754585.html

    but I am having problem on the last line(sorted_stocks[index ++] = n of this function

    void CopyListToArray(List l)
    ({
    Node *n;
    int index;
    for(index =0, n =l ; n ; n= n-> next)
    sorted_stocks[index ++] = n; //////////here is the problem?!!!
    })

    compiler displays: [C++ Error] Main.c(518): E2096 Illegal structure operation

  10. #10
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >E2096 Illegal structure operation
    What is sorted_stocks declared as?
    My best code is written with the delete key.

  11. #11
    Registered User
    Join Date
    Mar 2004
    Posts
    11
    That is the declaration for n and sorted_stocks:

    for sorted_stocks:

    //global
    typedef struct node
    {

    Item item;
    struct node *next;

    }Node;

    Node sorted_stocks[MAX_NO_ITEM];


    for n (inside CopyListToArry()):

    Node *n;

  12. #12
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    You want to either change the statement:
    Code:
    sorted_stocks[index ++] = *n;
    Or the declaration of sorted_stocks:
    Code:
    Node *sorted_stocks[MAX_NO_ITEM];
    As it is, sorted_stocks[index] is a Node, but n is a pointer to Node. The types do not match.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. QSort on structure array
    By Leftos in forum C Programming
    Replies: 8
    Last Post: 01-15-2008, 09:51 AM
  2. Inputting into linked list and then sorting it
    By bigtruckguy3500 in forum C Programming
    Replies: 7
    Last Post: 04-23-2007, 11:05 AM
  3. sorting in linked lists
    By vice in forum C Programming
    Replies: 2
    Last Post: 05-07-2005, 11:07 PM
  4. sorting a linked list with qsort()
    By caduardo21 in forum C Programming
    Replies: 12
    Last Post: 04-19-2005, 09:08 PM
  5. Sorting strings to speed up search?
    By Mox in forum C++ Programming
    Replies: 5
    Last Post: 09-10-2001, 01:17 PM

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