Go Down

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

#15
##### Sep 03, 2010, 07:54 pm
@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!

#### AWOL

#16
##### Sep 03, 2010, 11:07 pm
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.

#### mpeuser

#17
##### Sep 04, 2010, 12:23 am
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

#18
##### Sep 04, 2010, 03:10 am
@deSilva
Maybe. I was referring to reply #9, where the values were sorted in increasing order, despite OPs desire to sort in decreasing order.

#### whistler

#19
##### Sep 04, 2010, 10:49 am
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

#20
##### Sep 04, 2010, 02:59 pm
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

#21
##### Sep 04, 2010, 09:18 pm
@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)

#### mpeuser

#22
##### Sep 04, 2010, 09:25 pmLast 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 pmLast 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.

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

#25
##### Sep 05, 2010, 11:00 pm
Have you all seen this:

#26

#### carrycorrie

#27
##### Sep 06, 2010, 07:31 am
"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

#28
##### Sep 06, 2010, 02:13 pm
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.

#### carrycorrie

#29
##### Sep 16, 2010, 06:54 am
"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.

--------------