1

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 ?

Zephyr
  • 1,521
  • 3
  • 22
  • 42
  • 3
    *merge sort preferred for linked list* - citation is required. – Eugene Sh. Nov 30 '17 at 18:45
  • 1
    I'm voting to close this question as off-topic because this is better addressed to the [Computer Science](http://cs.stackexchange.com) site. – tadman Nov 30 '17 at 18:45
  • 1
    @tadman So am I not allowed to ask algorithm and time complexity questions here ? There are tons of questions like this on this site. – Zephyr Nov 30 '17 at 18:48
  • 1
    As no citation is provided I looked it up myself and the [very first result](http://www.geeksforgeeks.org/merge-sort-for-linked-list/) is stating *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*. – Eugene Sh. Nov 30 '17 at 18:52
  • Many of those questions pre-date the existence of the Computer Science site. They're better equipped to handle abstract questions like this. If you have an *implementation* you'd like to discuss, it's important to include actual code. Stack Overflow tries to be very pragmatic, as in "here's code that fixes your problem", compared with the CS version which can be more concerned about theory. – tadman Nov 30 '17 at 18:52
  • @EugeneSh. yeah, everywhere its written comparisons require more time per operation. But in my idea above, it requires only O(1) time and not O(n) time per comparison. – Zephyr Nov 30 '17 at 18:53
  • @Nemo If you want to take a stab at a formal answer here that's your prerogative. I'm just giving my opinion here: The CS crowd can give you a lot more theory and background because that's what that site is all about. – tadman Nov 30 '17 at 18:57
  • 2
    I've done it before and it works fine. I'd say the primary obstacle is practical inefficiency of applying more advanced/tricky pivot choosing algorithms. Without random access even simple median-of-three requires a full pass over the list. However, recent trends like this https://stackoverflow.com/questions/40622430/stdlistsort-why-the-sudden-switch-to-top-down-strategy might make that point obsolete. – AnT stands with Russia Nov 30 '17 at 18:59
  • @AnT Almost everywhere it's written that quick sort is not preferable for linked list. So I thought to confirm it by asking here. Thanks! – Zephyr Nov 30 '17 at 19:08
  • *"Almost everywhere..."* your question should at least provide evidence of this. – trincot Nov 30 '17 at 19:12

2 Answers2

2

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

rcgldr
  • 27,407
  • 3
  • 36
  • 61
  • I understand every random access requires O(n) time in linked list. But in my idea every comparison takes O(1) time and not O(n). Can you point out which step in quicksort requires more time in linked list than in arrays? – Zephyr Nov 30 '17 at 20:17
  • 1
    @Zephyr - consider the worst case example where the largest partition for each level of recursion is only reduced by 1, that means n-1 levels of recursion, and (n-1-recursion level) comparisons for each level of recursion for a time complexity of O(n^2). – rcgldr Nov 30 '17 at 20:23
  • Yes, worst case complexity is O(n^2). But even in linked list it should be O(n^2) . I don't understand how is it O(n^3) in linked list. – Zephyr Nov 30 '17 at 20:32
  • @Zephyr - I updated my answer and deleted the reference to O(n^3). I was thinking of another situation. – rcgldr Nov 30 '17 at 20:33
  • @Zephyr - you could do a variation of quicksort to eliminate swaps, but it would still have worst case time complexity of O(n^2). For each level of recursion, the first node is used as the pivot, and 3 lists are created, nodes < pivot, nodes == pivot, nodes > pivot. Recursion is used on the first and third sub-lists, then the three lists are linked together. – rcgldr Nov 30 '17 at 20:39
1

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.

valdo
  • 12,632
  • 2
  • 37
  • 67