Sorting algorithm

Math and Physics Programming

Started by ProblemBaby October 23, 2004 09:34 AM

29 comments, last by snk_kid 19 years, 5 months ago

1,596

October 23, 2004 03:28 PM

Quote:Original post by Eelco
too optimisitc?

the only memeory required is simply:

one buffer to copy the data to: linear and insignificant for the reason that any realtime sortable dataset will always be << available memory.
+
2 lookuptables with memory requirement that were already laugable in the 80's

Yes, that could have been me being dumb, too.

Blog — Facebook

ProblemBaby

122

Author

October 23, 2004 07:11 PM

for (int n = 0; n < 10; n++)
{
for (int m = n+1; m < 10; m++)
{
if (data[data[n].nIndex].nValue < data[data[m].nIndex].nValue)
{
index = data[n].nIndex;
data[n].nIndex = data[m].nIndex;
data[m].nIndex = index;
}
}
}

This didnt work, why?

Problems every where

LilBudyWizer

491

October 24, 2004 12:37 AM

Well, your comparision is backwards assuming you want ascending order. More likely it is because your values are not in order. They don't move, just the indices move. So to actually display the list in order you have to use data[data[n].nIndex].nValue.

Keys to success: Ability, ambition and opportunity.

Ajare

174

October 24, 2004 06:12 AM

Plus, it should be:

for (int n = 0; n < (10 - 1); n ++)
{
for (int m = n; m < (10 - 1) - n; m ++)
{

at the beginning. But that's about the slowest sort you can do, I would use one of the ones already suggested in the thread if you plan to sort much more....

ProblemBaby

122

Author

October 24, 2004 06:22 AM

It will max be 32

Problems every where

ProblemBaby

122

Author

October 24, 2004 06:28 AM

But I cant understand why it doesnt work, here is the case:

data[0].nValue = 29; // index 0
data[1].nValue = 9; // index 1
data[2].nValue = 12;// index 2
data[3].nValue = 39;// index 3
data[4].nValue = 26;// index 4

for (int n = 0; n < 5-1; n++)
{
for (int m = n; m < (5-1)-n; m++)
{
if (data[data[n].nIndex].nValue < data[data[m].nIndex].nValue)
{
index = data[n].nIndex;
data[n].nIndex = data[m].nIndex;
data[m].nIndex = index;
}
}
}

Result:
data[0].nValue = 29; // index 3
data[1].nValue = 9; // index 2
data[2].nValue = 12;// index 1
data[3].nValue = 39;// index 0
data[4].nValue = 26;// index 4

I want it to be...

data[0].nValue = 29; // index 1
data[1].nValue = 9; // index 4
data[2].nValue = 12;// index 3
data[3].nValue = 39;// index 0
data[4].nValue = 26;// index 2

Problems every where

Ajare

174

October 24, 2004 07:16 AM

[sorry, there was a typo in my previous code]

If you want to keep the order of the array elements, you're going to need some way of tracking where they've moved to when sorted. If you don't mind them moving (and I see no reason why they shouldn't, unless you're hard-referencing them from somewhere else), then try this:

int temp;for (int n = 0; n < 5-1; n++){  for (int m = 0; m < (5-1)-n; m++)  {    if (data[m].nValue < data[m + 1].nValue)    {      temp = data[m].nValue;      data[m].nValue = data[m + 1].nValue;      data[m + 1].nValue = temp;    }  }}for (n = 0; n < 5; n ++)  data[n].nIndex = n;

ProblemBaby

122

Author

October 24, 2004 07:37 AM

In fact that is what I do.
This should be implented in a Game iam workin on for GBA.

nValue = z
nIndex = ObjectIndex

it is 128 possible objects in the hardware
and the lower index the higher priority

so Ive to see which one has the greatest nValue and then give it nIndex = 0 etc..

Problems every where

Inmate2993

222

October 24, 2004 03:03 PM

Just to beat a dead horse, we seem to be talking about the "Insertion Sort", which as a simplified form:

for ( y=0; y<(max-1); y++ ){  indice = y;  for ( x=(y+1); x<max; x++ )  {    if (array[x] < array[indice]) indice=x;  }  swap( array[y], array[indice] );}

Now, this I believe is the fastest it gets with iterative methods, which if you're programming on something like a gameboy, is ideal since return tables are probably difficult to maintain.

william bubel

ProblemBaby

122

Author

October 24, 2004 03:35 PM

I tried this...

int index, temp;
for (int n = 0; n < (5-1); n++)
{
index = n;
for (int m = n+1; m < 5; m++)
{
if (data[m].nValue < data[index].nValue)
index = m;
}

temp = data[index].nIndex;
data[index].nIndex = data[n].nIndex;
data[n].nIndex = temp;
}

Result:
data[0].nValue = 29; // index 1
data[1].nValue = 9; // index 0
data[2].nValue = 12;// index 2
data[3].nValue = 39;// index 4
data[4].nValue = 26;// index 3

I want it to be...

data[0].nValue = 29; // index 1
data[1].nValue = 9; // index 4
data[2].nValue = 12;// index 3
data[3].nValue = 39;// index 0
data[4].nValue = 26;// index 2

Problems every where

Sorting algorithm

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Sorting algorithm

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines