3

I recently saw Quick Sort - Computerphile video on Youtube about how quicksort works (on paper) and I have a question. Imagine that we have an array that contains for example "27,6,19,2,15,9,10". In first place I choose 10 as pivot and the array becomes like this: 9,2,6 |10| 27,19,15. Then I choose 6 as pivot for the left unsorted array and it becomes 2 |6| 9 and for the right one I choose 19 as a pivot and the right unsorted array becomes 15 |19| 27. The question is: Can I choose any pivot I want to make my job easier (like I did in this example) or there is something more?

Edit: If I chose 27 as pivot instead of 19 how the array would be?

lor
  • 69
  • 11

3 Answers3

3

You can choose any value such that no part of the partition will be empty, i.e. not smaller than the smallest nor larger than the largest. (The value needn't be one of an element of the array.)

The more balanced the partition (so the closer to the median), the better. Even though this is never done, the arithmetic mean could do.

A common strategy is the median of three (first, central and last elements).

  • I have updated the question about the **last** part that you say. Please take a look. – lor Aug 09 '16 at 16:00
  • @lor: I don't see the relation between your edit and my last sentence. –  Aug 09 '16 at 16:02
  • My bad. I typed last instead of first. I have to specify that if we choose a different pivot than the ones I chose, like 2 instead of 6 and 27 instead of 19 what would be the difference? The sub array would look like |2| 6 9 and 15 19 |27| or we would have something else here? – lor Aug 09 '16 at 16:11
  • @lor What else could it be ? –  Aug 09 '16 at 16:13
  • I have a point. Just can't say it right. Here is an example. In the first place that we chose `10` as pivot, it only matters to place the smallest than pivot to the left and greater than pivot to the right without carrying about how they're placed or we start from left to right and put the elements in they right side? For example if I chose `2` for the first unsorted array, should I write |2| 9 6 and make another pass or should I write |2| 6 9 directly? – lor Aug 09 '16 at 16:45
  • Thanks it helped a lot. `i.e. not smaller than the smallest nor larger than the largest` – parsecer Dec 03 '20 at 14:11
2

In principle you can take any array element as the pivot; the algorithm will work. In practice, if you pick the smallest or largest element of the array as the pivot, one pass of the Quicksort algorithm will achieve very little. Say you have the numbers from 1 to 100 in random order and choose 1 as the pivot, then you will still have an array with 99 elements to sort. The worst possible case is picking the first array element as the pivot if the array is already sorted.

gnasher729
  • 51,477
  • 5
  • 75
  • 98
1

Take a look at this question and answer.

There is a discussion showing that choosing a random pivot is probably the best choice in most scenarios.

marcelovca90
  • 2,673
  • 3
  • 27
  • 34
  • A random pivot is indeed a good choice. Anyway, it should only be used in versions that switch to an alternative algorithm for short subarrays. Otherwise the cost of random number generation can become a significant overhead. –  Aug 09 '16 at 15:45
  • I saw the question. In this simple scenario with an 7 elements array, is my technique good or not? I have updated the question with a last question. Please take a look. – lor Aug 09 '16 at 15:58
  • @YvesDaoust a cheap pseudo random would be fine. You could probably just use `count++ % array.length` – Bohemian Aug 09 '16 at 17:14
  • The % operator isn't cheap. –  Aug 09 '16 at 17:25