StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POHas anyone seen this improvement to quicksort before?
primarykey
Id
2105737
data
AcceptedAnswerId
0
AnswerCount
5
ClosedDate
CommentCount
5
CommunityOwnedDate
CreationDate
2010-01-20T23:06:25.080
FavoriteCount
22
LastActivityDate
2014-05-16T00:02:56.277
LastEditDate
2014-03-12T11:56:20.933
LastEditorUserId
114770
OwnerUserId
254617
ParentId
0
PostTypeId
1
Score
25
ViewCount
4988
LastEditorDisplayName
text
Body
<h2>Handling repeated elements in previous quicksorts</h2> I have found a way to handle repeated elements more efficiently in quicksort and would like to know if anyone has seen this done before. This method greatly reduces the overhead involved in checking for repeated elements which improves performance both with and without repeated elements. Typically, repeated elements are handled in a few different ways which I will first enumerate. First, there is the Dutch National Flag method which sort the array like <code>[ < pivot | == pivot | unsorted | > pivot]</code>. Second, there is the method of putting the equal elements to the far left during the sort and then moving them to the center the sort is <code>[ == pivot | < pivot | unsorted | > pivot]</code> and then after the sort the <code>==</code> elements are moved to the center. Third, the Bentley-McIlroy partitioning puts the <code>==</code> elements to both sides so the sort is <code>[ == pivot | < pivot | unsorted | > pivot | == pivot]</code> and then the <code>==</code> elements are moved to the middle. The last two methods are done in an attempt to reduce the overhead. <h2>My Method</h2> Now, let me explain how my method improves the quicksort by reducing the number of comparisons. I use two quicksort functions together rather than just one. The first function I will call <code>q1</code> and it sorts an array as <code>[ < pivot | unsorted | >= pivot]</code>. The second function I will call <code>q2</code> and it sorts the array as <code>[ <= pivot | unsorted | > pivot]</code>. Let's now look at the usage of these in tandem in order to improve the handling of repeated elements. First of all, we call <code>q1</code> to sort the whole array. It picks a pivot which we will further reference to as <code>pivot1</code> and then sorts around <code>pivot1</code>. Thus, our array is sorted to this point as <code>[ < pivot1 | >= pivot1 ]</code>. Then, for the <code>[ < pivot1]</code> partition, we send it to <code>q1</code> again, and that part is fairly normal so let's sort the other partition first. For the <code>[ >= pivot1]</code> partition, we send it to <code>q2</code>. <code>q2</code> choses a pivot, which we will reference to as <code>pivot2</code> from within this sub-array and sorts it into <code>[ <= pivot2 | > pivot2]</code>. If we look now at the entire array, our sorting looks like <code>[ < pivot1 | >= pivot1 and <= pivot2 | > pivot2]</code>. This looks very much like a dual-pivot quicksort. Now, let's return to the subarray inside of <code>q2</code> (<code>[ <= pivot2 | > pivot2]</code>). For the <code>[ > pivot2]</code> partition, we just send it back to <code>q1</code> which is not very interesting. For the <code>[ <= pivot2]</code> partition, we first check if <code>pivot1 == pivot2</code>. If they are equal, then this partition is already sorted because they are all equal elements! If the pivots aren't equal, then we just send this partition to <code>q2</code> again which picks a pivot (further <code>pivot3</code>), sorts, and if <code>pivot3 == pivot1</code>, then it does not have to sort the <code>[ <= pivot 3]</code> and so on. Hopefully, you get the point by now. The improvement with this technique is that equal elements are handled without having to check if each element is also equal to the pivots. In other words, it uses less comparisons. There is one other possible improvement that I have not tried yet which is to check in <code>qs2</code> if the size of the <code>[ <= pivot2]</code> partition is rather large (or the <code>[> pivot2]</code> partition is very small) in comparison to the size of its total subarray and then to do a more standard check for repeated elements in that case (one of the methods listed above). <h2>Source Code</h2> Here are two very simplified <code>qs1</code> and <code>qs2</code> functions. They use the Sedgewick converging pointers method of sorting. They can obviously can be very optimized (they choose pivots extremely poorly for instance), but this is just to show the idea. My own implementation is longer, faster and much harder to read so let's start with this: <pre><code>// qs sorts into [ = p ] void qs1(int a[], long left, long right){ // Pick a pivot and set up some indicies int pivot = a[right], temp; long i = left - 1, j = right; // do the sort for(;;){ while(a[++i] < pivot); while(a[--j] >= pivot) if(i == j) break; if(i >= j) break; temp = a[i]; a[i] = a[j]; a[j] = temp; } // Put the pivot in the correct spot temp = a[i]; a[i] = a[right]; a[right] = temp; // send the [ = p] partition to qs2 if( right > i + 1) qs2(a, i + 1, right); } void qs2(int a[], long left, long right){ // Pick a pivot and set up some indicies int pivot = a[left], temp; long i = left, j = right + 1; // do the sort for(;;){ while(a[--j] > pivot); while(a[++i] <= pivot) if(i == j) break; if(i >= j) break; temp = a[i]; a[i] = a[j]; a[j] = temp; } // Put the pivot in the correct spot temp = a[j]; a[j] = a[left]; a[left] = temp; // Send the [ > p ] partition to qs1 if( right > j + 1) qs1(a, j + 1, right); // Here is where we check the pivots. // a[left-1] is the other pivot we need to compare with. // This handles the repeated elements. if(pivot != a[left-1]) // since the pivots don't match, we pass [ <= p ] on to qs2 if(left < j - 1) qs2(a, left, j - 1); } </code></pre> I know that this is a rather simple idea, but it gives a pretty significant improvement in runtime when I add in the standard quicksort improvements (median-of-3 pivot choosing, and insertion sort for small array for a start). If you are going to test using this code, only do it on random data because of the poor pivot choosing (or improve the pivot choice). To use this sort you would call: <pre><code>qs1(array,0,indexofendofarray); </code></pre> <h2>Some Benchmarks</h2> If you want to know just how fast it is, here is a little bit of data for starters. This uses my optimized version, not the one given above. However, the one given above is still much closer in time to the dual-pivot quicksort than the <code>std::sort</code> time. On highly random data with 2,000,000 elements, I get these times (from sorting several consecutive datasets): <pre><code>std::sort - 1.609 seconds dual-pivot quicksort - 1.25 seconds qs1/qs2 - 1.172 seconds </code></pre> Where <code>std::sort</code> is the C++ Standard Library sort, the dual-pivot quicksort is one that came out several months ago by Vladimir Yaroslavskiy, and <code>qs1/qs2</code> is my quicksort implementation. On much less random data. with 2,000,000 elements and generated with <code>rand() % 1000</code> (which means that each element has roughly 2000 copies) the times are: <pre><code>std::sort - 0.468 seconds dual-pivot quicksort - 0.438 seconds qs1/qs2 - 0.407 seconds </code></pre> There are some instances where the dual-pivot quicksort wins out and I do realize that the dual-pivot quicksort could be optimized more, but the same could be safely stated for my quicksort. <h2>Has anyone seen this before?</h2> I know this is a long question/explanation, but have any of you seen this improvement before? If so, then why isn't it being used?
Tags
<c++><algorithm><sorting><quicksort>
Title
Has anyone seen this improvement to quicksort before?
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. USAndy
UserOwnerUserId
1. USJustin Peel
plurals
PostLinksPostIdRelatedPostId
1. PL
 singulars
 LinkTypeLinkTypeId
 LTLinked
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
2. PO
 singulars
 PostTypePostTypeId
 PTAnswer
3. PO
 singulars
 PostTypePostTypeId
 PTAnswer
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 POHas anyone seen this improvement to quicksort before?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 POHas anyone seen this improvement to quicksort before?
 UserUserId
 USoggy
 VoteTypeVoteTypeId
 VTFavorite
3. VO
 singulars
 PostPostId
 POHas anyone seen this improvement to quicksort before?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTDownMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.