contributed by < Billy4195
>
linux2021
From the naming of list_concat and the argument name, we could guess that the list_concat() is used to concatenate two linked-list, more precisely, list_concat() concatenates the right
list to the last element of left
.
To find the last element in the left
list, we need to traverse through the left
list, the last element is the one that the next ptr stores NULL
.
As a result, the while loop is to traverse the elements in left
list, to find out the last element that should point to the head of right
list. One point is that the left
is the pointer of pointer of node_t
, so during the traversal it store the address of next pointer of the current node. The answer should be ( c ).
According to the requirement, the sorted list should be ascending order. We use pivot to divide the given list
into two list, the right one should be larger than left one. So when the n->value > value
, the n should be add to right
list(AAA), then BBB is left
list.
left
and right
listsleft
listright
listright
listQuick sort is an divide-and-conquer method, the sub-problem should be merged. We need to merge the sorted left
list, pivot and the sorted right
list in order. So the answer will be ( b )
According to the manual page of random()
, the generated random number is controlled by an seed value. It could be specified by using srandom()
. If the srand() is not used,random()
is automatically seeded with value 1.
For each time we execute the program, the seed pass through srandom()
should be different. According to DDerveialm's work and man page, the simplest method to make random()
better is just pass the current time to the srandom()
, e.g. srandom(time(NULL))
But as we execute the program twice less than one second, we could see the same result again(in 3rd and 4th execution).
TODO solve same random value problem when running the program in short time.
According to "Optimized QuickSort — C Implementation (Non-Recursive)", the author use array as the stack to implement an non recursive version of quick sort. But when we wish to apply the same method to sort singly linked-list, it has an problem that the linked-list can't support random access. Inspired by 林韋翰, we can store all nodes in an array, sorts it and then link them together. My implementation is done in this commit
quicksort()
is the entry point to sort an given array, but the linked-list is not support random access. We firstly allocate an array to store all elements for random access(Line 5-26), then we use __quicksort()
to execute the actual sorting algorithm. The sorted elements are stored in the array, so we need to reconstruct the linked-list(Line 28-31).
__quicksort()
is real implementation of the non-recursive quick sort.
The left_stk
and right_stk
array is used to store the left index and right index for the elements to be sorted.