Sorting an array

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:

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?

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 [0], [1], ... [5]. Since there are only 5 values in the array, the upper index limit is 4 (count < 5, not count <= 5).

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:

Serial.print(numbers[count], DEC);

Paul is not at his best tonight

You can't say things like that!

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.

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.

@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.

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....

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.

@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

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()
{
}

But, OP wanted the array sorted in descending order...

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:

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.

@smartroad

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.

@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.

//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;
  }
}

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.

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

@whistler

Got home and tried out your code, which worked fantastically! Thanks

I filled an array with 50 random numbers and timed how long it takes to sort the array. About 72uS is all (determined by taking micros() before and after running isort)

There is another part to this, but I want to try and sort it myself before I ask for help as I don't like bothering people too much and you guys have help so much already!

the infamous bubble sort and will ALLWAYS take n*n-1 iterations

Not so.
It will ALWAYS take at most n*n-1 iterations.

There are "intelligent bubblesorts". They notice that they did not do any swaps during the last iteration and stop. But you also see many "brute force bubblesorts" in the world.

@deSilva
Maybe. I was referring to reply #9, where the values were sorted in increasing order, despite OPs desire to sort in decreasing order.

the infamous bubble sort and will ALLWAYS take n*n-1 iterations

Not so.
It will ALWAYS take at most n*n-1 iterations.

You would of course be absolutely correct IF that's what I'd said. Try looking at my sentence again without cutting off the front in your excitement to correct me. Then take a look again at the implementation the OP submitted that I was talking about.