• Post Reply Bookmark Topic Watch Topic
  • New Topic

Help me sort my Singly Linked List  RSS feed

 
Ranch Hand
Posts: 122
C++ Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay guys, I searched a lot but can't seem to understand the sorting of a SLLNode... I noticed a method called Bubble Sort, I understand how it works, but can't think of a way to implement it to my code... Can you please give me a hand?
 
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kaspersky Ukshini wrote:Okay guys, I searched a lot but can't seem to understand the sorting of a SLLNode... I noticed a method called Bubble Sort, I understand how it works, but can't think of a way to implement it to my code... Can you please give me a hand?

I'm afraid nobody here is going to write it for you Kaspersky. Why don't you show us what you've done so far?

I should warn you that it's likely to be fairly fiddly, because in order to move a Node - which you'll need to do in order to "swap" it - you'll need to keep track of the Node before it (assuming the List is forward-pointing). Luckily, in a bubble sort, the Nodes you swap are always adjacent, so it's less hassle, but you'll still need to keep track of the Nodes before and after the ones you're actually swapping.

Another little tip for you: When "moving" Nodes in any linked list, try and disturb the List as little as possible while you're doing it. The technique I learned I call "bridging", although I'm not sure that it's technically correct. Suppose you have a set of Nodes:

... → A → B → C → D → ...

and you want to swap B and C around. The sequence goes something like this:

  • 1. Point B to D. This effectively "removes" C from the List, since nothing points to it any more, so anything that happens to be traversing the List at this point will move from A to B to D. However, since C still points to D, any traversal that happened to be on C at the time will still move on to D.
  • 2. Point A to C. This effectively "removes" B from the List, and re-attaches C after A, so anything that happens to be traversing the List at this point will now move from A to C to D; however, since B also points to D, any traversal that happened to be on B at the time will still move on to D.
  • 3. Finally, point C to B. This re-attaches B to its new position in the List.

  • It's by no means the only way to do it, but there are sequences that make it more likely for Nodes to be repeated, so be careful. [*]

    And if you don't follow the description, get out a piece of paper and write it down in diagrams - linked lists are tricky, and a picture is often worth a thousand words.

    HIH

    Winston

    [*] PS: Repeated Nodes can happen with the above procedure as well - specifically, the sequence A → B → C → B → D - but it would be very unusual. Indeed, I don't think repetition can be prevented without synchronization, although I'm sure someone will correct me if I'm wrong.
     
    Kaspersky Ukshini
    Ranch Hand
    Posts: 122
    C++ Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    This is what I've come up with until now:

    I'm copying my D.L list into another one, and then create another one. The reason is simple, I compare two D.L lists (which are the same), the first with all, once i find the biggest, I add it as first into another list.. then I get the 2nd element, compare with the rest.



    It's working but not in all the cases... I'm missing something!

    EDIT: Fixed it!! THANKYOU!
     
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!