[Solved] Sort Array according to integer array

Projects Programming
1

Hey everybody,
I tried to sort a char array according to an other array.
Goal Function (Pseudo):
Correlated (mixed) List:

Array A: {"test3", "", "test2", ""}  //nothing in Array ("") equals -1
Array B: {3, -1, 2, -1}// ex. "test3" equals 3, etc.

Finished sorting:

Array A: {"test2", "test3", "", ""} //sort Array A according to values of Array B
Array B: {2, 3, -1, -1}

Unfortunately I was just able to do it with the data-type "String". I need the exact following operation, but with char arrays. When using (large) Strings in my whole program, memory allocations, as well as performance problems appear.
Working Code just for Strings:

#define len(arg) ((unsigned int) (sizeof (arg) / sizeof (arg [0])))// number of items in an array

void setup() {
  // put your setup code here, to run once:
  Serial.begin(9600);
  delay(1000);
  Serial.println("startup");

  //init
  int intTest[] = {3, -1, -1, 2,};
  String stringTEst[] = {"test3","" , "", "test2" };
  //sorting
  bubbleAddRef(intTest, stringTEst, len(intTest));
  //print-out
  for (int i = 0; i < len(intTest); i++) {
    Serial.print("intTest: ");
    Serial.print(intTest[i]);
    Serial.print("- stringTest: ");
    Serial.println(stringTEst[i]);
  }

}
void loop() {
  // put your main code here, to run repeatedly:
}

void bubbleAddRef(int a[], String b[],  int size) {//highest goes to the last
  //bubble sorting method
  //http://hwhacks.com/2016/05/03/bubble-sorting-with-an-arduinoc-application/
  for (int i = 0; i < (size - 1); i++) {
    for (int o = 0; o < (size - (i + 1)); o++) {
      if (((a[o] < a[o + 1]) && (a[o] >= 0)) || (a[o + 1] < 0)) {//values under 0 are seen as the highest
        // array a
        int t = a[o];
        a[o] = a[o + 1];
        a[o + 1] = t;
        // array b
        String st = b[o];
        b[o] = b[o + 1];
        b[o + 1] = st;
      }
    }
  }
}

I would be really happy if some of you, could help me with this.
Oh yeah, and just doing the same operations with strcpy() for example, is also a performance problem.
I thought about to sort the char array after we determined the needed changes...?

EDIT: You can find the summary and the solution (also different data-types) on the 15# Post!

1 Like
2

So you want to use char * ? yeah that works really well.

#define len(arg) ((unsigned int) (sizeof (arg) / sizeof (arg [0])))// number of items in an array

void setup() {
  // put your setup code here, to run once:
  Serial.begin(9600);
  delay(1000);
  Serial.println("startup");

  //init
  int intTest[] = {3, -1, -1, 2,};
  String stringTEst[] = {"test3","" , "", "test2" };
  //sorting
  bubbleAddRef(intTest, stringTEst, len(intTest));
  //print-out
  for (int i = 0; i < len(intTest); i++) {
    Serial.print("intTest: ");
    Serial.print(intTest[i]);
    Serial.print("- stringTest: ");
    Serial.println(stringTEst[i]);
  }

}
void loop() {
  // put your main code here, to run repeatedly:
}

void bubbleAddRef(int a[], String b[],  int size) {//highest goes to the last
  //bubble sorting method
  //http://hwhacks.com/2016/05/03/bubble-sorting-with-an-arduinoc-application/
  for (int i = 0; i < (size - 1); i++) {
    for (int o = 0; o < (size - (i + 1)); o++) {
      if (((a[o] < a[o + 1]) && (a[o] >= 0)) || (a[o + 1] < 0)) {//values under 0 are seen as the highest
        // array a
        int t = a[o];
        a[o] = a[o + 1];
        a[o + 1] = t;
        // array b
        String st = b[o];
        b[o] = b[o + 1];
        b[o + 1] = st;
      }
    }
  }
}

In the 'String' , Somehow i think if you would do it like this :

String *st = &b[o];
        b[o] = b[o + 1];
        b[o + 1] = *st;

You would also just move the pointers around, and you don't get any fragmentation. You pass a String-array, as an argument, that is an array of pointers(to String object) but once you create a 'new' String and then assign it's pointer to a field in that array, this is where it goes wrong. The memory where the pointer in that field was pointing to is now not referenced anymore.

3

I need the exact following operation, but with char arrays.

How hard did you try ?
Replace the String data specifier with char * throughout the sketch

4

Hey, thanks for all your replys.
Unfortunately, when I replace the data-type "String" with char pointers (char*) there are still sometimes memory allocations, when working with large dynamic char-arrays (size is dynamic).
Do you have an Idea of how you could do this procedure, when having somethings like the following Array?

char stringTEst[][10] = {"test3","" , "", "test2" };

This is where I am having the problems.

5

there are still sometimes memory allocations, when working with large dynamic char-arrays (size is dynamic).

How are you dynamically changing the size of the arrays ?

6

Deva_Rishi:
In the 'String' , Somehow i think if you would do it like this :

String *st = &b[o];

b[o] = b[o + 1];
       b[o + 1] = *st;

Thanks for your reply. I think that this might be the way to go.
Unfortunately it doesn't work with Arduino. Did this code work for you? Could you post it, just in case I might have done a mistake?

UKHeliBob:
How are you dynamically changing the size of the arrays ?

No, i am just reading different Sizes of "Strings". And therefore I am kinda worried, that the compiler doesn't "safe" enough SRAM-Storage for those large new input "Strings".

7

i am just reading different Sizes of "Strings".

So you are not actually dynamically changing the size of the arrays after all, just changing the size of the data that they hold

Using Strings in that way is usually regarded as bad idea because it can lead to memory fragmentation and there is precious little memory available in the first place in the average Arduino, hence the advice to use strings rather than Strings

8

Unfortunately it doesn't work with Arduino. Did this code work for you?

Yep, (but for the second one using String* it may be just by accident) The first one with the char* arrays is actually the way to go. You simply swap the pointers and you never really move the data. You know your sorting function takes array as arguments, and the only reason it works at all is because the array is a pointer, so it is actually passed to the function by reference. And that is why the version with the 'String ' also should work, but as i said, the String class is not quite as transparent as when using char.

9

Oh no not like this :char stringTEst[][10] = {"test3","" , "", "test2" };like this char *stringTEst[] = {"test3","" , "", "test2" };The only condition is that you actually do not modify the data, but only swap it around. (due to the sizes of the strings not being equal) Otherwise you have to do the whole thing char-array where you set the size of the string (+1 for the null terminator) when you declare the arraychar stringTEst[][10] = {"test3","" , "", "test2" };as you did. But then repeat that size in the argument when you declare the function void bubbleAddRef(int a[], char b[][10],  int size) {and then swap the pointers over, and the only way i've manged to do that is by passing them as an argument to another function

if (((a[o] < a[o + 1]) && (a[o] >= 0)) || (a[o + 1] < 0)) {//values under 0 are seen as the highest
        // array a
        int t = a[o];
        a[o] = a[o + 1];
        a[o + 1] = t;
        // array b
        CharArraySwap(b[o], b[o + 1]);
      }

and the function can then take char* as arguments

void CharArraySwap(char* sw1, char* sw2) {
  char* sw = sw1;
  sw1 = sw2;
  sw2 = sw;
}

That compiles and works in the example.

10

Oh i see now that in my initial response i didn't post the sketch i meant to post. I will do that now here :

#define len(arg) ((unsigned int) (sizeof (arg) / sizeof (arg [0])))// number of items in an array

void setup() {
  // put your setup code here, to run once:
  Serial.begin(9600);
  delay(1000);
  Serial.println("startup");

  //init
  int intTest[] = {3, -1, -1, 2,};
  char * stringTEst[] = {"test3","" , "", "test2" };
  //sorting
  bubbleAddRef(intTest, stringTEst, len(intTest));
  //print-out
  for (int i = 0; i < len(intTest); i++) {
    Serial.print("intTest: ");
    Serial.print(intTest[i]);
    Serial.print("- stringTest: ");
    Serial.println(stringTEst[i]);
  }

}
void loop() {
  // put your main code here, to run repeatedly:
}

void bubbleAddRef(int a[], char * b[],  int size) {//highest goes to the last
  //bubble sorting method
  //http://hwhacks.com/2016/05/03/bubble-sorting-with-an-arduinoc-application/
  for (int i = 0; i < (size - 1); i++) {
    for (int o = 0; o < (size - (i + 1)); o++) {
      if (((a[o] < a[o + 1]) && (a[o] >= 0)) || (a[o + 1] < 0)) {//values under 0 are seen as the highest
        // array a
        int t = a[o];
        a[o] = a[o + 1];
        a[o + 1] = t;
        // array b
        char * st = b[o];
        b[o] = b[o + 1];
        b[o + 1] = st;
      }
    }
  }
}

That does throw a warning about the declaration though.
And for completions sake the full char-array version

#define len(arg) ((unsigned int) (sizeof (arg) / sizeof (arg [0])))// number of items in an array

void setup() {
  // put your setup code here, to run once:
  Serial.begin(9600);
  delay(1000);
  Serial.println("startup");

  //init
  int intTest[] = {3, -1, -1, 2,};
  char stringTEst[][10] = {"test3","" , "", "test2" };
  //sorting
  bubbleAddRef(intTest, stringTEst, len(intTest));
  //print-out
  for (int i = 0; i < len(intTest); i++) {
    Serial.print("intTest: ");
    Serial.print(intTest[i]);
    Serial.print("- stringTest: ");
    Serial.println(stringTEst[i]);
  }

}
void loop() {
  // put your main code here, to run repeatedly:
}

void bubbleAddRef(int a[], char b[][10],  int size) {//highest goes to the last
  //bubble sorting method
  //http://hwhacks.com/2016/05/03/bubble-sorting-with-an-arduinoc-application/
  for (int i = 0; i < (size - 1); i++) {
    for (int o = 0; o < (size - (i + 1)); o++) {
      if (((a[o] < a[o + 1]) && (a[o] >= 0)) || (a[o + 1] < 0)) {//values under 0 are seen as the highest
        // array a
        int t = a[o];
        a[o] = a[o + 1];
        a[o + 1] = t;
        // array b
        CharArraySwap(b[o], b[o + 1]);
      }
    }
  }
}

void CharArraySwap(char* sw1, char* sw2) {
  char* sw = sw1;
  sw1 = sw2;
  sw2 = sw;
}

It happens that when i post snippets as solutions people do not always implement them correctly.

11

The only condition is that you actually do not modify the data, but only swap it around. (due to the sizes of the strings not being equal)

Sorry, but I don't understand what you mean by this

Are you saying that

  char *stringTEst[] = {"test3", "" , "", "test2" };
  stringTEst[2] = "a very much longer string of characters";

would cause a problem ?

12

Deva_Rishi:
That does throw a warning about the declaration though.
And for completions sake the full char-array version:
[...]

Thanks man, that really helped a lot already!!!
The first version with char pointer works like a charm. I am kind having a problem with full defined char-arrays. I can't work with pointers, as I need to actually store those strings in that array! So, your second version doesn't work on all the arduinos I have.... Did I do something wrong here, I just don't get it?!
I only get this output:

startup
intTest: -1- stringTest: test3
intTest: -1- stringTest: 
intTest: 3- stringTest:         //here should be the "test3"
intTest: 2- stringTest: test2

UKHeliBob:
Are you saying that [...] would cause a problem ?

In my case not necessarily, though I technically have no "limitation" of the new definition and therefore it might can cause memory fragmentation (had that ones before: when printing a variable, it might happen, that different variables "falsely combine/store" values of other variables).
Or would you consider using char pointers as a safe method? I am not really sure, nor very well familiar with pointers...

13

Are you saying that
Code: [Select]

char *stringTEst[] = {"test3", "" , "", "test2" };
stringTEst[2] = "a very much longer string of characters";

would cause a problem ?

For sure it would ! You know it does. Declaring a char* only declares the number of characters + the null terminator, if you then increase the size you will be writing beyond it's size, and in this case beyond the size of the whole array. If you only swap the pointers around, there is no problem.

In my case not necessarily, though I technically have no "limitation" of the new definition and therefore it might can cause memory fragmentation

Fragmentation is not the issue !!

So, your second version doesn't work on all the arduinos I have....

Sorry yes it doesn't work for me either, i just wasn't sure what sketch i had uploaded, but now i see it doesn't work.

I am kind having a problem with full defined char-arrays. I can't work with pointers, as I need to actually store those strings in that array!

It is not my specialty either, and i keep forgetting that a 2 dimensional char-array is just that, a single pointer with a double-offset (rather than an array of pointers) anyway, that just means that we have to actually physically swap the data around using strcpy()
Also to prevent unwanted mistakes i changed the variable name 'o' to 'j' I think it is totally fine to use single character variable names for counters, but not 'o' ! It just looks to much like '0' (i start out with 'i' and keep going 1 letter up and rarely end up using 'l') usually more descriptive names are better.

#define len(arg) ((unsigned int) (sizeof (arg) / sizeof (arg [0])))// number of items in an array
const int CarraySize = 10;

void setup() {
  // put your setup code here, to run once:
  Serial.begin(9600);
  delay(1000);
  Serial.println("startup");

  //init
  int intTest[] = {3, -1, -1, 2,};
  char stringTEst[][CarraySize] = {"test3", "" , "", "test2" };
  //sorting
  bubbleAddRef(intTest, stringTEst, len(intTest));
  //print-out
  for (int i = 0; i < len(intTest); i++) {
    Serial.print("intTest: ");
    Serial.print(intTest[i]);
    Serial.print(" - stringTest: ");
    Serial.println(stringTEst[i]);
  }

}
void loop() {
  // put your main code here, to run repeatedly:
}

void bubbleAddRef(int a[], char b[][CarraySize],  int size) {//highest goes to the last
  //bubble sorting method
  //http://hwhacks.com/2016/05/03/bubble-sorting-with-an-arduinoc-application/
  for (int i = 0; i < (size - 1); i++) {
    for (int j = 0; j < (size - (i + 1)); j++) {
      if (((a[j] < a[j + 1]) && (a[j] >= 0)) || (a[j + 1] < 0)) {//values under 0 are seen as the highest
        // array a
        int t = a[j];
        a[j] = a[j + 1];
        a[j + 1] = t;
        char sw[CarraySize];
        strcpy(sw, b[j]);
        strcpy(b[j], b[j + 1]);
        strcpy(b[j + 1], sw);
      }
    }
  }
}
14

Are you saying that
Code: [Select]

char *stringTEst[] = {"test3", "" , "", "test2" };
stringTEst[2] = "a very much longer string of characters";

would cause a problem ?

For sure it would ! You know it does. Declaring a char* only declares the number of characters + the null terminator, if you then increase the size you will be writing beyond it's size, and in this case beyond the size of the whole array. If you only swap the pointers around, there is no problem.

Actually that would not produce an error. The compiler is creating a string constant, then assigning the pointer for that string constant to stringTEst[2].

Note that stringTEst should be declared as const char* because the object of the pointers are const char array.

15

Declaring a char* only declares the number of characters + the null terminator

When using arrays of pointers to data each pointer takes 2 bytes on an AVR. 4 array entries therefore takes 8 bytes. Changing the size of the data does not change the size of the pointer but the location of the data pointed to will probably change

16

Summery of this Thread: Solution with all the Data types we have discussed:

Working with Strings:

#define len(arg) ((unsigned int) (sizeof (arg) / sizeof (arg [0])))// number of items in an array

void setup() {
// put your setup code here, to run once:
Serial.begin(9600);
delay(1000);
Serial.println("startup");

//init
int intTest[] = {3, -1, -1, 2,};
String stringTEst[] = {"test3","" , "", "test2" };
//sorting
bubbleAddRef(intTest, stringTEst, len(intTest));
//print-out
for (int i = 0; i < len(intTest); i++) {
  Serial.print("intTest: ");
  Serial.print(intTest[i]);
  Serial.print("- stringTest: ");
  Serial.println(stringTEst[i]);
}

}
void loop() {
// put your main code here, to run repeatedly:
}

void bubbleAddRef(int a[], String b[],  int size) {//highest goes to the last
//bubble sorting method
//http://hwhacks.com/2016/05/03/bubble-sorting-with-an-arduinoc-application/
for (int i = 0; i < (size - 1); i++) {
  for (int o = 0; o < (size - (i + 1)); o++) {
    if (((a[o] < a[o + 1]) && (a[o] >= 0)) || (a[o + 1] < 0)) {//values under 0 are seen as the highest
      // array a
      int t = a[o];
      a[o] = a[o + 1];
      a[o + 1] = t;
      // array b
      String st = b[o];
      b[o] = b[o + 1];
      b[o + 1] = st;
    }
  }
}
}

Working with (fixed size) char array:

#define len(arg) ((unsigned int) (sizeof (arg) / sizeof (arg [0])))// number of items in an array
const int CarraySize = 10;

void setup() {
// put your setup code here, to run once:
Serial.begin(9600);
delay(1000);
Serial.println("startup");

//init
int intTest[] = {3, -1, -1, 2,};
char stringTEst[][CarraySize] = {"test3", "" , "", "test2" };
//sorting
bubbleAddRef(intTest, stringTEst, len(intTest));
//print-out
for (int i = 0; i < len(intTest); i++) {
  Serial.print("intTest: ");
  Serial.print(intTest[i]);
  Serial.print(" - stringTest: ");
  Serial.println(stringTEst[i]);
}

}
void loop() {
// put your main code here, to run repeatedly:
}

void bubbleAddRef(int a[], char b[][CarraySize],  int size) {//highest goes to the last
//bubble sorting method
//http://hwhacks.com/2016/05/03/bubble-sorting-with-an-arduinoc-application/
for (int i = 0; i < (size - 1); i++) {
  for (int j = 0; j < (size - (i + 1)); j++) {
    if (((a[j] < a[j + 1]) && (a[j] >= 0)) || (a[j + 1] < 0)) {//values under 0 are seen as the highest
      // array a
      int t = a[j];
      a[j] = a[j + 1];
      a[j + 1] = t;
      char sw[CarraySize];
      strcpy(sw, b[j]);
      strcpy(b[j], b[j + 1]);
      strcpy(b[j + 1], sw);
    }
  }
}
}

Working with char pointers (method I have used):

#define len(arg) ((unsigned int) (sizeof (arg) / sizeof (arg [0])))// number of items in an array

void setup() {
 // put your setup code here, to run once:
 Serial.begin(9600);
 delay(1000);
 Serial.println("startup");

 //init
 int intTest[] = {3, -1, -1, 2,};
 char stringArray[][10] = {"test3", "", "", "test2"};
 char * stringPointers[] = {stringArray[0], stringArray[1] , stringArray[2], stringArray[3]};
 //sorting
 bubbleAddRef(intTest, stringPointers, len(intTest));
 //print-out
 for (unsigned int i = 0; i < len(intTest); i++) {
   Serial.print("intTest: ");
   Serial.print(intTest[i]);
   Serial.print("- stringTest: ");
   Serial.println(stringPointers[i]);
 }

}
void loop() {
 // put your main code here, to run repeatedly:
}

void bubbleAddRef(int a[], char* b[],  int size) {//highest goes to the last
 //bubble sorting method
 //http://hwhacks.com/2016/05/03/bubble-sorting-with-an-arduinoc-application/
 for (int i = 0; i < (size - 1); i++) {
   for (int o = 0; o < (size - (i + 1)); o++) {
     if (((a[o] < a[o + 1]) && (a[o] >= 0)) || (a[o + 1] < 0)) {//values under 0 are seen as the highest
       // array a
       int t = a[o];
       a[o] = a[o + 1];
       a[o + 1] = t;
       // array b
       char * st = b[o];
       b[o] = b[o + 1];
       b[o + 1] = st;
     }
   }
 }
}

Note that you can also use just pointers, although that might cause some problems, as there is not fixed size for the array:

char* stringPointers[] = {"test3", "" , "", "test2" };

Special Thanks to @Deva_Rishi! You have helped me a lot with your great work!

P.S.: I figured out a way of still using pointers, with linking it to a fixed size array. This worked even better for me, as it doesn't consume so much dynamic memory, than using strcpy() so often.

17

This topic was automatically closed 120 days after the last reply. New replies are no longer allowed.