Go Down

Topic: Sorting an array (Read 31708 times) previous topic - next topic

smartroad

Sep 02, 2010, 09:36 pm Last Edit: Sep 02, 2010, 09:38 pm by smartroad Reason: 1
Okay, maybe I am trying to change apples to oranges, however I need to be able to sort an array and found this website that has code to do it. I have converted it to what I believe to be the equivalent with the Arduino however it isn't working. (-edit- I need the array to be descending rather then ascending).

Here is the code:
Code: [Select]
byte numbers[] = {2, 5, 10, 1, 31};

void setup()
{
 Serial.begin(9600);
}

void loop()
{
 SortDec(numbers, 5);
 for(byte count = 0; count <=5; count ++)
 {
   Serial.print(numbers[count]);
   Serial.print(", ");
 }
 Serial.println();
}




int FindMax(byte ARRAY[], byte START, byte END)
{
 byte MAXIMUM, LOCATION;
 
 MAXIMUM = ARRAY[START];
 LOCATION = START;
 for(byte i = START + 1; i < END; i++)
 {
   if(ARRAY[i] > MAXIMUM)
   {
     MAXIMUM = ARRAY[i];
     LOCATION = i;
   }
 }
 
 return LOCATION;
}



void Swap(byte ARRAY[], byte a, byte b)
{
 byte temp, location;
 
 temp = ARRAY[a];
 ARRAY[a] = ARRAY[b];
 ARRAY[b] = temp;
}



void SortDec(byte ARRAY[], byte SIZE)
{
 byte location;
 
 for(byte i = 0; i < SIZE - 1; i++)
 {
   location = FindMax(ARRAY, i, SIZE);
   
   Serial.print(location);
   Swap(ARRAY, i, location);
 }
}


Now if I call "FindMax" with FindMax(numbers, 0, 5) I will get the position of the largest number. But when I call SortDec(numbers, 5) it doesn't work and just clears the array. I have a feeling I can't keep using the array like this (passing from procedure to procedure) and that is why it isn't working as I hopped.

Anyone had any experience with this?

PaulS

Every time through the array (and you're stopping one position to soon), you need to find the largest value from the current position to the end of the array, not the largest value in the array.

You can use Serial.print() and Serial.println() to print out stuff, like the location of the largest number and the value at that location.

When printing the array, after "sorting", you print the values in
  • , [1], ... [5]. Since there are only 5 values in the array, the upper index limit is 4 (count < 5, not count <= 5).
The art of getting good answers lies in asking good questions.

mpeuser

#2
Sep 03, 2010, 12:54 am Last Edit: Sep 03, 2010, 12:58 am by mpeuser Reason: 1
Paul is not at his best tonight  ;)

The program is fine, though the algorithm is measly, but that is another story...
You problem is here:
Code: [Select]
Serial.print(numbers[count], DEC);

Eight

Quote
Paul is not at his best tonight ;)

You can't say things like that! :)

PaulS

Quote
You can't say things like that!

He could, if it were true.

There are many problems with the code, the least of which is the fact that the results are not printed properly.

Using Serial.print() to see what is happening during the sorting, as I suggested, would have revealed the printing problem, too.
The art of getting good answers lies in asking good questions.

Eight

#5
Sep 03, 2010, 10:48 am Last Edit: Sep 03, 2010, 10:48 am by Eight Reason: 1
Don't they teach how to write a bubble sort or similar in schools anymore?

I remember when I was young... they wouldn't even let you touch a computer until you wrote perfect psuedo-code for a bubble sort.

smartroad

@Eight

The last time I had to write up anything like this in a programming language was some 20 years ago lol

This is only a proof of concept at the moment. I wanted to get a basic sort running before I expand it out to the final program. This is my first attempt at translating code from one language to another and I wasn't even sure if you can keep re-pointing an array like that from one procedure to another with the Arduino.

mpeuser

#7
Sep 03, 2010, 01:08 pm Last Edit: Sep 03, 2010, 01:10 pm by mpeuser Reason: 1
Quote
He could, if it were true.

Paul, it is true :-)

There is nothing really wrong with the progam, except it uses a lousy algorithm...

The error was, that the OP had printed the array in binary and took the zero like output for an empty array.

Bubblesort is an advantage over the used - well - algorithm, in that it is much shorter  and tighter in code.

Otherwise Bubblesort also belongs to the algorithms teachers show their students to explain how they should NOT do it.... But for sorting things that would fit into a 328 RAM it might do....

PaulS

The FindMax function is called to find the largest value in the array, however many times there are values in the array. The largest value is then swapped with the current value.

With the original input, {2, 5, 10, 1, 31}, the SortDec function will loop with 0, 1, 2, and 3. During each iteration of the loop, the same maximum value, 31, will be found. After the first iteration, the array will contain {31, 5, 10, 1, 2} because 0 and 4 got swapped.
After the second iteration, the FindMax function will find the 31 again. It will then be swapped with the 5, resulting in {5, 31, 10, 1, 2}. This is hardly progressing in the first direction.

It isn't a lousy algorithm. It's plain wrong. If the program is to be used, FindMax needs to find the largest value in a range that gets progressively smaller.
The art of getting good answers lies in asking good questions.

whistler

@smartroad

As I think has been well pointed out there are much better ways of doing a simple sort. For short and tight and waaaaaay more intuitive and understandable can I offer an insert sort?

is 5 smaller than 2? - no - leave array as is: 2, 5, 10, 1, 31
is 10 smaller than 5? - no - leave array as is: 2, 5, 10, 1, 31
is 1 smaller than 10? - yes
is 1 smaller than 5? - yes
is 1 smaller than 2? - yes
move 2, 5 and 10 to the right and slot in 1 - array is: 1, 2, 5, 10, 31
is 31 smaller than 10 - no - leave array as is: 1, 2, 5, 10, 31

Code: [Select]
byte numbers[] = {2, 5, 10, 1, 31};

void setup()
{
 Serial.begin(9600);

 printArray(numbers, sizeof(numbers));
 isort(numbers, sizeof(numbers));
 printArray(numbers, sizeof(numbers));
}

//Bubble sort my ar*e
void isort(byte *a, int n)
{
 for (int i = 1; i < n; ++i)
 {
   int j = a[i];
   int k;
   for (k = i - 1; (k >= 0) && (j < a[k]); k--)
   {
     a[k + 1] = a[k];
   }
   a[k + 1] = j;
 }
}

//what it says on the tin
void printArray(byte *a, int n)
{
 for (int i = 0; i < n; i++)
 {
   Serial.print(a[i], DEC);
   Serial.print(' ');
 }
 Serial.println();
}

//we'll not use loop for this
void loop()
{
}

PaulS

But, OP wanted the array sorted in descending order...
The art of getting good answers lies in asking good questions.

smartroad

Sorry, maybe i should have explained in more detail. The final array will have 50 entries. I have only used 5 as an example. Had a quick look (at work so not much time too!) found this:
Code: [Select]
for(x = 0; x < ARRAY_SIZE; x++)
   for(y = 0; y < ARRAY_SIZE-1; y++)
     if(iarray[y] > iarray[y+1]) {
       holder = iarray[y+1];
       iarray[y+1] = iarray[y];
       iarray[y] = holder;
     }


Which on the surface looks very similar to whistlers algorithm.

Eight

@smartroad
Quote
The last time I had to write up anything like this in a programming language was some 20 years ago lol

Hahaha, to be quite honest, it's been a long time since I wrote an array sort myself. :D

@desilva
I wasn't recommending a bubble sort for this... even if it might work... I was just sharing the memory. Or thread jacking as it is sometimes known. ;)

whistler

Code: [Select]
//Descending insert sort - just for Paul (and the OP of course)
void isort(byte *a, int n)
{
 for (int i = 1; i < n; ++i)
 {
   int j = a[i];
   int k;
   for (k = i - 1; (k >= 0) && (j [glow]>[/glow] a[k]); k--)
   {
     a[k + 1] = a[k];
   }
   a[k + 1] = j;
 }
}


Quote
Which on the surface looks very similar to whistlers algorithm.


@smartroad - well not quite - yours is an implementation of the infamous bubble sort and will ALLWAYS take n*n-1 iterations i.e. 2450 for your 50 entry array. Wheras the insert sort will take substantially less the more sorted the array is to start with.

BTW yours in ASCENDING too - tsk - tsk. :)

mpeuser

@Paul: Can it be we are talking about different program code????

Go Up