I'm a CS student and my current assignment is to write a program that will find the largest value in an unsorted array of integers using a recursive divide & conquer algorithm. The concept is straightforward enough, but I'm having trouble with the implementation.
From the diagram I get the idea that you use a helper function to find the larger of two numbers, to determine what to return in the next recursive call. That's simple enough to write. But I don't know how to divide & conquer an array that is unsorted. I'm also not sure what to write for a base case. Can someone help me out here?
5 Replies  12266 Views  Last Post: 20 December 2009  08:37 PM
#1
Finding the largest value in an unsorted array using recursion
Posted 14 April 2007  04:16 PM
Replies To: Finding the largest value in an unsorted array using recursion
#2
Re: Finding the largest value in an unsorted array using recursion
Posted 14 April 2007  04:25 PM
i would suggest using a prototype of:
public int largest(int[] array, int current_index, int size_of_array, int max){
these values if incremented properly allow you to traverse the array, and you have a base case of when current_index == size_of_array, then return the max int.
public int largest(int[] array, int current_index, int size_of_array, int max){
these values if incremented properly allow you to traverse the array, and you have a base case of when current_index == size_of_array, then return the max int.
#3
Re: Finding the largest value in an unsorted array using recursion
Posted 15 April 2007  05:45 AM
This article might help you...
it gives some pseudocode for quicksort:
http://en.wikipedia.org/wiki/Quicksort
it gives some pseudocode for quicksort:
http://en.wikipedia.org/wiki/Quicksort
#4
Re: Finding the largest value in an unsorted array using recursion
Posted 16 April 2007  03:16 PM
Thank you everyone for your input. However I am still stuck. My problem isn't that I am unable to accomplish the task of finding the largest integer in an array. It's doing it the specific way they want me to do it that is giving me fits. I could do it from one end to the other, and retain the max value that would be relatively simple. A recursive version of the bubblesort, as it were. But they want me to specifically divide & conquer, recursively, using a helper function to determine the largest of two values, an unsorted array of integers. I even have the pseudocode I just can't think of any ways to impliment it. Here I'll type the pseudocode for you.
So I understand the concept.. You divide the array in half every recursive call until you are left with essentially all the individual values, which are then compared 2 by 2 using the helper function, each returning the max to the next level above it, until the max value rises to the top. I can describe it, I can tell you the process but I can't DO it for the life of me! lol Maybe I'm just overlooking the painfully obvious (wouldnt be the first time) but can someone please help me figure out how to implement this?
if (anarray has only one item) maxArray(anarray) is the item in anarray else if (anarray has more than one item) maxArray(anarray) is the maximum of maxArray(left half of anarray) and maxArray(right half of anarray)
So I understand the concept.. You divide the array in half every recursive call until you are left with essentially all the individual values, which are then compared 2 by 2 using the helper function, each returning the max to the next level above it, until the max value rises to the top. I can describe it, I can tell you the process but I can't DO it for the life of me! lol Maybe I'm just overlooking the painfully obvious (wouldnt be the first time) but can someone please help me figure out how to implement this?
#5
Re: Finding the largest value in an unsorted array using recursion
Posted 20 April 2007  03:35 PM
I  finally  did it. I'm so happy. I thought I'd go ahead and post the code here if anyone else has problems like this.
#include <iostream> using std::cout; using std::endl; const int arraysize = 10; int anArray[arraysize] = {100, 12, 89, 17, 33, 7, 97, 2, 4, 105}; int maxArray(int, int, int); int max(int, int); main() { cout << "The largest value in anArray is: " << maxArray(arraysize, 0, (arraysize  1)) << endl; system("PAUSE"); return 0; } int maxArray(int arraycount, int first, int last) { if (arraycount==1) return max(anArray[first], anArray[last]); else if(arraycount>1) return max(maxArray((arraycount /2), first, (first + last) / 2), maxArray((arraycount /2), (first + last) /2, last)); } max(int x, int y) { if (x > y) { return x; } else { return y; } }
#6
Re: Finding the largest value in an unsorted array using recursion
Posted 20 December 2009  08:37 PM
You are good at coding
Page 1 of 1
