1

Given a string, seperted by a single space, I need to transfer each word in the String to a Node in a linked list, and keep the list sorted lexically (like in a dictionary).

The first step I did is to move through the String, and put every word in a seperate Node. Now, I'm having a hard time sorting the list - it has to be done in the most efficient way.

Merge-sort is nlogn. Merge-sort would be the best choice here?

Improve this question
4
  • 1
    A better approach would be to implement an insert function that attempts to insert each word in the correct order in the linked list. Commented Jun 21, 2015 at 15:40
  • "...and keep the list sorted lexically." That sounds like you need to keep it sorted for each insertion. Are you sure you're allowed to sort it once after all words are inserted? Commented Jun 21, 2015 at 15:40
  • 1
    I tried to do this while going through the text, but the problem is that it's only possible to add a new word to the start or to the end, no? Each check will require another loop (to know where to insert the new word).. Commented Jun 21, 2015 at 15:43
  • insertion sort is O(n^2), isn't it? Commented Jun 21, 2015 at 15:47

2 Answers 2

Reset to default
1

Generally if you had a list and wanted to sort it merge sort is a good solution. But in your case you can make it better.
You have a string separated by spaces and you break it and put it in list's nodes. Then you want to sort the list.
You can do better by combining both steps.
1) Have a linked list with head and tail and pointers to previous node.
2) As you extract a word from the sentence store the word in the list in inserted order. I mean you start from the tail or head of the list depending on if it is larger or smaller than these elements and go forward until you reach an element larger/smaller than the current one. Insert it at that location. You just update the pointers.

Improve this answer
Sign up to request clarification or add additional context in comments.

12 Comments

Thanks, sounds very logical. One more question: if the only attribute I can use in the class List is "head", can I still use your approach? (can't add another attribute except for the head). What I'm allowed to touch is the Node iteself (not the list). In the Node class itself, I have only textual value and a pointer to the next Node.. So I guess it doesn't work here :S
@Osh24:If you have only head you can still do it but it is a bit more tricky. You would need to start moving forward from head and keep a pointer of the next->next element so when you want to put something in between 2 nodes because that is its place you won't lose any element's reference
I don't get it. Let's say we have "Hello Beautiful World". I'm starting to go through the String, "Hello" -> setting the head pointer to "Hello" Node. Then, "Beautiful". Lexically before "H", so I am making a new Node "Beautiful", where its next is "Hello", then set the head to Beautiful. What's next? "World" should be last, I'm not sure how to approach that situation.
And what if I have more than 3 words? Getting to the last Node will require passing through the entire list, no?
@Osh24:Originally you have an empty list so you add Hello->NULL. Then you have beautiful and you start traversing the list until you find an element that is bigger than what you currently have. In this case you find Hello bigger and stop there so you have Beatiful->Hello->NULL. Then you have World and start traversing the list and you see that it is bigger than Beatiful so you keep on going, bigger than Hello, keep going and reach the end of list so you add it there and end up with Beatiful->Hello->World->NULL. Basically it is same reasoning as insert sort
|
0

Just use the built-in Collections.sort, which is a mergesort implementation. More specifically:

This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.

Improve this answer

2 Comments

Thanks, but they require that we write the code on our own (preparation for an exam). Anyway, mergesort is the most efficient way for this kind of problem, true?
That's a really surprising algorithm. Don't most built-in sorting methods use a variation of Quick Sort?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.