C++ boost::sort::pdqsort()
Description
Pattern-defeating quicksort (pdqsort) is a sorting algorithm that combines the fast average case of randomized quicksort with the fast worst case of heapsort.It can achieve linear time complexity on certain type of patterns.
Its usage is same as std::sort.
pdqsort has two forms -
1)pdqsort()
2)pdqsort_branchless()
1)pdqsort()
2)pdqsort_branchless()
Both are faster than std::sort. pdqsort_branchless runs significantly faster than pdqsort for comparison functions that are branchless such as simple integer comparisons.
Benchmark
( Time required to sort 1000000 32 bit integers )
OS: Windows
Processor: INTEL i3 6th gen
Memory: 4 GB
To know more about Benchmarking check out the article on C++ BENCHMARKING
Header
#include<boost/sort/pdqsort/pdqsort.hpp>
Syntax
1) void boost::sort::pdqsort(First Iterator ,Last Iterator)
2) void boost::sort::pdqsort(First Iterator ,Last Iterator ,Compare comp)
3) void boost::sort::pdqsort_branchless(First Iterator ,Last Iterator)
4) void boost::sort::pdqsort_branchless(First Iterator ,Last Iterator ,Compare comp)
#include<boost/sort/pdqsort/pdqsort.hpp>
Syntax
1) void boost::sort::pdqsort(First Iterator ,Last Iterator)
2) void boost::sort::pdqsort(First Iterator ,Last Iterator ,Compare comp)
3) void boost::sort::pdqsort_branchless(First Iterator ,Last Iterator)
4) void boost::sort::pdqsort_branchless(First Iterator ,Last Iterator ,Compare comp)
Implementation
#include<boost/sort/pdqsort/pdqsort.hpp>
#include<iostream>
using namespace std;
using namespace boost::sort; // using namespace so that we don't have to write it every time
bool comp(int a,int b) //compare function that can be passed to the pdqsort function.
{
return(a>b); // if a>b it sorts in descending order and if a<b it sorts in ascending order.
}
int main()
{
vector<int>a{3,5,2,1,6,9,10,11,0,1}; // taking a vector of few integers
cout<<"Sorting in ascending order without compare function --->"<<endl;
pdqsort(a.begin(),a.end());// a.begin() and a.end() are the first and last iterator of vector a
for(int i=0;i<a.size();i++)//printing the sorted array
cout<<a[i]<<" ";
cout<<endl;
cout<<"Sorting in descending order with compare function--->"<<endl;
pdqsort(a.begin(),a.end(),comp); // comp is the compare function
for(int i=0;i<a.size();i++)//printing the sorted array
cout<<a[i]<<" ";
cout<<endl;
// Now using the pdqsort_branchless function
cout<<" Now using pdqsort_branchless()----------------> "<<endl;
cout<<"Sorting in ascending order without compare function --->"<<endl;
pdqsort_branchless(a.begin(),a.end());
for(int i=0;i<a.size();i++)//printing the sorted array
cout<<a[i]<<" ";
cout<<endl;
cout<<"Sorting in descending order with compare function--->"<<endl;
pdqsort_branchless(a.begin(),a.end(),comp); // comp is the compare function
for(int i=0;i<a.size();i++)//printing the sorted array
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
Output
Comments