Ivan said:
: Does anyone know how to make quicksort for single linked list without
: using array?
:
: I know that mergesort is maybe better but I need quicksort!!
MergeSort is not maybe better, it is guaranteed to be (as good)
or better than QuickSort when sorting a linked list.
QuickSort requires random access to the elements that are to
be sorted, which make it very unsuitable for a linked list.
Quicksort does not "require" random access. Pluck the first
node from the list and call it the partitioning element, walk
sequentially through the list reassigning its nodes to two new
lists depending on how they compare to the partitioning node (if
desired, make a third list for nodes that compare equal), sort
the two lists recursively, and concatenate.
Unfortunately, it seems difficult to avoid degeneracy in a
way that's both effective and cheap. Choosing the first node as
the partioning element is cheap, but runs a substantial risk of
degeneracy: for example, if the list is already in order or in
reverse order, each partitioning pass accomplishes almost nothing.
You could choose a "random" node from a list of known length at the
cost of generating one random number and traversing (on the average)
half the list before each partitioning pass, or you could make the
choice while building the list at the cost of generating a random
number for each node added. Neither of these strategies seems cheap.
What makes you say that you "need" QuickSort ?
His teacher, I bet.
