5 Replies - 12234 Views - Last Post: 20 December 2009 - 08:37 PM Rate Topic: -----

#1 falconheart  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 8
  • Joined: 14-April 07

Finding the largest value in an unsorted array using recursion

Posted 14 April 2007 - 04:16 PM

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?

Is This A Good Question/Topic? 0
  • +

Replies To: Finding the largest value in an unsorted array using recursion

#2 William_Wilson  Icon User is offline

  • lost in compilation
  • member icon

Reputation: 205
  • View blog
  • Posts: 4,807
  • Joined: 23-December 05

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.
Was This Post Helpful? 0
  • +
  • -

#3 lifeRoot  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 23
  • Joined: 01-April 07

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 pseudo-code for quicksort:
http://en.wikipedia.org/wiki/Quicksort
Was This Post Helpful? 0
  • +
  • -

#4 falconheart  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 8
  • Joined: 14-April 07

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.

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?
Was This Post Helpful? 0
  • +
  • -

#5 falconheart  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 8
  • Joined: 14-April 07

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;
	}
}

Was This Post Helpful? 1
  • +
  • -

#6 rmitboy  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 53
  • Joined: 26-August 09

Re: Finding the largest value in an unsorted array using recursion

Posted 20 December 2009 - 08:37 PM

You are good at coding
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1