I have the following data structure and sort function, so that when a new event is entered, the entire array is sorted by startTime. It almost works, except it leaves a couple stragglers out of order. I have fixed it by running the function twice, seems to fix the stragglers, but I'd rather get some help and understand exactly what's wrong with it.
struct fourZoneStruct {
unsigned char zone1 :4;
unsigned char zone2 :4;
unsigned char zone3 :4;
unsigned char zone4 :4;
};
struct bellEventStruct {
unsigned long startTime :11;
unsigned long sunday :1;
unsigned long monday :1;
unsigned long tuesday :1;
unsigned long wednesday :1;
unsigned long thursday :1;
unsigned long friday :1;
unsigned long saturday :1;
fourZoneStruct zones1to4;
fourZoneStruct zones5to8;
};
struct ntpModuleSettings {
WORD version;
char deviceName[21];
bellEventStruct bellEvent[100];
WORD checkSum;
}extern userNTPSettings;
void setup() {
// put your setup code here, to run once:
}
void loop() {
// put your main code here, to run repeatedly:
}
void sortEvents() {
unsigned char i, j, k;
for (i = 0; i < 50; i++) {
k = i;
for (j = i + 1; j < 50; j++) {
if (userNTPSettings.bellEvent[j].startTime == 0);
else if (userNTPSettings.bellEvent[j].startTime == 1440) {
k = j;
swapEvents(&userNTPSettings.bellEvent[k], &userNTPSettings.bellEvent[i]);
}
else if (userNTPSettings.bellEvent[j].startTime < userNTPSettings.bellEvent[k].startTime) {
k = j;
swapEvents(&userNTPSettings.bellEvent[k], &userNTPSettings.bellEvent[i]);
}
}
}
}
void swapEvents(bellEventStruct* pMinTime, bellEventStruct* pMinPlace) {
bellEventStruct tempEvent = *pMinTime;
*pMinTime = *pMinPlace;
*pMinPlace = tempEvent;
}
0 is an empty record, and 1440 is 00:00 or midnight of the previous day... ie minute 0.... I should have mentioned that...
I think it's my for loops and how I am indexing them... the n and the n dirivitives...
I fixed the function name, that was a typo.
so what should happen to empty records ?
why do you use unsigned long if the max value is 1440 (I assume you split the day in minutes)? a uint16_t would be plenty.
why do you use a legit time for empty records? make that 0xFFFF and they will be bumped to the end of the array through the sorting algorithm and you don't need to worry about those
(note that you stop at 50 when you have 100 in the structure)
J-M-L:
so what should happen to empty records ?
why do you use unsigned long if the max value is 1440 (I assume you split the day in minutes)? a uint16_t would be plenty.
why do you use a legit time for empty records? make that 0xFFFF and they will be bumped to the end of the array through the sorting algorithm and you don't need to worry about those
(note that you stop at 50 when you have 100 in the structure)
Empty records should go to the bottom of the list...
I use a struct with bitfields, and I removed some part of the struct irrelevant to the sorting question, but with those bits in there, the structure is 32 bits...
I used to have midnight as zero and empty records were at 0x07FF, the top value for an 11-bit number... The problem was, it would create work elsewhere in the program... for example, I had to fill empty records by default, then conditionals were more complicated... It is easier if 0 is empty because that's their default state, and Boolean conditionals work like that...
The sort really only happens when the records are updated, which is much less frequently than all the other code operating on the records and the conditionals as they are now do what they should...
Midnight also works as the top value because it doesn't even work right as zero, more to do with where it is in a 24-hour cycle, so I have to have exception code for handling midnight anyway, making the value representing it irrelevant.
a correct sort of a few records would look like this:
{
1440,//midnight
1,// 00:01
480,// 08:00
720,// 12:00
1080,// 18:00
0,
0,
0,//... to the end of the array
}
You know that there are library functions for performing sorts? All you have to do is provide compare and swap functions
I don't know about library functions for sorting... which library? Can you provide more information?
about the oops would an empty bracket make it more clear? I have the line in there to prevent the third conditional from operating on j events with 0 values.
J-M-L:
So for the sorting algorithm you have special comparisons:
1440 is less than anything
0 is greater than anything
rest works as usual math
void sort()
{
for (byte i = 0; i < n-1; i++)
for (byte j = 0; j < n-i-1; j++)
if ((arr[j+1] == 1440) || (arr[j] == 0) || (arr[j] > arr[j+1])) swap(&arr[j], &arr[j+1]);
}
It took me some time to implement this because other things became a priority, but I managed this morning...
Because 1440 > 1 to 1439 > 0 the third argument breaks the sort.... and 0s and midnights end up wherever when the sort is complete....
I recall one of my college lecturers saying that sort algorithms are simple enough that anyone can implement one, but that they're hard enough that any such attempt will inevitably have at least one bug in it.
Take Awol's advice and look at library functions - qsort for example, although it can consume a lot of stack space - which Arduino are you using?
J-M-L:
right indeed needed to check also for J+1
(don't hardcode 49 and 50 in your program, make the size a constant and use it - that will ease maintenance)
I check j && j+1 && j > j+1...
Yeah, 49 and 50 aren't hardcoded anymore... as you discovered, there's 100 records, or 50 or x, so in the larger body of code it's derivative of the array using size_t n = sizeof arr / sizeof arr[0] ...
wildbill:
I recall one of my college lecturers saying that sort algorithms are simple enough that anyone can implement one, but that they're hard enough that any such attempt will inevitably have at least one bug in it.
Take Awol's advice and look at library functions - qsort for example, although it can consume a lot of stack space - which Arduino are you using?
I am um not using Arduino anything... it's actually running on a "SBL2E" which is a Netburner module with a Freescale Coldfire microcontroller, with an Eclipse IDE but I think it's a Gnu GCC compiler... I don't have a lot of stack space left... The sort, as implemented works, once the bugs were squashed... I am not familiar enough with c++ libraries...
It improves on bubble sort (which is the one you are using) by fast tracking to the right location the small values (the turtles) that are near the end
void combSort(int a[], size_t n)
{
size_t gap = n;
bool swapped = true;
while (gap != 1 || swapped == true) {
gap = ((gap * 10) / 13) < 1) ? 1 : gap; // this might be costly depending on CPU capabilities
swapped = false;
for (size_t i = 0; i < n - gap; i++) {
if (a[i] > a[i + gap]) {
swap(a[i], a[i + gap]);
swapped = true;
} // end if
} // end for
} // end while
}
as previously you need to adjust the comparison before the swap to take into account you specifics if (a[i] > a[i + gap]) {here it's not J and J+1 but i and i+gap
Perehama:
I am um not using Arduino anything... it's actually running on a "SBL2E" which is a Netburner module with a Freescale Coldfire microcontroller, with an Eclipse IDE but I think it's a Gnu GCC compiler... I don't have a lot of stack space left... The sort, as implemented works, once the bugs were squashed... I am not familiar enough with c++ libraries...
Don't reinvent the wheel, use the well-tested, fast std::sort function from the C++ standard library: std::sort - cppreference.com
According to the standard, std::sort may dynamically allocate. GCC uses introsort, which is an in-place sorting algorithm, so you don't have to worry about that.
Either overload the less-than operator for your data type, or provide a comparison function as an argument to the std::sort function.
Thank you.