# Sort 5 objects with 7 comparisons

9 replies to this topic

### #1Mihail121

Senior Member

• Members
• 1059 posts

Posted 16 June 2007 - 01:39 PM

Hi!

Do you think it's possible to sort 5 objects with 7 comparisons? I'm doing a small research project where I use 5 parallel clipping planes, which need to be sorted. I define an order by taking the distance to the user. I know it's possible with 8, but each operation is important, since we're extremely low-level.

Thank you!

### #2Reedbeta

DevMaster Staff

• 5344 posts
• LocationSanta Clara, CA

Posted 16 June 2007 - 03:22 PM

Is there any way to take advantage of temporal coherence? For instance, is it possible to start with the order from last frame and just update it to get the order for the current frame?
reedbeta.com - developer blog, OpenGL demos, and other projects

### #3Mihail121

Senior Member

• Members
• 1059 posts

Posted 16 June 2007 - 03:48 PM

Unfortunately no, we thought about that strategy though.

### #4dave_

Senior Member

• Members
• 584 posts

Posted 16 June 2007 - 06:18 PM

... I'm not sure about the implementation but I quickly knocked this up:

#include <iostream>
#include <vector>
#include <algorithm>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <Windows.h>

unsigned compares=0;

struct SomeSortable {
SomeSortable() : v(rand()) {}

bool operator <(const SomeSortable& rhs) const { ++compares; return v < rhs.v; }
bool operator >(const SomeSortable& rhs) const { return v > rhs.v; }

unsigned v;
};

template<typename T>
bool is_sorted(T start, T end)
{
for(T itt = start; itt != end; ++itt)
{
if (itt > itt+1)
return false;
}
return true;
}

int main(int argc, char *argv[])
{
time_t t;
time(&t);
srand((unsigned int)t);

std::vector<SomeSortable> sort1;

const unsigned num_iterations = 100000;

DWORD start;
start = GetTickCount();
for (unsigned j = 0; j < num_iterations; ++j)
{
for (unsigned i = 0; i < 5; ++i)
{
sort1.push_back(SomeSortable());
}
std::sort(sort1.begin(), sort1.end());

bool sorted = is_sorted(sort1.begin(), sort1.end());
assert(sorted);
sort1.clear();
}
DWORD end;
end = GetTickCount();

std::cout << "std::sort number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

compares = 0;
start = GetTickCount();
for (unsigned j = 0; j < num_iterations; ++j)
{
for (unsigned i = 0; i < 5; ++i)
{
sort1.push_back(SomeSortable());
}
std::stable_sort(sort1.begin(), sort1.end());

bool sorted = is_sorted(sort1.begin(), sort1.end());
assert(sorted);
sort1.clear();
}

end = GetTickCount();
std::cout << "std::stable_sort number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

compares = 0;
start = GetTickCount();
for (unsigned j = 0; j < num_iterations; ++j)
{
for (unsigned i = 0; i < 5; ++i)
{
sort1.push_back(SomeSortable());
}
std::sort_heap(sort1.begin(), sort1.end());

bool sorted = is_sorted(sort1.begin(), sort1.end());
assert(sorted);
sort1.clear();
}

end = GetTickCount();
std::cout << "std::sort_heap number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

return 0;
}


std::sort number of comparisons 9 duration 4047
std::stable_sort number of comparisons 8 duration 4344
std::sort_heap number of comparisons 5 duration 4016


### #5Mihail121

Senior Member

• Members
• 1059 posts

Posted 16 June 2007 - 06:31 PM

Ehm Dave, there is most probably an error in your code. There is no sorting algorithm, that can sort 5 comparable objects with 5 comparisons, since the lower bound of the amount of comparisons for the worst case (n objects) should be greater equal log2 (n!) . In our case that's 7.

### #6dave_

Senior Member

• Members
• 584 posts

Posted 16 June 2007 - 07:25 PM

Heapsort has a worst case complexity of O(n log n) that should be 11.61 so I've no idea where the error is.

Edit figured it out. I wasn't dereferencing the iterators and I also forgot a make heap. That doubles the comparisons. :(
Corrected results, with more iterations
std::sort number of comparisons 9 duration 20875
std::stable_sort number of comparisons 8 duration 21266
std::sort_heap number of comparisons 10 duration 22688


### #7dave_

Senior Member

• Members
• 584 posts

Posted 16 June 2007 - 11:07 PM

Since they're parallel planes is it possible to sort them by 'd' first to gain some advantage?
What about caching normal . eye?
Edit: Though about it a bit more.
comparison is normal1 . eye + d1 < normal2 . eye + d2
since plane1 & plane2 are parallel normal1 == normal2
can you simplify this to just d1 < d2?
Have you already done this optimization? Is it even valid?
#include <iostream>
#include <vector>
#include <algorithm>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <Windows.h>

unsigned compares=0;

float eyex = 1.0f, eyey = 12.433f, eyez = -100.f;
struct SomeSortable {
SomeSortable() : x_(0.58f), y_(0.58f), z_(0.58f), d_((rand() % 1000)*1.f) {}

float distanceToEye() const
{
float dot = x_ * eyex
+ y_ * eyey
+ z_ * eyez;
return dot + d_;

}
bool operator<(SomeSortable const& rhs) const
{
++compares;
return distanceToEye() < rhs.distanceToEye();
}
bool operator>(SomeSortable const& rhs) const
{
return distanceToEye() > rhs.distanceToEye();
}

float x_, y_, z_, d_;
};

template<typename T>
bool is_sorted(T start, T end)
{
for(T itt = start; itt != end-1; ++itt)
{
if (*itt > *(itt+1))
return false;
}
return true;
}

struct Sorter
{
Sorter() {}
bool operator()(SomeSortable const& lhs, SomeSortable const& rhs) const
{
++compares;
return lhs.d_ < rhs.d_;
}

};

int main(int argc, char *argv[])
{
time_t t;
time(&t);
srand((unsigned int)t);

std::vector<SomeSortable> sort1;

const unsigned num_iterations = 100000;

DWORD start;
start = GetTickCount();
for (unsigned j = 0; j < num_iterations; ++j)
{
for (unsigned i = 0; i < 5; ++i)
{
sort1.push_back(SomeSortable());
}
std::sort(sort1.begin(), sort1.end());

bool sorted = is_sorted(sort1.begin(), sort1.end());
assert(sorted);
sort1.clear();
}
DWORD end;
end = GetTickCount();

std::cout << "std::sort number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

compares = 0;
start = GetTickCount();
for (unsigned j = 0; j < num_iterations; ++j)
{
for (unsigned i = 0; i < 5; ++i)
{
sort1.push_back(SomeSortable());
}
std::stable_sort(sort1.begin(), sort1.end());

bool sorted = is_sorted(sort1.begin(), sort1.end());
assert(sorted);
sort1.clear();
}

end = GetTickCount();
std::cout << "std::stable_sort number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

compares = 0;
start = GetTickCount();
for (unsigned j = 0; j < num_iterations; ++j)
{
for (unsigned i = 0; i < 5; ++i)
{
sort1.push_back(SomeSortable());
}
std::make_heap(sort1.begin(), sort1.end());
std::sort_heap(sort1.begin(), sort1.end());

bool sorted = is_sorted(sort1.begin(), sort1.end());
assert(sorted);
sort1.clear();
}

end = GetTickCount();
std::cout << "std::sort_heap number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

compares = 0;
start = GetTickCount();
for (unsigned j = 0; j < num_iterations; ++j)
{
for (unsigned i = 0; i < 5; ++i)
{
sort1.push_back(SomeSortable());
}

std::sort(sort1.begin(), sort1.end(), Sorter());

bool sorted = is_sorted(sort1.begin(), sort1.end());
assert(sorted);
sort1.clear();
}

end = GetTickCount();
std::cout << "dot sort number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

return 0;
}


### #8Nick

Senior Member

• Members
• 1227 posts

Posted 17 June 2007 - 08:57 AM

Mihail121 said:

I'm doing a small research project where I use 5 parallel clipping planes, which need to be sorted.
Could you give us a little hint at what you're trying to do? It sounds interesting, but I can't imagine anything where sorting 5 numbers is a performance bottleneck. And it's even weirder that there's no temporal/spacial coherence...

### #9Hyde

New Member

• Members
• 22 posts

Posted 12 July 2007 - 10:21 PM

I bet you can't avoid having to do 8 compares, given that you assume nothing.
0, 1/2, 2/3, 3/4, 4/5, ...

### #10SamuraiCrow

Senior Member

• Members
• 459 posts

Posted 13 July 2007 - 01:06 AM

The only way you can beat O(n log n) time with a sorting algorithm is if you can use the values themselves as an index and avoid the whole comparison-type sorting algorithms altogether. Eg. the radix sort.

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users