Lab 14 Problem 6 (name this Lab14_Problem6) This program will sort a one-dimensi
ID: 3913825 • Letter: L
Question
Lab 14 Problem 6 (name this Lab14_Problem6)
This program will sort a one-dimensional array using recursion. Design factors and hints follow. Remember, a recursive method calls itself until it's done—done is defined in this case as the array is sorted. If you can make one complete pass through the array without doing a single interchange, then you're done—it's sorted. That will help define your base case.
In main(), construct a one-dimensional array of 5 integer values. Use 3, 19, 4, 7, and 1. Populate it with shortcut notation.
Write a void() method to simply display the array, horizontally, with each value separated by a space.
Call the method to display the array within main(). You should see it in native order:
3 19 4 7 1
Now, write another void() method—this is your recursive method that will call itself until its done. It will partially sort the array, a little bit at a time, in ascending order during each recursive call. Design it to be called from main(), after your display method call, and pass it the array as an argument.
You recursive method should begin with the declarations and setup needed to traverse the array—but use a NON-NESTED for loop structure (not nested). As with a non-recursive sorting algorithm, perform an interchange whenever you find adjacent values are out of ascending order.
After your for loop ends, then write in your recursive "if-else" block. If you make it through the for loop without interchanging a single value, you're done. That's your base case. Execute the return statement. Otherwise, call the method again, passing it the array as an argument once again.
In main(), add another statement to display the array in its "after" state (i.e., sorted). Your array should now look like this:
1 3 4 7 19
Finally, modify your recursive and make it a value-returning method instead. Code it so that you return the number of iterations needed to perform the COMPLETE sortation, from start to finish. This may be tricky, but you've got skills. Think counter and inter-process communication. You'll figure it out. There are a few ways to do it.
Explanation / Answer
Here is the completed code for this problem. Developed this program in Java. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
// Lab14_Problem6.java
public class Lab14_Problem6 {
/**
* method to print the array
*/
static void print(int array[]) {
for (int i = 0; i < array.length; i++) {
System.out.printf(array[i] + " ");
}
System.out.println();
}
/**
* method to sort an array recursively and return the number of iterations
* (recursive calls) needed to sort it
*/
static int recursiveSort(int array[]) {
boolean done = true;// assuming the array is sorted
for (int i = 0; i < array.length - 1; i++) {
if (array[i] > array[i + 1]) {
// assumption was wrong
done = false;
// swapping elements
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
if (!done) {
// recursively calling again and returning +1 for the extra
// recursive call
return 1 + recursiveSort(array);
}
return 0; // array is sorted, no swapping was needed in this call
}
public static void main(String[] args) {
int array[] = { 3, 19, 4, 7, 1 }; // array
System.out.println("Before:");
print(array);
int iter = recursiveSort(array);
System.out.println("After:");
print(array);
System.out
.println(iter+ " iterations (recursive calls) needed for sorting above array");
}
}
/*OUTPUT*/
Before:
3 19 4 7 1
After:
1 3 4 7 19
4 iterations (recursive calls) needed for sorting above array
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.