429 views
Which of the following is worst choice to sort a linked list?

a)Merge Sort

b) Quick Sort

c) heap sort

d) Insertion sort
in DS | 429 views
0
I think heap sort is completely impossible for linked list.
0
explain a bit , why do  u think impossible?

Heap sort is inefficient on linkedlist

why because

it completely depends on the random access facility of the array, but linked list does not support random access.

Answer is Heap sort as it most dependent on random access which is costly in case on Linked List.

Detailed Explanation:

Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.

MergeSort(headRef)
1) If the head is NULL or there is only one element in the Linked List
then return.
2) Else divide the linked list into two halves.
FrontBackSplit(head, &a, &b); /* a and b are two halves */
3) Sort the two halves a and b.
MergeSort(a);
MergeSort(b);
4) Merge the sorted a and b (using SortedMerge() discussed here)
*headRef = SortedMerge(a, b);

Time Complexity: O(n Log n)

Algorithm
Partition Algorithm
1. Take rightmost element as the pivot
Traverse through the list
a. If the node has value greater than pivot, we will move it after tail

b. else, keep it in same position

QuickSort Algorithm
1. Call Partition(), which places pivot at right position and returns the pivot
2.  Find the tail node of the left sublist ie, left side of the pivot and recur for left list

3.  Now, recur for right list


Below is simple insertion sort algorithm for linked list.

1) Create an empty sorted (or result) list
2) Traverse the given list, do following for every node.
......a) Insert current node in sorted way in sorted or result list.
3) Change head of given linked list to head of sorted (or result) list

Heapsort is a good sorting algorithm because it's O(n log n) and it's in-place. However, when you have a linked list heapsort is no longer O(n log n) because it relies on random access to the array, which you do not have in a linked list. So you either lose your in-place attribute (by needing to define a tree-like structure is O(n) space). Or you will need to do without them, but remember that a linked list is O(n) for member lookup. Which brings the runtime complexity to something like O(n^2 log n) which is worse than bubblesort.