There are many procedures for \"sorting\" a data set (arranging its items so tha
ID: 3760448 • Letter: T
Question
There are many procedures for "sorting" a data set (arranging its items so that they are ordered from smallest to largest): Bin Sort, Quick Sort, Insertion Sort, Merge Sort, Heap Sort, etc. For this assignment, you will implement a "Bin Sort". You will use Stacks (you can use the built-in Stack class). BIN SORT RULES: --------------- 1. Consider a "main bin" (bucket). Consider 10 "sort bins" (buckets), i.e. sort bin#0 to sort bin#9. 2. Place each of your (unsorted) data items onto the "main bin". (For ease, assume that each data item will be no more than 4 numerical digits long, i.e. in the range 0 to 9999.) 3. MtoS procedure: Until the main bin is empty, repeatedly remove the top item. For each top item, look at the digit in the "ones" position (ie, rightmost digit). Place the item onto the top of the sort bin whose number matches the digit (e.g., if the data item is "456", then digit "6" is in the ones position, therefore place the data item "456" onto sort bin#6.) 4. StoM procedure: Until sort bin#9 is empty, repeatedly remove the top item. For each top item, place it onto the top of the main bin. Repeat that for sort bin#8, then sort bin#7, then sort bin#6, etc., then sort bin#0. 5. Repeat the MtoS procedure, but transfer data items based on the digit in the "tens" position instead. (If there is no explicit digit in the tens position, then the digit is 0. E.g., because 0001 is the same number as 1.) 6. Repeat the StoM procedure. 7. Repeat MtoS, but transfer based on the digit in the "hundreds" position. 8. Repeat StoM. 9. Repeat MtoS, but transfer based on the digit in "thousands" position. 10. Repeat StoM. 11. Since your data items were assumed to have 4 digits maximum, then you only need to do 4 "MtoS, StoM" routines. So, you can stop now. Your main bin now contains your data items, sorted from smallest (at top of the bin) to largest (at bottom of the bin). ---------------------------------------------------------------------- SPECS: ====== We discussed Stacks in the File Browser Program, and in the Maze Program. Now, you will use Stacks for sorting data. * Repeatedly ask the user to enter data values from 0 to 9999, until the user hits the ENTER key alone to stop the inputting. As each data value is inputted, store it onto the Stack representing your main bin. * Next, output the user's unsorted data, by outputting the Stack's contents. * Next, perform a "Bin Sort" on the user's data. This will arrange the data items from smallest to largest, in the "main bin". (The steps for a Bin Sort are explained in the prior section.) * Finally, output the main bin's contents, which now consists of the user's data in "sorted" order. (NOTE: If you use the one-line shortcut for outputting the main bin Stack, don't get surprised if the data looks like it's outputting from largest to smallest, rather than smallest to largest. The one-line shortcut for outputting a Stack prints from bottom to top of the stack, which in this case means largest data to smallest data. This is acceptable, despite the fact that it looks backwards on screen.) ------------------------------------------------------------------------ USEFUL JAVA COMMANDS: (similar to, but not necessarily identical to, the HW's) --------------------- (you may only need to use some of these) String s = "456789"; String t = s.substring(1,2); //t is "5" //i.e., we obtained the substring of s //which starts at string index 1, //and ends before (but not including) //string index 2. //NOTE: Java string indices start at 0, on the //left side of the string. int w = Integer.parseInt("100"); //w is the integer 100 char c = s.charAt(1); //c is '5' //i.e., we obtained the "char data-type" character //located at string index 1. int k = (int)c - (int)'0'; //convert character c='5' to integer k=5 String st = scan.nextLine(); if (st.equals("")) { System.out.println("You hit the ENTER key only"); } ---------------------------------------------------------------------- COMMENTS -------- There are various possible ways to do this assignment, including: 1. Inlined code (NOT RECOMMENDED FOR THIS ASSIGNMENT) -- one "main" routine only. Inlined code is more efficient in terms of speed and memory usage, but it can be complicated to read and debug. 2. Modular code, with parameter passing -- the "main" routine shares its "main bin" and "sort bins" with the MtoS and StoM subroutines, by passing the bins as parameters to the subroutines. (This is how many "professional" programmers would do this assignment, but it's somewhat messier than way #3 below.) 3. Modular code, without parameter passing -- the "main routine" shares its "main bin" and "sort bins" with the MtoS and StoM subroutines, by declaring the bins as global "class variables" accessible throughout the entire class.
Explanation / Answer
package current;
import java.util.Stack;
public class BinSortString {
public static void main(String[] args)
{
// display a welcome message
System.out.println("Unsorted array: ");
String arr[] = {"40", "25", "656", "9999", "333", "7734", "8", "100", "99", "3321"};
BinSortString binsort = new BinSortString();
binsort.printArr(arr);
String sortedArr[] = binsort.sort(arr);
System.out.println("sorted array: ");
binsort.printArr(sortedArr);
}
private Stack<String>[] bins;
private Stack<String> mainBin;
public BinSortString() {
mainBin = new Stack<String>();
bins = (Stack<String>[]) new Stack[10];
for(int i =0; i <= 9; i++)
bins[i] = new Stack<String>();
}
void printArr(String arr[]) {
if(arr != null)
for(int i = 0; i < arr.length; i++)
System.out.print(arr[i]+" ");
System.out.println("");
}
String[] sort(String arr[]) {
String sortedArr[] = new String[arr.length];
try {
if(arr != null) {
//2. Place each of your (unsorted) data items onto the "main bin"
for(String ele: arr) {
mainBin.push(ele);
}
//call MtoS and StoM 4 times, ie 4th most position
// your data items were assumed to have 4 digits maximum,
for(int i = 1; i <= 4; i++) {
MtoS(i);
StoM();
}
int i = 0;
while(mainBin != null && !mainBin.isEmpty()) {
sortedArr[i++] = mainBin.pop();
}
}
} catch(Exception e) {
System.out.println(e.getMessage());
e.printStackTrace();
}
return sortedArr;
}
//#3. MtoS procedure:
void MtoS(int position) {
//move based on units poistion
if(mainBin != null) {
String num = "";
char ch = ' ';
int index = 0;
while(!mainBin.isEmpty()) {
num = mainBin.pop();
if(position <= num.length()) {
ch = num.charAt(num.length()-position);
index= Character.getNumericValue(ch);
//System.out.println(num+", "+ch+", "+index);
} else {
index = 0;
}
bins[index].push(num);
}
}
}
//4. StoM procedure:
void StoM() {
if(bins != null) {
for(int i = 9; i >= 0; i--) {
while(bins[i] != null && !bins[i].isEmpty()) {
mainBin.push(bins[i].pop());
}
}
}
}
}
----------output--------------------------
Unsorted array:
40 25 656 9999 333 7734 8 100 99 3321
sorted array:
8 25 40 99 100 333 656 3321 7734 9999
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.