Q: While working on the challenge, I came across something strange with the recursion calls and how to use the pivot point, `q`. Here is my quickSort function so far: ``` `var quickSort = function(array, p, r) { if (2 <= r-p) { var q = partition(array, p, r); quickSort(array, p, q-1); quickSort(array, q, r); } };` ```The above code produces the correct output but is not accepted by the grader. If I change the quickSort recursion calls to the example below: ``` ` quickSort(array, p, q-1); quickSort(array, q+1, r);` ```The wrong output is produced because there is an index in the array not being included in the sorting process. Now, I change it to this: ``` ` quickSort(array, p, q); quickSort(array, q+1, r);` ```And I get an Oh Noes message that tells me there is an "InternalError: too much recursion". Why is this happening? How should I get past this issue?

Hey, so you have this almost right. Your error, I believe, is stemming from your if statement, but your second edit of the quickSort calls is also the correct call. If statement should be: ```if ( p < r ) ``` This ensure that the array is of adequate length, because if the array is 1 or zero, p would either equal r or not exist. Your quickSort calls should be: ```quickSort(array, p, q-1); quickSort(array, q+1, r);``` The partition places the pivot in the correct spot and returns the index. You then use the pivot index to sort the two remaining arrays, and since the pivot is already "sorted" you just sort the subarrays to indexes one below and one above the pivot. Once all the recursion occurs, everything is sorted in place and it should return the whole array sorted.

Q: In the Challenge, Implement quicksort, I played with ( < ); until I got it to work with (p < r), which I really do not understand. Can someone please explain why it works? Thanx.d

"The quickSort function should recursively sort the subarray array[p..r]." If p = r then you have a one element array that is, by definition, already sorted. So, you only need to sort subarrays that have more than one element. How many elements does array[p..r] have ? It has r-p+1 elements. So we need to sort when r-p+1 > 1 Which is equivalent to: r-p > 0, r > p, p < r, etc.

Q: So this algorithm basically splits it in half, the halves are bigger/smaller than the middle one, then you sort them and put them together?

That's the basic idea. However, we don't really know which element is the "middle one", so we just pick an element. As a result, the smaller and bigger chunks may not be the same size. That is, we may not actually be splitting the array in half. If the data is randomly ordered it works pretty well i.e. the big and small chunks will be close to the same size. However, on already sorted data, it can fail miserably, as one chunk can have 1 element while the other chunk has the rest.

Q: No matter what I do, it always says maximum call stack exceeded. I don't understand how we can evaluate subarrays, because we have not had the pivot yet

If you are getting max call stack exceeded, i.e. a stack overflow, it is likely because your recursion is not reaching the base case. Instead it is infinitely calling itself, kind of like an infinite loop. Make sure your base case is set up right, and that your recursion makes the problem smaller each call. To debug, try printing out the parameters that the function was called with at the top of the function.

Q: array[p..r] What symbolic mearning do the letters p and r have here, what are they referring to?

p is the leftmost index of the subarray r is the rightmost index of the subarray q is the index of the pivot (after the subarray has been partitioned)

Q: How many comparisons in total were there in the example?

I believe that there are a total of 20 comparisons made in the example.

Question 1

Why select the right element as the pivot? Why not the median of three method, which is supposed to do it better?

Accepted Answer

Pivot selection is an important part of quick sort and there are many techniques, all with pros and cons.

*Why does the pivot matter* ?
On average quick sort runs in O(n log n) but if it consistently chooses bad pivots its performance degrades to O(n^2)
This happens if the pivot is consistently chosen so that all (or too many of) the elements in the array are < the pivot or > than the pivot.
(A classic case is when the first or last element is chosen as a pivot and the data is already sorted, or nearly sorted)

*What are some techniques to choose a pivot* ?

Choose the left most or rightmost element. 
Pros: Simple to code, fast to calculate
Cons: If the data is sorted or nearly sorted, quick sort will degrade to O(n^2)

Choose the middle element:
Pros: Simple to code, fast to calculate, but slightly slower than the above methods
Cons: Still can degrade to O(n^2). Easy for someone to construct an array that will cause it to degrade to O(n^2)

Choose the median of three:
Pros: Fairly simple to code, reasonably fast to calculate, but slightly slower than the above methods
Cons: Still can degrade to O(n^2). Fairly easy for someone to construct an array that will cause it to degrade to O(n^2)

Choose the pivot randomly (using built in random function):
Pros: Simple to code. Harder for someone to construct an array that will cause it to degrade to O(n^2)
Cons: Selecting a random pivot is fairly slow. Still can degrade to O(n^2).

Choose the pivot randomly (using a custom built random function):
Pros: Much harder for someone to construct an array that will cause it to degrade to O(n^2), if they don't know how you are choosing the random numbers.
Cons: May be complicated to code. Selecting a random pivot is fairly slow. Still theoretically possible that it can degrade to O(n^2).

Use the median of medians method to select a pivot
Pros: The pivot is guaranteed to be good. Quick sort is now O(n log n) worst case !
Cons: Complicated code. Typically, a lot slower than the above methods.

*Which method should I use* ?

-If it is unlikely that the data will be sorted, and you are willing to accept O(n^2) in the rare cases when the array is sorted then use the leftmost or rightmost element.
-If there is a reasonable chance your data is sorted use the middle element or median of threes.
-If you are somewhat worried about malicious users giving you bad arrays to sort (used as a Denial of Service attack) then use random pivots.
-If you are really worried about malicious users or you need to guarantee that the quicksort runs is O(n log n) then use the median of medians. At this point you may want to seriously consider using a different sorting method like merge sort.

Hope this makes sense

Question 2

The second paragraph says, "constant factor hidden in the big-Θ notation for quicksort is quite good"
can someone tell me what is this hidden constant factor. Is it do with the time it takes to partition versus the time it takes to merge in merge sort.

Accepted Answer

Here's what they are talking about:
Both merge sort and quicksort are Θ(n log n) algorithms (for the average case).
So quicksort's running time will be ~k1 * n log n and merge sort's running time will be ~k2 * n log n (for the average case). When they are talking about the  "constant factor"s, they are talking about k1 and k2. The values of k1 and k2 depend on the implementation of the algorithms, the computer used etc.  In practice, if you ran quick sort and merge sort on the same computer, you would find that k1 is  much smaller than k2.

Hope this makes sense

Question 3

While working on the challenge, I came across something strange with the recursion calls and how to use the pivot point, `q`. Here is my quickSort function so far:
```
`var quickSort = function(array, p, r) {
    if (2 <= r-p) {
        var q = partition(array, p, r);
        quickSort(array, p, q-1);
        quickSort(array, q, r);
    }
};`
```The above code produces the correct output but is not accepted by the grader. 
If I change the quickSort recursion calls to the example below:
```
`        quickSort(array, p, q-1);
        quickSort(array, q+1, r);`
```The wrong output is produced because there is an index in the array not being included in the sorting process. 
Now, I change it to this:
```
`        quickSort(array, p, q);
        quickSort(array, q+1, r);`
```And I get an Oh Noes message that tells me there is an "InternalError: too much recursion". Why is this happening? How should I get past this issue?

Accepted Answer

Hey, so you have this almost right. Your error, I believe, is stemming from your if statement, but your second edit of the quickSort calls is also the correct call.

If statement should be:
```if ( p < r ) ```
This ensure that the array is of adequate length, because if the array is 1 or zero, p would either equal r or not exist.

Your quickSort calls should be:
```quickSort(array, p, q-1);
   quickSort(array, q+1, r);```
The partition places the pivot in the correct spot and returns the index. You then use the pivot index to sort the two remaining arrays, and since the pivot is already "sorted" you just sort the subarrays to indexes one below and one above the pivot. Once all the recursion occurs, everything is sorted in place and it should return the whole array sorted.

Question 4

In the Challenge, Implement quicksort, I played with ( < ); until I got it to work with (p < r), which I really do not understand. Can someone please explain why it works? Thanx.d

Accepted Answer

"The quickSort function should recursively sort the subarray array[p..r]."
If p = r then you have a one element array that is, by definition, already sorted. So, you only need to sort subarrays that have more than one element.

How many elements does array[p..r] have ?
It has r-p+1 elements.
So we need to sort when r-p+1 > 1
Which is equivalent to:
r-p > 0,
r > p,
p < r,
etc.

Question 5

So this algorithm basically splits it in half, the halves are bigger/smaller than the middle one, then you sort them and put them together?

Accepted Answer

That's the basic idea.

However, we don't really know which element is the "middle one", so we just pick an element. As a result, the smaller and bigger chunks may not be the same size. That is, we may not actually be splitting the array in half.

If the data is randomly ordered it works pretty well i.e. the big and small chunks will be close to the same size. However, on already sorted data, it can fail miserably, as one chunk can have 1 element while the other chunk has the rest.

Question 6

No matter what I do, it always says maximum call stack exceeded. I don't understand how we can evaluate subarrays, because we have not had the pivot yet

Accepted Answer

If you are getting max call stack exceeded, i.e. a stack overflow, it is likely because your recursion is not reaching the base case. Instead it is infinitely calling itself, kind of like an infinite loop.

Make sure your base case is set up right, and that your recursion makes the problem smaller each call. To debug, try printing out the parameters that the function was called with at the top of the function.

Question 7

array[p..r]

What symbolic mearning do the letters p and r have here, what are they referring to?

Accepted Answer

p is the leftmost index of the subarray
r is the rightmost index of the subarray
q is the index of the pivot (after the subarray has been partitioned)

Question 8

How many comparisons in total were there in the example?

Accepted Answer

I believe that there are a total of 20 comparisons made in the example.

Course: Computer science theory > Unit 1

Overview of quicksort

Want to join the conversation?