linked list sorting..

well i have some kind of problem... the goal is to developt a algorithm to sort a linked list (single or double linked).. that uses the less memory possible.. we can use for exemple auxiliar lists with pointers to the real registers instead of the real lists.. thats an example..
so i dont know if i'll use single or double linked lists... neither the best algorithm..
sorry for the english xD

peace

Well, basically, you can use any sort that you could use to sort an ordinary array of numbers: http://en.wikipedia.org/wiki/Sorting_algorithm

You probably want to use a sorting algorithm that doesn't require random access to the sorting elements; bubble sort, insertion sort, and selection sort would probably be workable.

As for whether you need a single-linked list or a double one, that's your decision. You probably want to avoid sorts like the Shaker sort that practically require double-linked lists. :)

Come up up with a way to merge two already-sorted linked lists into a single sorted linked list. This can be done in constant space by pointer swapping, and doesn't require a doubly-linked list. Once you have that you can mergesort. This requires you to walk down the list to divide it roughly in half each time, but it's an option.

Quote:

---

Originally Posted by brewbuck

Come up up with a way to merge two already-sorted linked lists into a single sorted linked list. This can be done in constant space by pointer swapping, and doesn't require a doubly-linked list. Once you have that you can mergesort. This requires you to walk down the list to divide it roughly in half each time, but it's an option.

---

Yeah I think you're right. Basically you can still do a kind of quick sort. Pick the first node as the pivot. Traverse through the linked list and append all nodes less than the pivot on the left side (the head of the linked list), whilst all nodes greater than the pivot would be inserted to the front of the list to the right of the pivot. You now have two linked lists left and right.
Pointers to mark the beginning and end of each list can be retained. Rinse and repeat the process for each list and each sublist etc., and you're done.

Quote:

---

Originally Posted by SevenThunders

Yeah I think you're right. Basically you can still do a kind of quick sort. Pick the first node as the pivot. Traverse through the linked list and append all nodes less than the pivot on the left side (the head of the linked list), whilst all nodes greater than the pivot would be inserted to the front of the list to the right of the pivot. You now have two linked lists left and right.
Pointers to mark the beginning and end of each list can be retained. Rinse and repeat the process for each list and each sublist etc., and you're done.

---

Rinse and repeat amounts to: recursive calls or an explicit stack. Sure, that may be fine, but it may be that using the least memory possible includes using stack space. Especially since in this case it can amount to O(n) stack space.

dwks' ideas were actually quite sensible, provided an O(n*n) algorithm will suffice.

Otherwise, natural-merge-sort should use only O(1) extra memory and is doable with lists. For the same reasons also consider comb-sort, strand-sort, bingo-sort, odd-even-transposition-sort (a.k.a brick-sort), and possibly even bozo-sort.

> that uses the less memory possible
Well if you can stand to allocate 1 pointer for every element in the list, I would
- allocate an array of 'n' pointers
- set each pointer to point to each successive element of the list
- qsort on the array
- reconstruct the linked list from the sorted array
- free the array of pointers.

Quote:

---

Originally Posted by Salem

> that uses the less memory possible
Well if you can stand to allocate 1 pointer for every element in the list, I would
- allocate an array of 'n' pointers
- set each pointer to point to each successive element of the list
- qsort on the array
- reconstruct the linked list from the sorted array
- free the array of pointers.

---

well.. thats probably the point xP.. but how can i sort the list using an array of pointers? i should look in the list and then change in the array?

Well do you have something to count the number of nodes in the list?

Code:

---

while ( node ) { arr[i++] = node ; node = node->next; }

---

Then sort it - easy

Code:

---

head = arr[0]; for( i = 0 ; i < len-1 ; i++ ) { arr[i]->next = arr[i+1]; } arr[i]->next = NULL;

---