All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Algorithm requested (Posted on 2013-12-18)
Given an array with random odd and even integers.
Please suggest the most efficient algorithm to put all even numbers on one side and all odd numbers on the other side in this array.

Source: Got an Email from an unknown person.

 See The Solution Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 a couple of algorithms | Comment 1 of 3

This is basically a sort, treating numbers as their mod 2 values. A while back, the Shell sort was considered the fastest in-place sort, but now it seems quicksort is more efficient.

As I'm not too familiar with quicksort, here is an implementation of a Shell sort:

DIM array(100)
FOR i = 1 TO 100
array(i) = INT(RND(1) * 900 + 100): PRINT array(i);
NEXT
PRINT : PRINT

span = INT(100 / 3)
DO
DO
done = 1
FOR i = 1 TO 100 - span
compct = compct + 1
IF array(i) MOD 2 > array(i + span) MOD 2 THEN
SWAP array(i), array(i + span): done = 0
swapct = swapct + 1
END IF
NEXT
LOOP UNTIL done
pspan = span
span = INT(span / 3)
IF span = 0 THEN span = 1
compct = compct + 1
LOOP UNTIL pspan = 1

PRINT
FOR i = 1 TO 100
PRINT array(i);
NEXT
PRINT : PRINT

PRINT compct, swapct, 3 * swapct

The random array of 100 3-digit numbers, before the sort, is first printed out:

` 734  580  621  360  371  797  112  784  833  738  140  472  876  811  436  965 884  150  954  427  572  790  148  633  521  368  660  683  337  351  846  842 630  987  919  304  725  982  319  580  195  999  708  114  617  190  192  818 356  141  366  443  370  953  981  461  350  244  246  681  469  471  741  393 669  286  267  625  172  512  915  335  806  441  360  927  668  664  485  188 604  725  922  851  120  589  924  487  710  552  562  516  418  464  342  150 319  981  154  451  After the sort:   734  580  304  360  982  884  112  784  360  738  140  472  876  192  436  356  464  150  954  370  572  790  148  350  244  368  660  922  342  150  846  842  630  664  190  172  512  418  710  580  120  818  708  114  366  552  188  924  286  246  668  562  806  516  604  154  797  371  319  833  195  427  919  683  987  965  393  669  351  267  625  621  337  915  335  927  441  999  485  811  617  725  141  851  443  589  953  981  461  633  521  725  681  469  471  741  319  981  487  451  `

The statistics are that 1541 comparisons were made; 88 swaps were made. If the 88 swaps were done via 3 assignments each, that would be 264 assignments.

Of course a simpler algorithm, based on the fact you have only two values to consider, would just place the numbers into two different lists depending on odd or even:

DIM array(100)
FOR i = 1 TO 100
array(i) = INT(RND(1) * 900 + 100): PRINT array(i);
NEXT
PRINT : PRINT

DIM even(100), odd(100)
FOR i = 1 TO 100
compct = compct + 1
IF array(i) MOD 2 = 0 THEN
evenct = evenct + 1: even(evenct) = array(i)
ELSE
oddct = oddct + 1: odd(oddct) = array(i)
END IF
assnct = assnct + 2
NEXT
FOR i = 1 TO evenct: array(i) = even(i): NEXT
FOR i = 1 TO oddct: array(i + evenct) = odd(i): NEXT
assnct = assnct + 100

PRINT
FOR i = 1 TO 100
PRINT array(i);
NEXT
PRINT : PRINT

PRINT compct, assnct

resulting in

` 734  580  621  360  371  797  112  784  833  738  140  472  876  811  436  965 884  150  954  427  572  790  148  633  521  368  660  683  337  351  846  842 630  987  919  304  725  982  319  580  195  999  708  114  617  190  192  818 356  141  366  443  370  953  981  461  350  244  246  681  469  471  741  393 669  286  267  625  172  512  915  335  806  441  360  927  668  664  485  188 604  725  922  851  120  589  924  487  710  552  562  516  418  464  342  150 319  981  154  451`
` 734  580  360  112  784  738  140  472  876  436  884  150  954  572  790  148 368  660  846  842  630  304  982  580  708  114  190  192  818  356  366  370 350  244  246  286  172  512  806  360  668  664  188  604  922  120  924  710 552  562  516  418  464  342  150  154  621  371  797  833  811  965  427  633 521  683  337  351  987  919  725  319  195  999  617  141  443  953  981  461 681  469  471  741  393  669  267  625  915  335  441  927  485  725  851  589 487  319  981  451`

where 100 comparisons were made, and 300 assignments; so there were fewer comparisons to make but more assignments.

The second version has the advantage that within even or odd numbers, the numbers themselves are in the same order in which they started.

 Posted by Charlie on 2013-12-18 13:09:55

 Search: Search body:
Forums (0)