search

octareenroon91 / analog-box

Automatically exported from code.google.com/p/analog-box
0 stars 0 forks source link

FFTOP Sort uses Bubble Sort !!! #25

Open GoogleCodeExporter opened 9 years ago

GoogleCodeExporter commented 9 years ago 
Problem:
The 'Sort' operation in the FFTOP Object uses a variation of a
bubble sort to arrange the 512 complex values by amplitude. For
large sorts (ie the largest 400 values), the bubble sort is
O(n squared) and wasteful of CPU cycles (not to mention it being
an embarrasment to programmers everywhere). For small sorts
(ie. find the largest 16 values), it is not so bad.

Recommend:
*Using an O(n log n) sort is desirable.
*The ABox macro library includes a Red-Black tree (rbtree.h) that
 could be used to sort the array of values. Tree sorts are
 O(n log n) but, using ABox rbtree, require four additional values
 per element: three pointers and one color.
*Alternately: Merge sort and/or Quick sort could be developed and
 included in the macro library. Merge and Quick need fewer addition
 values, and are thus slighly faster than a tree sort.

Original issue reported on code.google.com by andyt7...@gmail.com on 8 Jul 2011 at 8:48