There are many procedures for \"sorting\" a data set (arranging its items so tha
ID: 3760321 • 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.)
Explanation / Answer
package current;
import java.util.Stack;
public class BinSort {
public static void main(String[] args)
{
// display a welcome message
System.out.println("Unsorted array: ");
int arr[] = {40, 25, 656, 9999, 333, 7734, 8, 100, 99, 3321};
BinSort binsort = new BinSort();
binsort.printArr(arr);
int sortedArr[] = binsort.sort(arr);
System.out.println("sorted array: ");
binsort.printArr(sortedArr);
}
private Stack<Integer>[] bins;
private Stack<Integer> mainBin;
public BinSort() {
mainBin = new Stack<Integer>();
bins = (Stack<Integer>[]) new Stack[10];
for(int i =0; i <= 9; i++)
bins[i] = new Stack<Integer>();
}
void printArr(int arr[]) {
if(arr != null)
for(int i = 0; i < arr.length; i++)
System.out.print(arr[i]+" ");
System.out.println("");
}
int[] sort(int arr[]) {
int sortedArr[] = new int[arr.length];
try {
if(arr != null) {
//2. Place each of your (unsorted) data items onto the "main bin"
for(int 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) {
int num = 0;
int rem = 0;
while(!mainBin.isEmpty()) {
num = mainBin.pop();
// System.out.println("stack: pop: " + mainBin);
// System.out.print(num+" ");
if(position == 1)
rem = num %10;
else if(position == 2) {
rem = num / 10;
// System.out.println(" - "+rem+" - " ) ;
rem = rem % 10;
} else if(position == 3) {
rem = num / 100;
rem = rem % 10;
} else if(position == 4) {
rem = num / 1000;
}
// System.out.println(" - "+rem+" - ") ;
bins[rem].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.