"Beating" the linux standard quicksort (glibc) Thu, Nov 17. 2011
Trackbacks
Trackback specific URI for this entry
No Trackbacks
inline void swap(int* p1, int* p2) {
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
inline int divide(int* start, int* end, int pivotIndex) {
int len = end - start + 1;
int pivot = start[pivotIndex];
int storeIndex = 0;
swap(&start[pivotIndex], &start[len-1]);
for (int i=0; i < len-1; i++) {
if (start[i] < pivot) {
swap(&start[i], &start[storeIndex++]);
}
}
swap(&start[storeIndex], &start[len-1]);
return storeIndex;
}
inline void mysort(int* start, int* end) {
int len = end - start + 1;
if (start >= end || len == 1) {
return;
}
int pivotIndex = rand() % len;
int newPivotIndex = divide(start, end, pivotIndex);
mysort(&start[0], &start[newPivotIndex-1]);
mysort(&start[newPivotIndex+1], end);
}
Sorting 57 MB
My sort: 3694 msec
Quicksort: 5861 msec
Intel(R) Pentium(R) D CPU 3.00GHz (Presler)
2GB RAM
Linux 2.6.32-5-amd64 x86_64 GNU/Linux
g++ (Debian 4.4.5-8) 4.4.5
glibc 2.11.2
#1 - Magnus 2011-12-13 03:52 - (Reply)
That's C, not C++ . C++ would use a function object or roll the comparison into a template. Both would inline the comparison.
How does the C++ STL version compare against Windows? They would both drop down to insertion sort when the number of elements in the split arrays gets into single digits to save the recursive function call overhead.
#2 - Magnus 2011-12-16 06:13 - (Reply)
Also, do you have access to a C++11 compiler? I'd like to know how fast it is with a lambda compare.
#2.1 - Amanjit Singh Gill 2011-12-26 20:42 - (Reply)
Hi,
Thank you for your comments
You are absolutely right. Every method that allows the compiler to take a glimpse at the actual comparison is bound to be able to achieve comparable results. First of all, of course, std::sort.
But then again I just liked the entry of the blog entry
WRT to MSCV10, I will just have to investigate - MSVC has the reputation of replacing complete C standard library code... the compiler completely replaced memcpy with suitable optimized assembly code, f.e. ...
Sorry for my late reply,
have a nice one
#3 - nj 2012-01-27 14:28 - (Reply)
hello
i saw your avl C++ implementation in http://www.epsilon-delta.net/ but when i run your code with Dev-C++ it has the error below:
[Linker error]undefined reference to 'WinMain@16'
how can i solve this error? please send your answer to my email if you can.
thanks for attention
#3.1 - Amanjit Singh Gill 2012-01-28 15:49 - (Reply)
Hi,
DevCpp is probably not the best choice for c++ and windows, you should use the Visual Studio C++ express edition or qt sdk
bye
![]() |
May '22 | |||||
Mo | Tu | We | Th | Fr | Sa | Su |
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
© 2010 Amanjit Singh Gill (amanjit.gill@gmx.de) | About this site | Contact | RSS | Back to top
Design by Andreas Viklund | Serendipity Template by Carl