Flash Website Builder- Trendy Site Builder is a Flash Site Building tool that helps users build stunning websites. Check Out Custom Custom Logo Design by LogoBee. Website Design and Free Logo Templates available.
 CodingForums.com help with quicksort

Before you post, read our: Rules & Posting Guidelines

Enjoy an ad free experience by logging in. Not a member yet? Register.
 11-07-2010, 03:00 AM PM User | #1 orangegrundo New to the CF scene   Join Date: Nov 2010 Posts: 1 Thanks: 0 Thanked 0 Times in 0 Posts 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)); } }```

 Bookmarks

 Tags java, order statistic, quicksort, select

 Thread Tools Rate This Thread Rate This Thread: 5 : Excellent 4 : Good 3 : Average 2 : Bad 1 : Terrible

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home :: Client side development     JavaScript programming         DOM and JSON scripting         Ajax and Design         JavaScript frameworks         Post a JavaScript     HTML & CSS     XML     Flash & ActionScript         Adobe Flex     Graphics and Multimedia discussions     General web building         Site reviews         Building for mobile devices :: Server side development     Apache configuration     Perl/ CGI     PHP         Post a PHP snippet     MySQL         Other Databases     Ruby & Ruby On Rails     ASP     ASP.NET     Java and JSP     Other server side languages/ issues         ColdFusion         Python :: Computing & Sciences     Computer Programming     Computer/PC discussions     Geek News and Humour Web Projects and Services Marketplace     Web Projects         Small projects (quick fixes and changes)         Medium projects (new script, new features, etc)         Large Projects (new web application, complex features etc)         Unknown sized projects (request quote)         Vacant job positions         Looking for work/ for hire         Project collaboration/ partnership         Paid work offers and requests (Now CLOSED)     Career, job, and business ideas or advice     Domains, Sites, and Designs for sale         Domains for sale         Websites for sale         Design templates and graphics for sale :: Other forums     Member Offers     Forum feedback and announcements

All times are GMT +1. The time now is 05:47 PM.