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

Home > Algorithms
Algorithm requested (Posted on 2013-12-18) Difficulty: 3 of 5
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.)
Some Thoughts 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (10)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information