The Gateway to Computer Science Excellence

+3 votes

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

a)Merge Sort

b) Quick Sort

c) heap sort

d) Insertion sort

a)Merge Sort

b) Quick Sort

c) heap sort

d) Insertion sort

0 votes

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.

ref : https://stackoverflow.com/questions/10885449/heap-sort-using-linked-lists

0 votes

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

Detailed Explanation:

Merge Sort for Linked Lists:

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) and update the head pointer using headRef. *headRef = SortedMerge(a, b);

**Time Complexity: **O(n Log n)

Quick Sort on Linked List:

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

Heap Sort on Linked 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.

Ref: https://www.geeksforgeeks.org/merge-sort-for-linked-list/

https://www.tutorialcup.com/interview/linked-list/quick-sort-singly-linked-list.htm

https://www.geeksforgeeks.org/insertion-sort-for-singly-linked-list/

https://stackoverflow.com/questions/10885449/heap-sort-using-linked-lists

0

Heap sort can be applied when we have a heap data structure. And ** a heap is a non linear data structure, while a linked list is a linear data structure.** Thus, the very basic underlying data structure prevents heap sort being used on a linked list.

Heap sort can be applied on array as the heap data structure can be easily implemented using indexing.Also, "structures"(nodes) can be used to construct heap and heap sort can be applied on that just like we do for arrays.

52,315 questions

60,427 answers

201,757 comments

95,237 users