Home › Topics › Algorithmic Profiling

Same Algorithmic Profile for Different Programming Paradigms

This page shows algorithmic profiles for two fundamentally different implementations of the Insertion Sort algorithm. The implementation on the left side is imperative, uses iteration, and a mutable data structure, while the implementation on the right side is functional, uses recursion and an immutable data structure.

The two profiles produced by AlgoProf, our Algorithmic Profiling prototype, show the same repetition tree (two repetitions in the harness, one repetition for constructing the data structure, and two repetitions grouped into the insertion sort algorithm) and the same asymptotic complexity.

Imperative, Iterative, Mutable Functional, Recursive, Immutable








Note: AlgoProf does not currently automatically fit cost functions to data points. We currently have to fit the red curves and add the cost functions to the legends manually. 
import java.util.Random;
 
public class Main  {
 
  public static void main(final String[] args) {
    new Main().measure();
  }
 
  private void measure() {
    System.out.println("Size\tComparisons");
    for (int size=0; size<100; size=size+10) {
        for (int i=0; i<3; i++) {
	  final List list = new List();
	  //constructReversed(list, size);
	  //construct(list, size);
	  constructRandom(list, size);
	  System.out.println(size);
	  sort(list);
	}
    }		
  }
 
  private void construct(List list, int size) {
    for (int i=0; i<size; i++) {
      list.append(i);
    }
  }
 
  private void constructReversed(List list, int size) {
    for (int i=0; i<size; i++) {
      list.append(9-i);
    }
  }
 
  private void constructRandom(List list, int size) {
    Random r = new Random();
    for (int i=0; i<size; i++) {
      list.append(r.nextInt(size));
    }
  }
 
  private void print(List list) {
    list.print();
  }
 
  private static void sort(List list) {
    list.sort();
  }	
}
//*******************************************
public class List {
 
  private Node head;
  private Node tail;
 
  public List() {
    head = null;
    tail = null;
  }
 
  public void append(int value) {
    final Node node = new Node(value);
    if (tail==null) {
      tail = node;
      head = tail;
    } else {
      tail.next = node;
      node.prev = tail;
      tail = tail.next;
    }
  }
 
  public void print() {
    Node node = head;
    while (node!=null) {
      System.out.print(node.getValue()+", ");
      node = node.next;
    }
     System.out.println();
  }
 
  public void sort() {
     if (head==null || head.next==null) {
      // empty or singleton -> sorted
      return;
     }
    Node firstUnsorted = head.next;
    while (firstUnsorted!=null) {
      Node target = firstUnsorted;
      Node nextUnsorted = firstUnsorted.next;
      while (target.prev!=null && 
                target.prev.value>target.value) {
        final Node candidate = target.prev;
	final Node pred = candidate.prev;
	final Node succ = target.next;
	if (pred!=null) {
	  pred.next = target;
	} else {
	  head = target;
	}
	target.prev = pred;
	if (succ!=null) {
	  succ.prev = candidate;
	} else {
	  tail = candidate;
	}
	candidate.next = succ;
	target.next = candidate;
	candidate.prev = target;
      }
      firstUnsorted = nextUnsorted;
    }
  }	
}
//*********************************************
public class Node {
 
  public Node prev;
  public Node next;
  public final int value;
 
  public Node(int value) {
    this.value = value;
  }	
  public int getValue() {
    return value;
  }
  public int compareTo(Node other) {
    return value-other.value;
  }
}
 
public class Main {
 
  private Cons cons = null;
  public static void main(String a[]){
    new Main().harness();
  }
 
  public void fillArray (int size, 
                               List cons) {
    if (size!=0) {
      fillArray(size, 
      new Cons((int)(Math.random()*1000), 
                            cons));
    } else {
      this.cons = (Cons)cons;
    }
  }
 
  public void harness() {
    int length = 1000;
    try {
      for (int i = 1; i<=length; i=i+1) {
        for (int j=0; j<3; j++) {
          fillArray(i, new Empty());
	  cons.sort();
	}
      }
    } catch (Exception e) {
      e.printStackTrace();
    }
  }
}
//*********************************
 
interface List {
  List sort();
  List insert(int x);
}
 
//*********************************
public class Empty implements List {
 
  public List sort() { return this; }
 
  public List insert(int x) {
    return new Cons(x, this);
  }	  
  public String toString() {return "Empty"; }
}
 
//*********************************
public class Cons implements List {
  int hd;
  List tl;
 
  Cons (int hd, List tl) { 
    this.hd=hd; 
    this.tl=tl; 
  }
 
  public List sort() {
    return tl.sort().insert(hd);
  }
 
  public List insert(int x){
    if (x <= hd)
      return new Cons(x,this);
    else
      return new Cons(hd,tl.insert(x));
  }
 
  public String toString() {
    return "Cons("+hd+","+tl.toString()+")"; 
  }
}