1
$\begingroup$

In CLRS's Introduction to Algorithms,

The following procedure implements quicksort:

QUICKSORT(A; p; r) 1 if p < r 2 q D PARTITION(A; p; r) 3 QUICKSORT(A; p; q-1) 4 QUICKSORT(A; q+1; r)

To sort an entire array A, the initial call is QUICKSORT(A; 1; A.length). The key to the algorithm is the PARTITION procedure, which rearranges the subarray A[p..r] in place.

PARTITION(A; p; r) 1 x = A[r] 2 i = p - 1 3 for j = p to r - 1 4 if A[j] <= x 5 i = i + 1 6 exchange A[i] with A[j] 7 exchange A[i+1] with A[r] 8 return i +1

The quicksort algorithm sorts a set in increasing order, where the pivot is chosen to be the last element in the current array.

I am trying to figure out the worse case and best case to the algorithm.

But I am more interested in whether quicksort will be faster, if the input set is originally more close to the final sorted result. In the concern, I guess the choice of pivot may not matters.

After some thought, the following questions make me think that quicksort will be slower if the input set is more close to the final sorted result.

Is it correct that

  • when the input set is already in decreasing order, the assignments and exchanges in the for loop in PARTITION will be skipped?

  • Does quicksort work faster when the input set is already more sorted in decreasing order?

Thanks.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ What have you tried and where did you get stuck? Which research papers have you read? These issues have definitely been studied. Note that the particular choice of partitioning algorithm is important here, less so the Quicksort wrapping, so you may want to search for results on partitioning. $\endgroup$ Commented Nov 15, 2016 at 12:41

2 Answers 2

Reset to default
1
$\begingroup$

First, this is not the Quicksort that we all know and love, but some rather strange version of it, so your results cannot be applied to what is usually called Quicksort.

If the array is already in descending order, your version (unlike the original Quicksort) will not do any exchanges in the first partitioning. So the partitioning will be fast. However, it makes practically no progress; only one element is moved to its right position, and you will have about $n^2 / 2$ comparisons in total, which is about the worst case possible.

An array in ascending order is even worse, since you will do $n^2/2$ comparisons, plus $n^2/2 exchange operations.

Improve this answer
$\endgroup$
3
  • $\begingroup$ What is the Quicksort that you all know and love? $\endgroup$ Commented Jan 14, 2017 at 22:38
  • $\begingroup$ Partitioning starts both at the left and the right, until it finds an element > pivot on the left, and an element < pivot on the right, and exchanges them. $\endgroup$ Commented Jan 15, 2017 at 9:33
  • $\begingroup$ And typically you wouldn't take the first or last element the pivot, because that makes sorts and reverse sorted take quadratic time. $\endgroup$ Commented Jan 15, 2017 at 21:58
0
$\begingroup$

This may not answer your question, but it is a bit more information than belongs in a comment.

In theory, you seem to have answered your own question. :)

In practice, well what have you tried?

The fact of the matter is that it's difficult to determine, really it depends.

I would suggest that CPUs are complicated and predicting where speedups will occur is often counter intuitive. It often depends on the trade-offs between memory usage and computational load. Even more adversely, we have little control over what code our compilers will emit or what they are optimizing for and finally we have zero control over how the CPU will decide to optimize what it is trying to do. The best we can do is understand as much of the process as we can research and learn about and from there make educated guesses about how to proceed.

This article gives a good in-depth analysis, for example, of one of the cornerstones of algorithmic search. Admittedly not what you're looking for, but it was close at hand and it will give you a better sense of the arena in which you struggle. For the reasons in that article, many advanced implementations take a high-level and multi-tiered approach to problem solving, relaxing rules when they matter least, relying on special CPU instructions when they are available and otherwise attempting to cover as much territory as possible to give the best results all-around for a given problem. Often times that can get murky and far from trivial.

Many programmers prefer to stick with approaches that are easier to understand and code. I remember seeing an algorithm ( forgive a lack of an example here ) I believe one of Chazelle's which has been above the radar for a decade, yet no implementation exists - not even one by him.

I hope this helps to clarify part of the problem for you. And much luck in your quest!

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.