Sample IC Programs

We encourage students to write their own programs, but here are two programs to get people started:

• Quicksort
• Sieve

Quicksort.ic

class Quicksort {
    int[] a;
    
    int partition(int low, int high) {
	int pivot = a[low];
	int i = low; 
	int j = high;
	int tmp;

	while (true) { 
	    while (a[i] < pivot) i = i+1;
	    while (a[j] > pivot) j = j-1;
	    
	    if (i >= j) break;
	    
	    tmp = a[i];
	    a[i] = a[j]; 
	    a[j] = tmp;
	    i = i+1;
	    j = j-1;
	} 
	
	return j;
    }

    void quicksort(int low, int high) {
	if (low < high) {
	    int mid = partition(low, high);
	    quicksort(low, mid);
	    quicksort(mid+1, high);
	}
    }

    void initArray(int n) {
	a = new int[n];
	int i = 0;
	while(i < n) {
	    a[i] =  Library.random(a.length*2);
	    i = i+1;
	}
    }

    void printArray() {
	Library.print("Array elements: ");
	int i = 0;
	while(i < a.length) {
	    Library.printi(a[i]);
	    Library.print (" ");
	    i = i + 1;
	}
	Library.print("\n");
    }
}

class Main {
    static void main(string[] args) {
	if (args.length != 1) {
	    Library.println("Unspecified array length");
	    Library.exit(1);
	}

	int n = Library.stoi(args[0], -1);
	if (n <= 0) {
	    Library.println("Invalid array length");
	    Library.exit(1);
	}

	Quicksort qs = new Quicksort();
	qs.a = new int[n];
	qs.initArray(n);
	qs.printArray();
	qs.quicksort(0, n-1);
	qs.printArray();
    }
}

Back to top

---

Sieve.ic

class Sieve {
    
    static int[] initArray(int n) {
        int[] a = new int[n];
        int i = 0;
        while (i < a.length) {
            a[i] = i;
            i = i + 1;
        }
        return a;
    }
    
    static void sieveAll(int[] a) {
        int i = 2;
        while (i < a.length) {
            sieve(a, i);
            i = i + 1; 
        }
    }
    
    static void sieve(int[] a, int n) {
        int i = 2*n;
        while (i < a.length) {
            a[i] = 0;
            i = i + n;
        }
    }
    
    static void printPrimes(int[] a) {
        int i = 2;
        Library.print("Primes less than ");
        Library.printi(a.length);
        Library.print(": ");
        while (i < a.length) {
            if (a[i] != 0) {
                Library.printi(a[i]);
                Library.print(" ");
            }
            i = i + 1;
        }
    }
    
    
    static void main(string[] args) {
        if (args.length != 1) {
            Library.println("Please provide a number.");
            Library.exit(1);
        }
        
        Library.println("");
        int n = Library.stoi(args[0], -1);
        if (n <= 0) {
            Library.println("Invalid array length");
            return;
        }
        
        int[] a = initArray(n);
        sieveAll(a);
        printPrimes(a);
        Library.println("");
    }
}

Back to top

---