Timeline for Comparing pivot choosing methods in quicksort
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 27, 2016 at 6:33 | comment | added | Celeritas |
Does it matter which order the 3 swaps are done for sorting the elements used for the median? For example, I think if(arr[middle] > arr[end]); if(arr[beginning] > arr[middle]); if(arr[beginning] > arr[end]); works too, even though the middle is checked first.
|
|
| Jul 11, 2014 at 23:49 | vote | accept | Celeritas | ||
| Jul 11, 2014 at 23:28 | comment | added | David Harkness | @Celeritas It should go without saying that you cannot use "median of three" for lists with less than three elements. | |
| Jul 11, 2014 at 22:26 | comment | added | Celeritas |
@DavidHarkness Important to note this way of choosing the pivot cannot be used for the entire array. For arrays of size 2 it leads to a stackoverflow error because rhtPtr is always greater than lftPtr. For arrays of size 1 there is an out of bounds error as rhtPtr's index is shifted one to the left which doesn't exist in arrays of size 1.
|
|
| Jul 11, 2014 at 20:57 | comment | added | David Harkness | @Celeritas Not sure I follow. It probably needs to return the index that divides the two partitions. | |
| Jul 11, 2014 at 18:31 | comment | added | Celeritas | Ok thanks. Does it make a difference if the lftPtr or rhtPtr is returned from the partitioning method? | |
| Jul 10, 2014 at 22:15 | comment | added | David Harkness | @Celeritas That's correct. I assumed it was doing that since without it, there's no point in swapping the pivot to the second-to-last position. It would get swapped by the partition step. So absolutely initialize the pointers as you have in your comment. | |
| Jul 10, 2014 at 18:43 | comment | added | Celeritas |
@DavidHarkness so we have the array (A,.....B,C) where A<=B<=C. Here they initialize leftPtr = left; rightPtr = right - 1; can't you have leftPtr = left + 1 since you know that the first element is less than the pivot and rightPtr = right - 2 since the second last element is the pivot itself and there's no point in comparing it to itself? Wouldn't this save a couple more iterations?
|
|
| Jul 8, 2014 at 23:32 | history | edited | David Harkness | CC BY-SA 3.0 |
explained the final swap
|
| Jul 8, 2014 at 23:23 | comment | added | David Harkness |
@Celeritas According to the code you posted--swap(arr, middle, end-1);--the pivot (at middle) gets moved to the second-to-last slot. This would be used when partitioning with if (arr[i] < pivot) { /* move to 1st partition */ }. If you use <= instead, you'd swap the pivot to the 2nd position with swap(arr, middle, beginning + 1);. I'll update my answer to make this clearer.
|
|
| Jul 8, 2014 at 22:42 | comment | added | Celeritas | What do you mean the pivot is always moved to the second partition? For example (2,9,7,5,4)=>(2,9,4,5,7) with 4 as pivot. 9 and 4 get swapped => (2,4,9,5,7) so 4 is left of where it started and I call that the first partition. | |
| Jul 8, 2014 at 22:19 | comment | added | David Harkness | @Celeritas It's a micro-optimization. Because the center (median) element becomes the pivot, it will always be moved to the second partition. This swap makes it explicit and avoids the comparison and one iteration during the partition step. | |
| Jul 8, 2014 at 21:35 | comment | added | Celeritas |
I still don't understand the part about swap(arr, middle, end-1); in medianOf3?
|
|
| Jul 8, 2014 at 20:20 | comment | added | David Harkness | @rolfl Hehe, don't you hate that? You're almost done with your awesome answer when someone swoops in and submits theirs first. | |
| Jul 8, 2014 at 20:16 | comment | added | rolfl | Posted mine just to prove it was done! .... nice answer ;-) | |
| Jul 8, 2014 at 20:13 | history | answered | David Harkness | CC BY-SA 3.0 |