<repo_name>zjuchenlong/Coding<file_sep>/java/algorithms/ch2/SelectionSort.java
package ch2;

import edu.princeton.cs.algs4.*;

public class SelectionSort {

	public static void sort(Comparable[] a)
	{//sort a[] into increasing order
		int N = a.length;
		for(int i=0;i< N;i++)
		{
			int min = i;
			for(int j=i+1; j< N;j++)
				if(less(a[j], a[min]))
					min = j;
			exch(a, i, min);
		}
	}
	
	private static boolean less(Comparable w, Comparable v)
    {
    	return w.compareTo(v) < 0;
    }
    
    private static void exch(Comparable[] a, int i, int j)
    {
    	Comparable temp = a[i];
    	a[i] = a[j];
    	a[j] = temp;
    }
    
    private static void show(Comparable[] a)
    {
    	for(int i=0;i<a.length;i++)
    		System.out.print(a[i]+" ");
    	System.out.println(" ");
    }
    
    private static boolean isSorted(Comparable[] a)
    {
    	for(int i=1;i<a.length;i++)
    	    if(less(a[i], a[i-1]))
    	    	return false;
    	return true;
    }
    
	public static void main(String[] args)
	{
		String[] a = In.readStrings();
		sort(a);
		assert isSorted(a);
		show(a);
	}
	
}
<file_sep>/java/algorithms/ch1/Bag.java
package ch1;

import java.util.Iterator;
import edu.princeton.cs.algs4.StdIn;

public class Bag<Item> implements Iterable<Item> {

	private Node first;
	private int N;
	
	private class Node
	{
		Item item;
		Node next;
	}
	
	public void add(Item item)
	{
		Node oldfirst = first;
		first = new Node();
		first.item = item;
		first.next = oldfirst;
		N++;
	}
	
	public int size()
	{
		return N;
	}
	
	public Iterator<Item> iterator()
	{
		return new listIterator();
	}
	
	private class listIterator implements Iterator<Item>
	{
		private Node current = first;
		public boolean hasNext() {return current!=null;}
		public Item next()
		{
			Item item = current.item;
			current = current.next;
			return item;
		}
		public void remove() {}
	}
	
	public static void main(String[] args)
	{
		Bag<Double> bag = new Bag<Double>();
		while(!StdIn.isEmpty())
		{
			bag.add(StdIn.readDouble());
		}
		
		double sum = 0.0;
		for(double i:bag)
		{
			sum += i;
			System.out.println(i);
		}
		System.out.println("Sum of the number are "+sum);
	}
}
<file_sep>/java/algorithms/ch1/UFQuickUnion.java
package ch1;

import edu.princeton.cs.algs4.StdIn;

public class UFQuickUnion {
    private int[] id; // id store the root number of this node
    private int count;
    
    public UFQuickUnion(int N)
    {
    	count = N;
    	id = new int[N];
    	for(int i=0;i<N;i++)
    		id[i] = i;
    }
    
    public int count() {return count;}
    
    public boolean connected(int p, int q)
    {
    	return find(p) == find(q);
    }
    
    //for the worst case, the number of array access is 1 plus 
    // twice the depth of the node corresponding to the given site
    public int find(int p) 
    {
    	while(p != id[p])
    		p = id[p];
    	return p;
    }
    
    public void union(int p, int q) 
    {
    	int pRoot = find(p);
    	int qRoot = find(q);
    	if(pRoot == qRoot)    return;
    	
    	id[pRoot] = qRoot;
    	count--;
    }
    
    public static void main(String[] args)
    {
    	int N = StdIn.readInt();
    	UFQuickUnion uf = new UFQuickUnion(N);
    	while(!StdIn.isEmpty())
    	{
    		int p = StdIn.readInt();
    		int q = StdIn.readInt();
    		if(uf.connected(p, q))
    			continue;
    		uf.union(p,q);
    		System.out.println(p + " " + q);
    	}
    	System.out.println(uf.count() + " components.");
    }
}
<file_sep>/java/algorithms/ch2/ShellSort.java
package ch2;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.In;

public class ShellSort {
	
	public static void sort(Comparable[] a)
	{
		int N = a.length;
		int  h =1;
		while(h < N/3)
			h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
		while(h >= 1)
		{ //h-sort the array
			for(int i=h; i<N; i++)
			{
				for(int j=i; j >=h && less(a[j], a[j-h]); j -=h)
					exch(a, j, j-h);
			}
			h = h/3;
		}
	}

	private static boolean less(Comparable w, Comparable v)
	{
		return w.compareTo(v) < 0;
	}
	
	private static void exch(Comparable[] a, int i, int j)
	{
		Comparable temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
	private static boolean isSorted(Comparable[] a)
	{
		for(int i=1;i<a.length;i++)
			if(less(a[i], a[i-1]))
				return false;
		return true;
	}
	
	private static void show(Comparable[] a)
	{
		for(int i=0;i<a.length;i++)
			System.out.print(a[i]+" ");
		System.out.println(" ");
	}
	
	public static void main(String[] args)
	{
		String[] a = In.readStrings();
		sort(a);
		assert isSorted(a);
		show(a);
	}
}
<file_sep>/python/sparse/sparse_csr_matrix.py
import numpy as np

def matrix2csr(matrix):

    assert matrix.ndim == 2, "matrix convert to csr_matrix should be 2 dimension"
    data = []
    indices = []
    indptr = []

    indptr.append(0)
    for row in matrix:
        for index, elem in enumerate(row):
            if elem != 0:
                data.append(elem)
                indices.append(index)
        indptr.append(len(indices))

    return np.array(data), np.array(indices), np.array(indptr)

# there is no shape parameter, so the shape is derived from indices
def csr2matrix(data, indices, indptr):
   
    assert len(data) == len(indices), "data lenght should same as indices"
    row_num = len(indptr) - 1
    col_num = np.max(indices) + 1  # because col i index is start from 0
    rval = np.zeros((row_num, col_num), dtype = data.dtype)

    for row_index in xrange(row_num):
       rval[row_index, indices[indptr[row_index]:indptr[row_index + 1]]] \
         = data[indptr[row_index]:indptr[row_index + 1]]

    return rval

mat = np.array([[1, 0, 2], [0, 0, 3], [4, 5, 6]])
print mat
data, indices, indptr = matrix2csr(mat)
recover = csr2matrix(data, indices, indptr)
print recover
