Radix sort struct by one variable

[VBNick]

hi, I'm using this bubble sort to sort the elements in my array right now, but I need something faster.

bSorted = false;
while(!bSorted)
{
	bSorted = true;
	for(int e = a_count - 2; e >= a_lbound; e--)
	{	
		if(a_edges[e + 1].B < a_edges[e].B)
		{
			bSorted = false;
			tmpEdge = a_edges[e];
			a_edges[e] = a_edges[e + 1];
			a_edges[e + 1] = tmpEdge;
		}
	}
}

I want to use a radix sort, but I'm not sure how to do it with anything but a list of numbers.

struct EDGE
{
	int poly;
	double inv_slope;
	int B;
	POINT3D p1, p2;
};

I want to sort this struct by "B", but there can be more than one instance with the same value for "B" and different value for "poly" for example. I can't then create an array of integers and add 1 to intarray[5] if "B" is 5, for this reason.

can someone point me in the right direction on how I would sort such a thing quickly?
thanks, Nicolas

[Ancient Dragon]

There are several ways to solve the problem. One way is to create a 64-bit int in the structure that represents both B and poly at the same time, which will result in unique values for each structure in the array. Your program could set that value just before inserting the structure into the array

struct EDGE
{
    int  poly;
    double inv_slope;
    int B;
    long long sortValue; 
            
POINT3D p1, p2;
};

...
sortValue = (long long)B << 32 | (long long)poly;

Now you can code radix sort by sorting the sortValue member variable.

[VBNick]

by using the long long variable, do you mean that it will work something like this?

long long MyVariable;
a = loword(MyVariable);
b = hiword(MyVariable);

if this is it, I still don't think that will work. I may have used the wrong term. "Bucket Sort" is what i meant.

I want to sort like this:

int arrayofB[SCREENWIDTH];
EDGE myedges[100];
EDGE sortededges[100];
for(int i = 0; i < 100; i++)
{
    arrayofB[myedges[i].B] += 1;
}
for(int i = 0; i < SCREENWIDTH; i++)
{
    for(int j = 0; j <= arrayofB[i]; j++)
    {
        //put edge with this B into the sorted array. "poly" is irretrievable =(
    }
}

below is a list of what might have to be sorted. If I used the above procedure, it would be impossile to retrieve the other values, like "poly" from the value of B after the list was sorted.

myedges[0]
  .poly = 0
  .inv_slope = 0.4933...
  .B = 12
  .P1
    .x = 45
    .y = 21
  .P2
    .x = 105
    .y = 347

myedges[1]
  .poly = 1
  .inv_slope = 0.535
  .B = 12
  .P1
    .x = 1
    .y = 4
  .P2
    .x = 189
    .y = 532

myedges[2]
  .poly = 0
  .inv_slope = 0.902
  .B = 34
  .P1
    .x = 262
    .y = 262
  .P2
    .x = 199
    .y = 541

myedges[3]
  .poly = 1
  .inv_slope = 0.1
  .B = 34
  .P1
    .x = 66
    .y = 93
  .P2
    .x = 799
    .y = 301

so if I were to sort for B, myedges[0] and myedged[2] would have to be put in the same cell, which wouldnt allow me to get the poly number from B.

thanks again for the help =)

[Ancient Dragon]

you would leave B and poly as they are, just add another long long variable for sorting purposes. When two structs have the same B value the long long will auto sort by poly. This is similar to the approach databases use when more than one field are needed to create a unique key.

[VBNick]

Ok, this is kinda cool. I looked it up and came up with this:

#include "stdafx.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
	long long myVal;
	int B = 438;
	int poly = 45;
	int lo_word;
	int hi_word;
	myVal = (long long)B << 32 | (long long)poly;
	lo_word = (myVal / 0x10000) & 0xFFFF;
	hi_word = myVal & 0xFFFF;
	cout << lo_word << " " << hi_word << endl;
	
	return 0;
}

but it returns 0 and 45. I don't understand why it gets one and not the other.
I also tried it with this and got the same result:
#include "windows.h"
LOWORD(myVal)
HIWORD(myVal)

may I please have the last piece to my puzzle?
Thanks ;)

[ArkM]

Some additions.
I think a radix sort is not a suitable method to sort array of structures with sort key fields. You need a lots of additional memory and unnatural code modifications.

Probably the simplest way to adopt common sort codes (usually published with int array parameter) for structures sorting in C++ is to define a proper compare operator.

For example, let's adopt sort codes from the excellent tutorial:
http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_sorting.aspx
Get selection and Shell sort algorithmes. The selection sort is a good method for a fast compare operation but relatively slow data movement case (typical for struct sorting). However it's a slow method suitable for short arrays only. That's why the second example is a Shell sort - relatively fast with a very simple implementation.

struct POINT3D { double x, y, z; };

struct Edge { // I don't like all-capital names ;)
    int poly;
    double inv_slope;
    int b;
    POINT3D p1, p2;
};

inline // see compound key handling
bool operator>(const Edge& e1, const Edge& e2) {
    return e1.b > e2.b
        || e1.b == e2.b && e1.poly > e2.poly;
}

void SelectionSort(Edge a[], int n )
{
    int maxi;
    Edge w;

    while (--n > 0) {
        maxi = n;
        for (int i = 0; i < n; ++i)
            if (a[i] > a[maxi])
                maxi = i;
        if (maxi != n) { // swap
            w = a[n];
            a[n] = a[maxi];
            a[maxi] = w;
        }
    }
}

void ShellSort(Edge a[], int n )
{
    int i, h = 1;

    while ( h <= n / 9 )
        h = 3 * h + 1;

    while ( h > 0 ) {
        for ( i = h; i < n; i++ ) {
          int j;
          Edge save = a[i];

          for ( j = i; j >= h && a[j - h] > save; j -= h )
            a[j] = a[j - h];

          a[j] = save;
        }
        h /= 3;
    }
}

The only correction needed was a simple redeclaration of temporary variables as a structure type, not int.

For Edge[10] arrays SelectionSort works ~4 microseconds and ShellSort ~3 microseconds. Obviously, for Edge[100] Shell sort is much more faster than SelectionSort.

Don't use this approach for large structures directly. If it's possible better create and fill an array of pointers to all structure elements and sort this array (avoid data moving at all). It's the other story how to adopt common sort codes in that case...

[VBNick]

Thanks to everyone for the suggestions. I'm starting to get the idea of what I need to do. ArkM, I guess I should have also mentioned that this is a 3D rendering program. I plan on doing Depth-Field Rendering, which would potentially require me run this sort 1000s of times per frame. While scanning the screen from left to right for every row, I will need to calculate which of the edges has the topmost Z. So I need to use the absolute fastest sorting method I can. I don't understand how anything could be faster than the bucket sort for this application.
anyways, I was thinking about what Ancient Dragon was saying, and it is a good idea, but if I wanted to declare the array of "Buckets", to work properly with a 64-bit long, wouldn't it have look something like this?

long long unsorted_edges[18446744073709551616]?

running through that many numbers over and over could get Reallllly slow couldn't it?
I mean...if this methodd:
myVal = (long long)B << 32 | (long long)poly;
could yield a number between 0 and 18446744073709551616, then I would need that many buckets woudlnt I?
C++ gives error : unknown size

[ArkM]

If you need fast sorting, think about another approach: keep your data sorted - for example, maintain balanced tree with nodes pointing to data structures.

[VBNick]

Hi, thanks again for the help, but I'm still a little foggy on how exactly I can sort what I need in the fastest possible way. I have also found that I am going about this certain part of my app the hard way as well, so I wont know exactly what I'm dealing with until its all together right. BUT! I did find an HUGE amount of sorting tutorials specifically for games at www.gamedev.net in their "resources" section that will be much easier to understand since they were written for this specific application.
Thanks again, Nick