01Knapsack in php

<?php
/* PHP is pass by value semantics.
   To pass by reference one uses the $& symbol for the
   parameters.
   Take the array of weights and array of benefits/value and
   try to infer the best possible combination for value M.
 */
    $b = array(50, 40, 30, 10);
    $w = array(3,   4,  6,  5);
    $b1 = array(4,   3,  6,  5);
    $w1 = array(3,   2,  5,  4);
    
    function listItems(array & $B, $n, $M)
    {
       $i = $n;
       $j = $M;  
       global $w, $b;
       $maxb = 0;
      
       while ($i > 0 && $j > 0)
       {
          if ($B[$i][$j] !=  $B[$i-1][$j])
          {
            print ("Take item number: $i ");
            echo "<BR/>\n";           
           
            $j = $j - $w[$i-1];
            $i = $i - 1;
            $maxb += $b[$i];
          }
          else 
            $i = $i - 1;
       }
       print ("Max benefit: $maxb ");
       echo "<BR/>\n";           
    }
   
    function printTable(array & $B, & $n, & $M)
    {
       $maxv = 0;
      
       $mw = 0;
       $mb = 0;
      
       for ($i = 0 ; $i <= $n; $i++)
       {
         for ($j = 0 ; $j <= $M; $j++)
         {
            printf("%02d ", $B[$i][$j]);
            if ($maxv < $B[$i][$j])
            {
               $mw = $i;
               $mb = $j;
               $maxv = $B[$i][$j];
            }           
         }
         echo "<BR/>\n";
       }
       echo "<BR/>\n";
      
       # Set the index where maximum exists
       $n = $mw;
       $M = $mb;
       printf("%02d \n", $B[$n][$M]); echo "<BR/>\n";
    }
   
    function knapsack01 (array & $w, array & $b, $M)
    {
        /* Two dimensional array to pre-compute */
        $B = array(array());
        $n = count($w);
       
        for ($indx = 0; $indx <= $n ; $indx++)
           $B[$indx][0] = 0;
  
        for ($indx = 0; $indx <= $M ; $indx++)
           $B[0][$indx] = 0;
      
        for ($i = 1; $i <= $n ; $i++)
        {
           for ($j = 0; $j <= $M ; $j++)
           {
              if ($w[$i-1] <= $j &&
                  ($B[$i-1][$j-$w[$i-1]] + $b[$i-1]) > $B[$i-1][$w[$i-1]])
              {
                 $B[$i][$j] = $B[$i-1][$j-$w[$i-1]] + $b[$i-1];             
              }
              else
                 $B[$i][$j] = $B[$i-1][$j];
           }
        }
        printTable ($B, $n, $M);
        listItems  ($B, $n, $M);
    }
   
    knapsack01 ($w, $b, 9);
?>

01 Knapsack in Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class KnapSack01 {
 
  List b = Arrays.asList(10, 40, 30, 50);
  List w = Arrays.asList(5, 4, 6, 3);
  private int B[][];
 
  public int getNum() { return w.size(); }
 
  public KnapSack01(int M)
  {
    doAlloc(w.size()+1, M+1);
    doAllot(w.size(), M+1);
    printTable(w.size()+1, M+1);
  }
 
  public static void main(String args[])
  {
    KnapSack01 ks = new KnapSack01(10);    
   
    ks.listItems(10);
  }
 
  public void listItems(int M)
  {
    int i = getNum();
    int k = M;
   
    while (i > 0 && k >0)
    {
      if (B[i][k] != B[i-1][k])
      {
        System.out.println(i + " is in the knapsack");
        i = i - 1;
        k = k - (int)w.get(i-1);
      }
      else
        i = i - 1;
    }
  }
 
  public void printTable(int n, int M)
  {
    for (int i = 0 ; i < n; i++)
    {
      for (int j = 0 ; j < M; j++)
        System.out.printf("%02d ", B[i][j]);
      System.out.println();
    }
  }
 
  public void doAlloc(int n, int M)
  {
    B  = new int[n][M];
   
    for (int i = 0 ; i < n; i++)
      B[i][0] = 0;
    for (int j = 0 ; j < M; j++)
      B[0][j] = 0;   
  }
 
  public void doAllot(int n, int M)
  {
    for (int i = 1 ; i <= n; i++)
    {
      for (int j = 0 ; j < M; j++) 
      {
        if ((int)w.get(i-1) <= j &&
            (((int)b.get(i-1) + B[i-1][j-(int)w.get(i-1)]) > B[i-1][(int)w.get(i-1)]))
        {
          B[i][j] = (int)b.get(i-1) + B[i-1][j-(int)w.get(i-1)];           
        }
        else
          B[i][j] = B[i-1][j];
      }     
    }
  }
}

Merging sorted arrays in Java

import java.util.Arrays;

public class MergingSortedArrays
{
  private int C[];
 
  public void doSpill()
  {
    System.out.println(Arrays.toString(C)); 
  }
 
  public MergingSortedArrays(int a[], int b[])
  {
    int i = 0, j = 0, k = 0;
   
    C = new int[a.length+b.length];
   
    while ( i < a.length || j < b.length)
    {
      System.out.println("Values: " + i + " " + j + " " +  k);
     
      if (i >= a.length)
      {
        C[k++] = b[j++];
      }
      else if (j >= b.length || a[i] < b[j])
      {
        C[k++] = a[i++];
      }
      else
      {
        C[k++] = b[j++];
      }
    }
  }
 
  public static void main(String args[])
  {
    int a[] = new int[] {8, 9, 9, 10, 10, 11, 12, 14};
    int b[] = new int[] {5, 6, 13, 37};
    MergingSortedArrays msr = new MergingSortedArrays(a,b);
   
    msr.doSpill();
  }
}

Merging sorted arrays in C

#include <stdio.h>
#include <stdlib.h>

/* Utility to spill the beans - print contents */
void spill(int *c, int len)
{
   int i;

   for (i = 0 ; i < len; i++)
      printf("%d ", c[i]);
   printf("\n");

}

/* The meat - If j index of second array crossed the maximum,
   of the second array, then populate with the first.
   Similarly, if the i index crossed the maximum of the first
   array, populate with the second.
   Else, populate the lesser of the two into the new array.
   For non-descending sort.
 */
int * mergesort(int A[], int la,  int B[], int lb)
{
    int i = 0, j = 0, k = 0;
    int *C = malloc(la + lb);

    while (i < la || j < lb)
    {
       if (j >= lb || (A[i] < B[j]))
       {
          C[k] = A[i];
          i++;
       }
       else
       {
          C[k] = B[j];
          j++;
       }
       k++;
    }
    return C;
}

int main()
{
    int A[] = {8, 9, 9, 10, 10, 11, 12, 14};
    int B[] = {5, 6, 13, 37};
    int *c;

    c = mergesort(A, sizeof(A)/sizeof(int), B, sizeof (B)/sizeof(B[0]));
    spill(c, sizeof(A)/sizeof(int) + sizeof (B)/sizeof(B[0]));
    return 0;
}

Linear sort for numbers in PHP

<?php
/* PHP is pass by value semantics.
   To pass by reference one uses the $& symbol for the
   parameters.
   Sorting numbers in a defined range 0 ... N-1 with no repeats
   Inspired from Programming Pearls : Jon Bentley
   O(n) linear cost.
   PHP does not support long bit arrays out of the box.
   Code assumption: 32-bits integer
 */
    $N = 1000000;
    $SHIFT = 5;
    $MASK  = 0x1f;
    $BITS  = 32;
    $TOPVAL = (1+$N/$BITS);
   
    function set (&$a, $i)
    {
       global $SHIFT;
       global $MASK;
      
       $shift = $i >> $SHIFT;   /* Which byte to set */
       $mask = $i & $MASK;      /* Which bit to set */
       $a[$shift] = $a[$shift] | (1 << $mask);
      
       return;
    }
   
    function get ($a, $i)
    {
       global $SHIFT, $MASK;
       return ( $a[$i >>$SHIFT] & (1 << ($i & $MASK)) );
    }
   
    function linearsort (array & $a)
    { 
        global $TOPVAL;
        $bitvec = [];
        $maxval = 0;
        $i = 0;
       
        for ($indx = 0; $indx < $TOPVAL ; $indx++)
        {
           $bitvec[$indx] = 0;
        }
       
       
        for ($indx = 0; $indx < count($a) ; $indx++)
        {
           if ($a[$indx] > $maxval) $maxval = $a[$indx];
              set($bitvec, $a[$indx]);
        }
         
        for ($indx = 0; $indx <= $maxval ; $indx++)
        {
           if (get($bitvec, $indx))
             $a[$i++] = $indx;
        }
    }

    $a = array(205, 10, 7, 5, 9, 8, 1, 2, 100);
    linearsort ($a);
    print_r ($a);
?>

Linear sort for range of numbers in Java

import java.util.BitSet;

/* Sorting numbers on disk
 * Linear sort
 * Inspired from Programming Pearls: Jon Bently
 * Java's ready availability of BitSet's makes
 * all the gory details of bit operations go away,
 * though essential.
 */
public class LinearPerfSort
{
  /* Printing routine */
  public void spill(int a[])
  {
    int indx;
    for (indx = 0 ; indx < a.length; indx++)
    {
      System.out.print(a[indx] + " ");
    }
    System.out.println();
  }
 
  public void doSort(int a[])
  {
    int indx= 0;
    BitSet bs = new BitSet(0);
   
    for (int i = 0; i < a.length; i++)
      bs.set(a[i]);
   
    for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1))
    {
      // guard on indx i here, just to guard from additional phony bits
      //if (indx < a.length) -- not required.
        a[indx++] = i;
    }
  }
 
  public static void main(String args[])
  {
    int arr[] = {205, 10, 7, 5, 9, 8, 1, 2, 100};
   
    LinearPerfSort lps = new LinearPerfSort();
    lps.doSort(arr);
    lps.spill(arr);
  } 
}

Linear sort for range of numbers in C

#include <stdio.h>
#include <stdlib.h>

/* Sorting numbers in a defined range 0 ... N-1 with
 * no repeats
 * Inspired from Programming Pearls : Jon Bently
 * O(n) linear cost.
 */

#define N           10000000
#define BITSPERWORD 32
#define SHIFT        5
#define TOPVAL      (1+N/BITSPERWORD)
#define MASK        0x1f
/* Above is same as mod operation, i%32 == i&5 */
/* Complete intent of mask is to guard against value
 * of 32 or above.
 */
#define set(i)    (bitvec[i >> SHIFT] |= (1<<(i&MASK)))
#define test(i)   (bitvec[i >> SHIFT] & (1<<(i&MASK)))

/* Printing routine */
void spill(int *a, int sz)
{
    int indx;
    for (indx = 0 ; indx < sz; indx++)
    {
        printf("%d ", a[indx]);
    }
    printf("\n");
}

void bitsort(int *a, int sz)
{
  int maxval = 0;
  int indx   = 0;
  int i = 0;

  int *bitvec = calloc(TOPVAL, sizeof(int));

  for (indx = 0; indx < sz ; indx++)
  {
     if (a[indx] > maxval) maxval = a[indx];
     set(a[indx]);
  }

  for (indx = 0; indx <= maxval ; indx++)
  {
     if (test(indx))
        a[i++] = indx;
  }

  free(bitvec);
}

int main()
{
  int arr[] = {205, 10, 7, 5, 9, 8, 1, 2, 100};
  bitsort(arr, 9);
  spill(arr,9);
}