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.
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 |
a couple of algorithms
