Benchmarking - Java

Use Java Timing libraries.

java.lang

static long     nanoTime() - Returns the current value of the running JVM's high-resolution time source, in nanoseconds.

Merge sort - Java

Basic algorithm:
1. If list has one element, return;
2. Divide list in half
3. Sort first half
    Sort second half    (use recursion)
4. Merge sorted lists.

Best = Worst = O(nlogn)

Quick sort best = average = O(nlogn), worst = O(n^2)

Regular Expression

"a*" - zero or more a
"a+" - 1 or more a's
"[a-f]" - Any character between a and f
"[^a-cz]" - Any character which is not between a and c, and not z
"[abc]+" - 1 or more of a, b or c in a row
"abc" - character abc in a row
"a|b" - Character a or character b

Java:
java.util.regex
java.util.regex.Matcher;
java.util.regex.Pattern;

protected List getTokens(String pattern)
 {
  ArrayList tokens = new ArrayList();
  Pattern tokSplitter = Pattern.compile(pattern);
  Matcher m = tokSplitter.matcher(text);
  
  while (m.find()) {
   tokens.add(m.group());
  }
  
  return tokens;
 }

Python projects

Schema

Geocoding:

PageRank:

Gmane:

Insertion sorting - Java

Insertion sorting:

 public static void insertionSort( int[] vals ) {
  int currInd;
  for (int pos=1; pos < vals.length; pos++) {
   currInd = pos;
   while (currInd > 0 && vals[currInd] < vals[currInd-1] ) {
    swap(vals, currInd, currInd-1);
    currInd--;
   }
  }
 }

Best: O(n)
Worst: O(n^2)

Java Built-in Sorting

Mergesort

import java.util.*;

public class MyBuiltInSortingTest {
    public static void main (String[] args) {
        Random random = new Random();
        List numsToSort = new ArrayList();
        
        for (int i=0; i < 5; i++) {
            numsToSort.add( random.nextInt(100) );
        }
        
        Collection.sort(numsToSort);
        System.out.println("New array after builtin sort: " + numsToSort.toString());
    }
}

Seletion Sort - Java

Steps:
Find smallest element, swap it with element at location 0;
Find next smallest element, swap it with element at location 1;
etc.

public static void selectionSort( int[] vals ) {
    int indexmin;

    for (int i = 0; i < vals.length-1; i++) {
        indexmin = i;
        for (int j = i+1; j < vals.length-2; j++) {
            if (vals[j] < vals[indexmin]) { indexmin = j; }
        }
        swap( vals, indexmin, j );
    }
}

Correctness:
Left array is always sorted.

Performance:
Time: O(n^2)
Space: O(1)

Note:
Not sensitive to already almost sorted array (takes same amount of time)
So Best = Worst = O(n^2)