hello i got an unsorted linked list and i need to sort it by acertain field and afterwards i need to return the linked list to its previous unsorted condition without making a copy of the list.
+2
A:
When you say "return the linked list to its previous unsorted condition", do you mean the list needs to be placed into a random order or to the exact same order that you started with?
In any case, don't forget that a list can be linked into more than one list at a time. If you have two sets of "next"/"previous" pointers, then you can effectively have the same set of items sorted two different ways at the same time.
bta
2010-08-23 19:08:38
it needsto be placed into the exact same order that i started with
Nadav Stern
2010-08-23 19:10:54
@Nadav Stern- The easiest thing to do would be to keep the list in the current unsorted order and add a second set of list pointers to the array items (you can call them "next_sorted"/"prev_sorted", etc). Sort the list using the new pointers, and the old pointers will retain your current order.
bta
2010-08-23 19:12:55
You can create a second linked list that points to elements in the first list. The second list can be sorted in any order without affecting the original list. Also, the second list does not require any modification to the elements in the original list.
Thomas Matthews
2010-08-23 22:29:21
A:
Taking your points in reverse order, to support returning to original order, you can add an extra int field to each list node. Set those values based on the original order, and when you need to return it to the original order, just sort on that field.
As far as the sorting in general goes, you probably want to use something like a merge-sort or possibly a Quick-sort.
Jerry Coffin
2010-08-23 19:10:36
A:
You can make that data structure somewhat like this.
struct Elem {
Elem* _next;
Elem* _nextSorted;
...
}
Then you can use any algo for sorting the list (maybe merge sort)
Klark
2010-08-23 19:11:58
this is C, not C++. You need to do `struct Elem* _next`. By the way, why the underscore?
mathepic
2010-08-23 20:40:31
A:
If you want to keep your linked list untouched, you should add information to store the ordered list of elements.
To do so, you can either create a new linked list where each element points to one element of your original linked list. Or you can add one more field in the element of your list like sorted_next.
In any case, you should use a sequential algorithm like mergesort to sort a linked list.
Here is a C source code of mergesort for linked lists that you could reuse for your project.
Jérôme Radix
2010-08-23 19:41:42
+1
A:
To do this you will need to either sort and then restore the list or create and sort references to the list.
To sort the list directly Merge Sort is most likely the best thing you could use for the initial sort, but returning them to their original state is tricky unless you either record your moves so you can reverse them or store their original position and resort them using that as the key.
If you would rather sort the references to the list instead you will need to allocate enough space to hold pointers to each node and sort that. If you use a flat array to store the pointers then you could use the standard C qsort to do this.
If this is an assignment and you must implement your own sort then if you don't already know the length of the list you could take advantage of having to traverse it to count its length to also choose a good initial pivot point for quicksort or if you choose not to use quicksort you can let your imagination go wild with all kinds of optimizations.
nategoose
2010-08-23 20:15:12