CODEWITHSUNDEEP
algorithmsortingtime-complexity
Zephyr
Zephyr

Reputation: 1621

Why don't we use quick sort on linked list?

Quick sort algorithm can be divided into following steps

1) identify pivot.

2) Partition the linked list based on pivot.

3) Divide the linked list recursively into 2 parts.

Now, if I always choose last element as pivot, then identifying pivot element (1st step) takes O(n) time.

After identifying pivot element, we can store it's data and compare it with all other elements to identify correct partition point (2nd step). Each comparison will take O(1) time as we store the pivot data and each swap takes O(1) time. So in total it takes O(n) time for n elements.

So recurrence relation is

T(n) = 2T(n/2) + n which is O(nlogn) which is same as in merge sort with linked list.

So why is merge sort preferred over quick sort for linked list ?

Upvotes: 1

Views: 1685

Answers (2)

valdo
valdo

Reputation: 12933

Now, if I always choose last element as pivot, then identifying pivot element (1st step) takes O(n) time.

It actually takes O(1) time. But anyway, a common misconception w.r.t. quick-sort is the idea that you may pick a predefined element as a pivot, rather than random. You may not.

Quick-sort works on average in O(N log(N)), but worst-case is O(N^2). Now, when the pivot is chosen randomly and algorithm is performed on large sets - then indeed O(N log(N)) is what you get in practice. However if you pick a predefined pivot, then, depending on the pattern of your data, you can easily hit the worst-case. Think that the source data is not random, it comes from some source, and exhibits some pattern.

For instance, if you take the last element as the pivot, and your source data just in case is already sorted in reverse order - then you'll definitely get the degenerate case of O(N^2).

Regarding your question why quick-sort isn't used usually for linked lists. The reason (IMHO) is that for lists the merge-sort is a preferred way to go. It guarantees the worst-case performance of O(N log(N)). It's usually not used for arrays, because in case of arrays it needs extra memory allocated, but this is not the case with linked lists.

Upvotes: 1

rcgldr
rcgldr

Reputation: 28828

So recurrence relation is ... O(nlogn)

Worst case quicksort on arrays is O(n^2), for example, each level of recursion only reduces the size of the largest partition by 1 or 2 (2 if pivot not included in either partition).

So why is merge sort preferred over quick sort for linked list ?

It's much faster, especially bottom up merge sort which eliminates scanning of lists to split them. Instead it uses a small (26 to 32) internal array of pointers or references to nodes (or small array of lists), merging nodes into the array, then merging the array to create a sorted list. Wiki article includes pseudo-code:

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

Upvotes: 2

Related Questions