I'm using Queue Abstract Data Type which is based on Singly Linked List. I want to sort the data which Queue keeps in 3 ways: First with merge sort, second with quick sort, third with heap sort. So is there anyone can help about this?
7
-
1What, specifically, do you need help with?Oliver Charlesworth– Oliver Charlesworth2011-12-26 20:33:55 +00:00Commented Dec 26, 2011 at 20:33
-
@OliCharlesworth Don't have any idea where to enqueue or where to dequeue in my sorting algorithms.kmetin– kmetin2011-12-26 20:39:18 +00:00Commented Dec 26, 2011 at 20:39
-
One simple way to do this is to dump the queue into a normal array, do the sort on the array, and then transfer everything back into the queue.Oliver Charlesworth– Oliver Charlesworth2011-12-26 20:41:03 +00:00Commented Dec 26, 2011 at 20:41
-
You're right. But its an assignment and its not allowed to do that.kmetin– kmetin2011-12-26 20:42:48 +00:00Commented Dec 26, 2011 at 20:42
-
6Queues have an intrinsic order which means they can't be sorted. You can sort the underlying data structure if you want, but that will mess up the queue. Your question makes no sense.Mark Ransom– Mark Ransom2011-12-26 20:48:29 +00:00Commented Dec 26, 2011 at 20:48
|
Show 2 more comments
1 Answer
Ordinarily a queue is sorted by insertion order - items are sorted by the order in which they were inserted into the queue. It appears you want to break that essential quality of a queue.
I'm only going to cover merge sorting with this answer. Hopefully others will cover the other algorithms or you can derive them yourself.
A single linked list can be treated as a list of lists simply by knowing when one list ends and another begins. For a merge sort you need to start with sorted lists - if each list has a length of 1, it is sorted simply because no other order is possible. Merging two linked lists into one is easy - you take the smallest item from each of two lists and link it into a new list, until both lists are exhausted. So for the first pass, you break the list into sublists of length 1, and combine them into sublists of length 2. The second pass you merge the sublists of length 2 into sublists of length 4. Each pass doubles the size of the sorted sublists. You're finished when the size of the sorted sublist is greater or equal to the size of your entire list.
