| orangegrundo |
11-07-2010 02:00 AM |
help with quicksort
I'm trying to write an implementation of a quicksort-like solution to find the kth order statistic in a set, but I seem to have messed up my public static double select(double[] values, int p, int r,
int k) method. Does anyone know what im doing wrong?
Code:
// Select.java
// Randomized selection program
// Static method select takes an array of doubles, indices for a subarray,
// and finds the kth smallest element in that subarray.
import java.util.Scanner;
import java.text.DecimalFormat;
public class Select {
public static void main(String[] args) {
int n; // size of array
int k; // order statistic desired
double[] values; // the array
final double MAX_VALUE = 1000; // the largest possible value in the array
final int LINE_LENGTH = 10;
System.out.print("How large an array? ");
Scanner input = new Scanner(System.in);
n = input.nextInt();
values = new double[n];
// Fill in the array.
for (int i = 0; i < n; i++)
values[i] = Math.random() * MAX_VALUE;
// Print the array.
System.out.println("The array:");
DecimalFormat decFmt = new DecimalFormat("0.0000");
FieldFormat fldFmt = new FieldFormat(Integer.toString(
(int) Math.ceil(MAX_VALUE)).length() + 5);
for (int i = 0; i < n; i++) {
System.out.print(fldFmt.format(decFmt
.format(values[i])));
if (i % LINE_LENGTH == (LINE_LENGTH - 1) || i == n - 1)
System.out.println();
else
System.out.print(" ");
}
// Ask for k.
System.out.print("\nWhich order statistic do you want? ");
k = input.nextInt();
while (k < 1 || k > n) {
System.out.print("It must be between 1 and " + n
+ ": ");
k = input.nextInt();
}
double kthSmallest = select(values, 0, n - 1, k);
String ord;
if (k % 10 == 1 && k / 10 != 1)
ord = "st";
else if (k % 10 == 2 && k / 10 != 1)
ord = "nd";
else if (k % 10 == 3 && k / 10 != 1)
ord = "rd";
else
ord = "th";
System.out.println("The " + k + ord
+ " smallest value is "
+ decFmt.format(kthSmallest));
// Check our answer.
int smaller = 0;
int larger = 0;
int equal = 0;
for (int i = 0; i < n; i++) {
if (values[i] < kthSmallest)
smaller++;
else if (values[i] > kthSmallest)
larger++;
else
equal++;
}
if (smaller >= k)
System.out
.println("The answer is too large; it's the "
+ (smaller + equal) + "th smallest.");
else if (smaller + equal < k)
System.out
.println("The answer is too small; it's the "
+ (smaller + equal) + "th smallest.");
}
// Return the kth smallest element in the subarray values[p..r].
public static double select(double[] values, int p, int r,
int k) {
if (values.length == 1)
return values[0];
int q = partition(values, p, r);
int z = (q - p);
if (z == k)
return values[q];
else if (z > k)
return (select(values, q-1, p, k));
return (select(values,r, q+1, k - z));
}
// Swap two locations i and j in array a.
public static void swap(double[] a, int i, int j) {
double t = a[i];
a[i] = a[j];
a[j] = t;
}
// Partition a[p..r] into subarrays a[p..q-1] and a[q+1..r], where p <= q <= r, and
// each element of a[p..q-1] is less than or equal to a[q], which is less than
// each element of a[q+1..r].
// Works by randomly choosing an element of a[p..q], swapping this randomly
// chosen element (called the pivot) with a[r], and partitioning a[p..r]
// around the pivot.
// Returns the value of q that marks the partition.
public static int partition(double[] a, int p, int r) {
int s = p + ((int) (Math.random() * (r - p + 1)));
// Swap a[s] and a[r]. Remember what starts in a[s]
// (and ends up in a[r]) as the pivot value.
swap(a, r, s);
double pivot = a[r]; // the value we pivot around
int i = p - 1; // i is index into left side
// The following for loop maintains the following invariants:
// 1. Every element of a[p..i] is less than or equal to the pivot.
// 2. Every element of a[i+1..j-1] is greater than the pivot.
// 3. a[r] equals the pivot.
for (int j = p; j < r; j++) { // j is index into right side
// Find out which side a[j] goes into. If the left side, then we have
// to increment the size of the left side and then get a[j] into position i.
// If the right side, a[j] is already where we want it, so just
// incrementing j in the loop header suffices.
if (a[j] <= pivot) { // which side does a[j] go into?
i++; // if left side, make it one larger...
swap(a, i, j); // ...and get a[j] into the left side
}
}
// We dropped out of the loop because j == r. Every element of a[p..i]
// is less than or equal to the pivot, and every element of a[i+1..r-1]
// is greater than the pivot. If we put the pivot into position i+1, then
// we have what we want: a[p..i] is less than or equal to the pivot, a[i+1]
// equals the pivot, and a[i+2..r] is greater than the pivot.
swap(a, i + 1, r);
// Return the index of where the pivot ended up.
return i + 1;
}
}
// FieldFormat.java
// Class to format a String or integer type to a given field width.
public class FieldFormat {
enum Justify {left, right} // enum for left or right justification
int fieldWidth; // how many spaces in the field
char padChar; // character to pad with
Justify justification; // right or left justify
// Create a FieldFormat object, with a given field width, blank pad
// character, and right justification.
public FieldFormat(int width) {
fieldWidth = width;
padChar = ' ';
justification = Justify.right;
}
// Create a FieldFormat object, with a given field width and justification,
// and a blank pad character.
public FieldFormat(int width, Justify just) {
fieldWidth = width;
padChar = ' ';
justification = just;
}
// Create a FieldFormat object, with a given field width and pad character,
// and a right justification.
public FieldFormat(int width, char pad) {
fieldWidth = width;
padChar = pad;
justification = Justify.right;
}
// Create a FieldFormat object, with a given field width, pad character,
// and justification.
public FieldFormat(int width, char pad, Justify just) {
fieldWidth = width;
padChar = pad;
justification = just;
}
// Change a FieldFormat object's width.
public void applyWidth(int width) {
fieldWidth = width;
}
// Change a FieldFormat object's pad character.
public void applyPadChar(char pad) {
padChar = pad;
}
// Change a FieldFormat object's justification.
public void applyJustification(Justify just) {
justification = just;
}
// Format a String to a given width by adding the pad character
// to the appropriate side.
public String format(String s) {
int padSize = fieldWidth - s.length(); // how many pad characters to use
String padString = ""; // String used to pad
// Make padString be padSize pad characters.
for (int i = 0; i < padSize; i++)
padString += padChar;
// Return s with padString on the appropriate side.
return (justification == Justify.right ? padString : "")
+ s + (justification == Justify.right ? "" : padString);
}
// Format an integer value to a given width by adding the pad character
// to the appropriate side.
public String format(long s) {
return format(Long.toString(s));
}
}
|
