Computer Science/61b/Homework/hw10/sort/Sorts.java

This page contains computer code. Unlike all articles on the lensowiki, which are released under the GFDL, this code is released under the GPL.

Copyright 2006, 2007 Paul Borokhov. All rights reserved.

This code is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

The code is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

/* Sorts.java */

package sort;

public class Sorts {
	
	/**
	 *  Place any final static fields you would like to have here.
	 **/
	public static final int NOOFDIGITS = 7;
	public static final int DIGITSIZE = 4;
	public static final int BUCKETLENGTH = 16; // 2^DIGITSIZE
	public static final int BITMASK = 15; // binary 1111
	
	/**
	 *  countingSort() sorts an array of int keys according to the
	 *  values of one of the base-16 digits of each key.  "whichDigit"
	 *  indicates which digit is the sort key.  A zero means sort on the least
	 *  significant (ones) digit; a one means sort on the second least
	 *  significant (sixteens) digit; and so on, up to a seven, which means
	 *  sort on the most significant digit.
	 *  @param key is an array of ints.  Assume no key is negative.
	 *  @param whichDigit is a number in 0...7 specifying which base-16 digit
	 *    is the sort key.
	 *  @return an array of type int, having the same length as "keys"
	 *    and containing the same keys sorted according to the chosen digit.
	 *
	 *    Note:  Return a newly created array.  DO NOT CHANGE THE ARRAY keys.
	 **/
	public static int[] countingSort(int[] keys, int whichDigit) {
		int[] newarr = new int[keys.length];
		int[] buckets = new int[BUCKETLENGTH];
		for (int i = 0; i < keys.length; i++) {
			buckets[((keys[i] >> (whichDigit*DIGITSIZE)) & BITMASK)]++;
		}
		int total = 0;
		for (int j = 0; j < buckets.length; j++) {
			int c = buckets[j];
			buckets[j] = total;
			total = total + c;
		}
		for (int i = 0; i < keys.length; i++) {
			newarr[buckets[((keys[i] >> (whichDigit*DIGITSIZE)) & BITMASK)]] = keys[i];
			buckets[((keys[i] >> (whichDigit*DIGITSIZE)) & BITMASK)]++;
		}
		return newarr;
	}
	
	/**
	 *  radixSort() sorts an array of int keys (using all 32 bits
	 *  of each key to determine the ordering).
	 *  @param key is an array of ints.  Assume no key is negative.
	 *  @return an array of type int, having the same length as "keys"
	 *    and containing the same keys in sorted order.
	 *
	 *    Note:  Return a newly created array.  DO NOT CHANGE THE ARRAY keys.
	 **/
	public static int[] radixSort(int[] keys) {
		int[] returnarr = keys;
		for (int i=0; i<=NOOFDIGITS; i++) {
			returnarr = countingSort(returnarr, i);
		}
		return returnarr;
	}
	
	/**
	 *  yell() prints an array of int keys.  Each key is printed in hexadecimal
	 *  (base 16).
	 *  @param key is an array of ints.
	 **/
	public static void yell(int[] keys) {
		System.out.print("keys are [ ");
		for (int i = 0; i < keys.length; i++) {
			System.out.print(Integer.toString(keys[i], 16) + " ");
		}
		System.out.println("]");
	}
	
	/**
	 *  main() creates and sorts a sample array.
	 *  We recommend you add more tests of your own.
	 *  Your test code will not be graded.
	 **/
	public static void main(String[] args) {
		int[] keys = { Integer.parseInt("60013879", 16),
			Integer.parseInt("11111119", 16),
			Integer.parseInt("2c735010", 16),
			Integer.parseInt("2c732010", 16),
			Integer.parseInt("7fffffff", 16),
			Integer.parseInt("4001387c", 16),
			Integer.parseInt("10111119", 16),
			Integer.parseInt("529a7385", 16),
			Integer.parseInt("1e635010", 16),
			Integer.parseInt("28905879", 16),
			Integer.parseInt("00011119", 16),
			Integer.parseInt("00000000", 16),
			Integer.parseInt("7c725010", 16),
			Integer.parseInt("1e630010", 16),
			Integer.parseInt("111111e5", 16),
			Integer.parseInt("61feed0c", 16),
			Integer.parseInt("3bba7387", 16),
			Integer.parseInt("52953fdb", 16),
			Integer.parseInt("40013879", 16) };
		
		yell(keys);
		keys = radixSort(keys);
		yell(keys);
	}
}