cpppro

Sorting a Linked List with QuickSort – Simple Algorithm

In C Tidbits, Data Structures in C/C++ on May 1, 2007 at 7:42 pm

Quicksort is the fastest known sorting algorithm in practice. Its average running time is O(nlogn). It is based on devide and conquer idea:
partition into two lists and put them back together again. It does more work on the divide side, less on the combine side.

The basic algorithm is
1)pick any element (called as Pivot) in list
2)Partition the list as two parts, first part contains all the elements which are less than pivot, the other contain all the elements which are greater than pivot
3)do quicksort recursively on sub lists

Regarding step1:
Any element can be selected as pivot, but some choices may cause bad performance. Example. first element everytime: this pivot cause bad performance on presorted or lists in reverse sorted order, because all elements go into one sublist. One safe strategy is choosing pivot randomly.

regarding Step2:
As already pointed out quicksort does most of the work while partitioning the lists, so this is the step which is a bit complex..

both step1 and 2 are represented graphically below…

Please refer http://www.refcode.net/2013/02/sorting-linked-list-with-quicksort.html

 

Advertisements
  1. I would not like to say simple algorithm 🙂 but it is understandable as it is similar to arrays version, good work.

  2. good work

  3. yes simple to understand, I was able to map this work to array version of it, BTW I can’t see merge sort here

  4. Neat implementation. Thanks for your time.

  5. j– runs into an infinite loop in the above quicksort module.

    Try sorting the following data with above code:
    301 -> 101 -> 201 -> 102 -> 201 -> 202 -> NULL

    FIX:
    (1) Add check “(j >= chain_start)” in j– loop
    +
    (2) Add check “(i <= (chain_end – 1))” in i++ loop

  6. I don’t understand this partition code from the QSort() function:

    for(;;)
    {
    //start partitioning the list
    for(;a[i]pivot;j- -);
    if (i<j)
    Swap(&a[i], &a[j]);
    else
    break;
    }

    If a[i] == a[j] == pivot then you will exit out of both for loops, swap the same two numbers, and then continue back to the top of the “for(;;)” loop. Thus resulting in an infinite loop.

    If anyone is interested in how to add video to their applications, I posted a article on that here:
    http://www.thread-pool.com/2008/10/22/gstreamer/

  7. Are you sure that this implementation is really efficient for single-linked lists?
    The time complexity of QuickSort if O(N*logN) – in terms of the number of comparisons, so it is supposed that reaching and swapping elements can be done in constant (O(1)) time.
    But it tries to find the previous node in every Swap from the beginning of the list (FindPrev), then Swap becomes linear (O(M), where M is the average length of partial lists), so the time complexity of this implementation is around O(M*N*logN) in terms of advancing item pointer, which can be even worst than e.g. Bubble Sort algorithm (O(N*N)). Intensive usage of GetNthNode and FindPrev elsewhere makes it even worst.
    So I would not use this implementation unless somebody corrects my above logic.

  8. It runs into infinite loop even with the fix mentioned.

    Use int data[] = {0,7,2,5,3,3,6,9,4,1,8,3,9,6};

  9. right = GetNthNode(list, list_end);
    left = GetNthNode(list, list_start);

    Is “GetNthNode(list, list_start)” part of an included library or do you have to write your own? Sorry, I’m a total newbie at this but now that I’ve discovered this site, I’m sure gonna be following it all the time!

    http://www.castlesteps.com/apartments.htm

  10. Sathish and all,

    Sorry for the delayed response. I didn’t check this site lately.

    You said that
    >>It runs into infinite loop even with the fix
    >>mentioned.
    >>Use int data[] =
    >>{0,7,2,5,3,3,6,9,4,1,8,3,9,6};

    Kindly note the following points again.
    ———————————-
    #POINT NO.1#
    I corrected this code for linked lists having UNIQUE elements only.

    I tried to run my code for the following data set:
    0,7,2,5,3,6,9,4,1,8 (removing duplicate values)

    It works absolutely fine.
    Here is the sample output:
    0,1,2,3,4,5,6,7,8,9

    ———————————-
    #POINT NO.2#
    Let me re-post the code I modified.

    **[BEFORE]**
    Function: quicksort
    Line #: 22 (approx.)
    for(;left->info info; left=left->next,i++);

    for(;right->info > pivot->info; right = FindPrev(list,right),j- -);

    **[AFTER]**
    Replace the code as below:

    while ((left->info info) &&
    (i next;
    i++;
    }

    while ((right->info > pivot->a) &&
    (j >= chain_start))
    {
    right = FindPrevListData(p_chain, right);
    j–;
    }

    ———————————-

    Kindly re-test it and let me know again!
    I’m watching this page!

  11. Reposting my code since it got garbled in the above post.

    **[AFTER]**
    Replace the code as below:

    while ((left->info info) && (i next;
    i++;
    }

    while ((right->info > pivot->info) && (j >= list_start))
    {
    right = FindPrev(list, right);
    j–;
    }

  12. My apologies.
    There seems to be some problem while posting operator symbols in my text.
    I’m adding white space between the code and re-posting again.

    while ( ( left – >info info ) & & ( i next ;
    i + + ;
    }

    while ( ( right – > info > pivot – > info) & & ( j > = chain_start ) )
    {
    right = FindPrev(list , right);
    j – – ;
    }

  13. I am posting it in English text since it is getting garbled everytime. Kindly re-interpret by yourself in language syntax.

    a.
    while info of left is less than info of pivot AND while i is less than or equal to list_end minus one,
    set left equal to next of left.
    Increment i by one.

    b.
    while info of right is greater than info of pivot and j is greater than or equal to list_start,
    set right equal to return value from function call FindPrev with arguments as list and right.
    Decrement j by one.

    Phew! That’s all!

  14. i dont get it why do peolpe still use C/C++
    i beleave pascal is as powerfull as c
    and delphi is almost as powerfull as c++
    but pascal/delphi are easier to learn,their code is better to go through and debug
    i dont get it why take a ride on an 80/miles per hour car when you can take a ride on 80/miles per hour luxury car!

  15. hey for graphics related programs please visit
    http://www.code-heaven.blogspot.com
    will post sorting and scheduling algorithms later!!

  16. @ star scream
    correction: delphi IS as powerfull as c++!
    and it actually is generally easier to learn and code
    but i was taught c++ in my university and have over 10 years of experiance in it i wont bother learning a new language
    though if i was given a choice i would have chosen delphi

  17. thanks very much, great information. Keep up the great work.

  18. When u have more than two equal elements this algorythm also runs in infinite loop.
    To avoid this, just add in while loops equation.

    “johnnycool said:

    a.
    while info of left is less than or EQAUL to info of pivot AND while i is less than or
    ….

    b.
    while info of right is greater than or EQUAL to info of pivot and j is greater than or equal to list_start,

    ….”

    Now it works in all cases.

    And I want to thank to the fans of Pascal and Deplphi for make me and my friends laughing our heads off.

  19. @johnnycool

    hey can u plz tell me how i need to change code by ur code
    i think there is some syntax error plz let me know what i hv to do exectly

    while ((left->info info) && (i next;
    i++;
    }

    what is this mean?
    i get second while loop but what is this in first one

  20. Hi Johnnycool, please insert code between

    , 

    tags, so that your format will be preserved..

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: