bubble sort in structure

C

cerr

Hi There,

I have no problem doing a bubble sort in an array but what if i need
to keep an identifier that is linked to the value so i always know
which values is where?
I have a little array with three "offset" elements and i would like to
sort them so that the smallest offset is at position 0. I can do that
with an array, n.p.:
// Bubble sort offset times
for (ctr=0;ctr<OFFSET_ARR_SZ;ctr++) {
if (iarray[ctr] > iarray[ctr+1]) {
//Here a swap is needed
temp=iarray[ctr+1];
iarray[ctr+1]=iarray[ctr];
iarray[ctr]=temp;
}
}
but once they're sorted and i want to take action i need to know what
action to take after the first offset i.e. i need to keep some kind of
identifier. I am aware that I could just sort after applying some kind
of binary mask to keep an id in my value... but i imagine there's a
more transparent way e.g. by sorting values in a structure...?
Recommendations and hints appreciated!
Thanks!
 
B

Ben Bacarisse

cerr said:
I have no problem doing a bubble sort in an array but what if i need
to keep an identifier that is linked to the value so i always know
which values is where?
I have a little array with three "offset" elements and i would like to
sort them so that the smallest offset is at position 0. I can do that
with an array, n.p.:
// Bubble sort offset times
for (ctr=0;ctr<OFFSET_ARR_SZ;ctr++) {
if (iarray[ctr] > iarray[ctr+1]) {
//Here a swap is needed
temp=iarray[ctr+1];
iarray[ctr+1]=iarray[ctr];
iarray[ctr]=temp;
}
}
but once they're sorted and i want to take action i need to know what
action to take after the first offset i.e. i need to keep some kind of
identifier. I am aware that I could just sort after applying some kind
of binary mask to keep an id in my value... but i imagine there's a
more transparent way e.g. by sorting values in a structure...?
Recommendations and hints appreciated!

An example might help. I think I know what you want but it's certainly
possible I've misunderstood.

One answer might be sort "indirectly". Rather than sort the data, you
sort an array containing the indexes of the data items (you can use
pointers if you prefer). Start by setting A = i and sort A by
comparing iarray[A]. If that does not suit, you can use A to sort
iarray and to build another index, B, where B contains the original
location of iarray.
 
C

cerr

An example might help.  I think I know what you want but it's certainly
possible I've misunderstood.

One answer might be sort "indirectly".  Rather than sort the data, you
sort an array containing the indexes of the data items (you can use
pointers if you prefer).  Start by setting A = i and sort A by
comparing iarray[A].  If that does not suit, you can use A to sort
iarray and to build another index, B, where B contains the original
location of iarray.


Hi Ben,

Thanks for getting back - not sure if I understood. I just implemented
a sort the alternative way i described above. That may help you to
understand:

iarray[0]=0; //SYNC
iarray[1]=500; //LPR
iarray[2]=200; //OVR

iarray[0]|=0x10000000; // set SYNC ID bit
iarray[1]|=0x20000000; // set LPR ID bit
iarray[2]|=0x40000000; // set OVR ID bit

// Bubble sort offset times
for (ctr=0;ctr<OFFSET_ARR_SZ;ctr++) {
if ((iarray[ctr]&0x00FFFFFF) > (iarray[ctr+1]&0x00FFFFFF)) {
//Here a swap is needed
temp=iarray[ctr+1];
iarray[ctr+1]=iarray[ctr];
iarray[ctr]=temp;
}
}

Then to "read" the sorted array I'd do it like this:
if (iarray[0]&&0xf0000000==0x10000000){
delay_us((iarray[0]&0x00FFFFFF))
SETSYNCTMR(timval);
} else if (iarray[0]&&0xf0000000==0x20000000){
delay_us((iarray[0]&0x00FFFFFF))
SETLPRTMR(timval);
} else if (iarray[0]&&0xf0000000==0x40000000){
delay_us((iarray[0]&0x00FFFFFF))
SETOVRTMR(timval);
}
and repeatr this for [1]&[2]
 
B

Ben Bacarisse

cerr said:
An example might help.  I think I know what you want but it's certainly
possible I've misunderstood.

One answer might be sort "indirectly".  Rather than sort the data, you
sort an array containing the indexes of the data items (you can use
pointers if you prefer).  Start by setting A = i and sort A by
comparing iarray[A].  If that does not suit, you can use A to sort
iarray and to build another index, B, where B contains the original
location of iarray.

Thanks for getting back - not sure if I understood. I just implemented
a sort the alternative way i described above. That may help you to
understand:

iarray[0]=0; //SYNC
iarray[1]=500; //LPR
iarray[2]=200; //OVR

iarray[0]|=0x10000000; // set SYNC ID bit
iarray[1]|=0x20000000; // set LPR ID bit
iarray[2]|=0x40000000; // set OVR ID bit

// Bubble sort offset times
for (ctr=0;ctr<OFFSET_ARR_SZ;ctr++) {
if ((iarray[ctr]&0x00FFFFFF) > (iarray[ctr+1]&0x00FFFFFF)) {
//Here a swap is needed
temp=iarray[ctr+1];
iarray[ctr+1]=iarray[ctr];
iarray[ctr]=temp;
}
}

This is not a bubble sort. It's not even well-defined unless
OFFSET_ARR_SZ is not what it claims to be!
Then to "read" the sorted array I'd do it like this:
if (iarray[0]&&0xf0000000==0x10000000){
delay_us((iarray[0]&0x00FFFFFF))
SETSYNCTMR(timval);
} else if (iarray[0]&&0xf0000000==0x20000000){
delay_us((iarray[0]&0x00FFFFFF))
SETLPRTMR(timval);
} else if (iarray[0]&&0xf0000000==0x40000000){
delay_us((iarray[0]&0x00FFFFFF))
SETOVRTMR(timval);
}
and repeatr this for [1]&[2]

It's not 100% clear. A guess: the fact the IDs are single bits is not
significant -- you won't ever combine them into a mask?

I suspect that a struct might be what you need. You can keep the data
(is it a time?) and the ID together. Another, similar, approach is to
sort two arrays in parallel: you have another array that contains the
IDs and you swap its elements whenever you swap a iarray pair.
 
K

Keith Thompson

cerr said:
I have no problem doing a bubble sort in an array but what if i need
to keep an identifier that is linked to the value so i always know
which values is where?
[...]

I hope you're aware that bubble sort is useful primarily as a coding
exercise. There are much better sorting algorithms (in fact, there
aren't many worse ones) and the standard qsort() will implement
one of them.

(Bubble sort might be useful in some cases where the list is already
almost sorted, but even there there might be better choices.)
 
M

Malcolm McLean

(Bubble sort might be useful in some cases where the list is already
almost sorted, but even there there might be better choices.)
These situations crop up quite a bit for real.

For instance imagine a virtual camera moving through a 3d world of
polygons. To draw the polygones correctly, you need to sort by z
order. However the camera will only move a small amount each frame.
Some of the ploygons might also move, if it's a dynamic world, but
again not by much.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Bubble Sort in C 48
Selection sort and bubble sort 22
Number of exchanges in a bubble sort 3
bubble sort!? 1
Selection-Sort in C 35
insertion sort in C 14
memory and speed 6
bubble sort 3

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top