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);
}

Maximum segment sum in PHP

<?php
/* PHP is pass by value semantics.
   To pass by reference one uses the $& symbol for the
   parameters.
 */
    function maxsegsum (array $arr, $sz, &$beg, &$end)
    {  
       $maxe = $arr[0];          /* maximum ending here 
                              * cumulative sum */
       $maxs = $arr[0];          /* maximum so far */
       $beg_tmp = 0;
   
       for ($i = 1 ; $i < $sz ; $i++)
       {
          if ($maxe < 0)
          {
             $maxe = $arr[$i];   
             $beg_tmp = $i;
          }
          else
          {
             $maxe += $arr[$i];
          }
   
          if ($maxe >= $maxs)
          {
             $beg = $beg_tmp;
             $end = $i;
             $maxs = $maxe;   
          }
       }
       return $maxs;
    }

 $a = array(1, -2, 3, -2, 4);
 $beg = 0;
 $end = 0;
 $sum = maxsegsum ($a, 5, $beg, $end);
 
 print "Value of begin: $beg and value of end: $end <br>";
 print $sum;
?>

Maximum segment sum in Java

public class MaxSegSum
{
  private int beg_tmp, end, beg = 0;
 
  /* maxe = maximum ending here <=> cumulative sum
   * maxs = maximum so far
   */
  public int doSegSum(int a[], int sz)
  {
    int maxe = a[0], maxs = a[0];
    for (int i = 1 ; i < sz ; i++)
    {
       if (maxe < 0)
       {
         beg_tmp = i;
         maxe = a[i];
       }
       else
         maxe += a[i];
      
       if (maxe >= maxs)
       {
          maxs = maxe;
          beg = beg_tmp;
          end = i; 
       }
    }
    return maxs;
  }
 
  public static void main(String args[])
  {
    int A[] = {1, -2, 2, -1, 3, 4};
    System.out.println("value is " + new MaxSegSum().doSegSum(A, 6));
  } 
}

Maximum Segment Sum in C

Given a list of numbers, the task is to compute the largest possible sum of a consecutive segment.


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

#define max(a,b)  ((a) > (b) ? (a) : (b))

/* Order of algorithm O(n^2) */
int maxsegsumO2(int a[], int sz)
{
    int maxtillnow = 0, maxsofar = 0;
    int i,j;

    for (i = 0; i < sz; i++)
    {
        maxtillnow = 0;
        for (j = i ; j < sz; j++)
        {
           maxtillnow = max(0,a[j]+maxtillnow);
           maxsofar = max(maxtillnow,maxsofar);
        }
        printf("%5d, %5d\n", maxtillnow, maxsofar);

    }
    return maxsofar;
}

/* Order of algorithm O(n) */
int maxsegsumO1(int a[], int sz)
{
    int maxtillnow = a[0],  maxsofar = a[0];
    int i, begin, end, begin_tmp;

    for (i = 1; i < sz; i++)
    {
        if (maxtillnow < 0)
        {
           begin_tmp = i;
           maxtillnow = a[i];
        }
        else
           maxtillnow += a[i];

        if (maxtillnow >= maxsofar)
        {
           maxsofar = maxtillnow;
           begin = begin_tmp;
           end = i;
        }
        /*
        maxtillnow = max(0,a[i]+maxtillnow);
        printf("%5d, %5d\n", maxtillnow, maxsofar);
        maxsofar = max(maxtillnow,maxsofar);
        */
    }

    printf("%d, %d\n", begin, end);
    return maxsofar;
}

int main()
{
   //int A[] = {3, 4, 5, -40, -20, 21, 25, 29, 31, 35};
 //  int A[] = {2, -3, 4, -1, 3};
   int A[] = {-2, -3, 4, -1, -2, 1, 5, -3};

   printf ("max seg sum: %d\n", maxsegsumO2(A, sizeof(A)/sizeof(int)));
   printf ("max seg sum: %d\n", maxsegsumO1(A, sizeof(A)/sizeof(int)));

   return 0;
}