Go Down

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

smartroad

@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 :D (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!

AWOL

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

Not so.
It will ALWAYS take at most n*n-1 iterations.
"Pete, it's a fool (who) looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.
I speak for myself, not Arduino.

mpeuser

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.

PaulS

@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 art of getting good answers lies in asking good questions.

whistler

Quote

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

mpeuser

Quote
50 random numbers and timed how long it takes to sort the array. About 72uS


May I doubt those figures?

And there is the bitter Rule of the Square...

I just checked some values on the Arduino

(intelligent) Bubblesort 10 values:   140 us
unoptimized Quicksort: 10 values:    60 us

(intelligent) Bubblesort 50 values: 3,500 us
unoptimized Quicksort: 50 values:   500 us

(intelligent) Bubblesort 100 values: 10,500 us
unoptimized Quicksort: 100 values:  1,150 us

Note: all numbers depend on the pre-sort status!

I did not use the standard qsort, as it uses terribly much FLASH; my own quicksort is 152 bytes against 74  of Bubblesort

AWOL

@deSilva:
I think you need to take another look at your "intelligent" bubble sort.

10  values     79us (max   104us min     44us)
50  values  1896us (max 2036us min 1568us)
100 values  7627us (max 7960us min 6788us)

(averages over 1000 sorts each array size, array reinitialised using "random()" before each sort)
"Pete, it's a fool (who) looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.
I speak for myself, not Arduino.

mpeuser

#22
Sep 04, 2010, 09:25 pm Last Edit: Sep 05, 2010, 01:21 pm by mpeuser Reason: 1
It seems "your" bubblesort is twice as fast - I don't know why.. can't analyse this today... Nevertheless here is code I used for the benchmark:
Code: [Select]
void bSort1(byte array [], byte from, byte upTo) {
// code size = 74 bytes
byte swaps;  
do {
   swaps=0;
   for(byte i = from; i < upTo; i++)
     if(array[i] > array[i+1]) {
       byte x = array[i+1];
       array[i+1] = array[i];
       array[i] = x;
         ++swaps;
     }//for
 } while (swaps);
}//bsort1


Eidt:
----
This is the improvement proposed by Groove:
Code: [Select]
     }//for
      --upTo;
 } while (swaps);

It was erroniously deleted when I changed an outer For loop to the while... As the result was still correct, I did  not notice...

GrooveFlotilla

#23
Sep 04, 2010, 09:43 pm Last Edit: Sep 04, 2010, 09:45 pm by GrooveFlotilla Reason: 1
You're not decrementing 'upto' afte each pass.
At the end of each pass, the last item is in the right place so doesn't need to be compared again.
Some people are like Slinkies.

Not really good for anything, but they bring a smile to your face when pushed down the stairs.

mpeuser

#24
Sep 05, 2010, 12:26 pm Last Edit: Sep 05, 2010, 01:16 pm by mpeuser Reason: 1
Excellent! This is the factor of around 1/2!!

Edit:
The benchmark now shows 72us for 10 elements for Bubblesort (which is the bresr even point with reference to Quicksort.. fromnow on Quicksort becomes more and more efficient!

For 100 elements  the Bubblesort needs 7150 us (Quicksort around 1100)

westfw

Have you all seen this:
http://www.youtube.com/watch?v=t8g-iYGHpEA


carrycorrie

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

I just know about the FindMax now because of this thread.  Thank you for this information.

PaulS

Quote
I just know about the FindMax now because of this thread.  Thank you for this information.

Before you get too excited, the FindMax function in question was part of OP's sketch, not a native or library function.

And, it was incomplete and being used incorrectly.
The art of getting good answers lies in asking good questions.

carrycorrie

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

I just know about the FindMax now because of this thread.  Thank you for this information.

--------------
music maker software download

Go Up