3,075 views
3 votes
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

2 Answers

1 votes
1 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

Related questions