Lensovet: Lensovet moved page CS/61b/Homework/hw10/sort/Sorts.java to Computer Science/61b/Homework/hw10/sort/Sorts.java

2023-02-20T03:51:34Z

Lensovet moved page CS/61b/Homework/hw10/sort/Sorts.java to Computer Science/61b/Homework/hw10/sort/Sorts.java

Lensovet: moved CS 61b/Homework/hw10/sort/Sorts.java to CS/61b/Homework/hw10/sort/Sorts.java: fix cs 61b hierarchy

2010-11-14T06:00:19Z

moved CS 61b/Homework/hw10/sort/Sorts.java to CS/61b/Homework/hw10/sort/Sorts.java: fix cs 61b hierarchy

Lensovet: formatting

2007-09-22T06:52:20Z

formatting

Lensovet at 06:51, 22 September 2007

2007-09-22T06:51:51Z

New page

{{code}}
/* 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);
}
}

← Older revision	Revision as of 03:51, 20 February 2023
(No difference)

← Older revision	Revision as of 06:00, 14 November 2010
(No difference)

@@ Line 16: / Line 16: @@
   	/**
   	 *  countingSort() sorts an array of int keys according to the
-  	 *  values of _one_ of the base-16 digits of each key.  "whichDigit"
+  	 *  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

Computer Science/61b/Homework/hw10/sort/Sorts.java - Revision history

Lensovet: Lensovet moved page CS/61b/Homework/hw10/sort/Sorts.java to Computer Science/61b/Homework/hw10/sort/Sorts.java

Lensovet: moved CS 61b/Homework/hw10/sort/Sorts.java to CS/61b/Homework/hw10/sort/Sorts.java: fix cs 61b hierarchy

Lensovet: formatting

Lensovet at 06:51, 22 September 2007