recursive method

my last method is in need of severe help.

Page 1 of 1

3 Replies - 1044 Views - Last Post: 10 March 2010 - 10:55 PM Rate Topic: -----

#1 drowninggirl  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 21-January 10

recursive method

Posted 10 March 2010 - 05:07 PM

import java.util.*;

/********************************************************************
 * Class for sorting an array of Comparable objects from smallest to
 * largest.
 *
 * This code is based on code from Chapter 11 and 12 of
 * Data Structures and Abstractions with Java 2/e
 *      by Carrano 
 *      
 *Summer Brown
 ********************************************************************/


public class SortArray
{

	/**************************************************************
	 * ITERATIVE SELECTION SORT
	 **************************************************************/


	/** Task: Sorts the first n objects in an array into ascending order.
	 * @param a an array of Comparable objects
	 * @param n an integer > 0 
	 */
	public static <T extends Comparable<? super T>>
	void selectionSort(T[] a, int n)
	{   
		for (int index = 0; index < n - 1; index++)
		{
			int indexOfNextSmallest = getIndexOfSmallest(a, index, n-1);
			swap(a, index, indexOfNextSmallest);
			// Assertion: a[0] <= a[1] <= . . . <= a[index] <= all other a[i]
		} // end for
	} // end selectionSort


	/** Task: Finds the index of the smallest value in an array.
	 * @param a an array of Comparable objects
	 * @param first an integer >= 0 that is the index of the first
	 * array element to consider
	 * @param last an integer >= 0 that is the index of the last
	 * array element to consider
	 * @return the index of the smallest value among
	 * a[first], a[first+1], . . . , a[last] 
	 */
	public static <T extends Comparable<? super T>>
	int getIndexOfSmallest(T[] a, int first, int last)
	{
		T min = a[first];
		int indexOfMin = first;
		for (int index = first+1; index <= last; index++)
		{
			if (a[index].compareTo(min) < 0)
			{
				min = a[index];
				indexOfMin = index;
				// Assertion: min is the smallest of a[first] through a[index].
			} // end if
		} // end for
		return indexOfMin;
	} // end getIndexOfSmallest


	/** Task: Swaps the array elements a[i] and a[j].
	 * @param a an array of  objects
	 * @param i an integer >= 0 and < a.length
	 * @param j an integer >= 0 and < a.length 
	 * 
	 * Modified from Carrano to use generics.
	 */
	private static <T>
	void swap(T[] a, int i, int j)
	{
		T temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	} // end swap



	/**************************************************************
	 * ITERATIVE INSERTION SORT
	 **************************************************************/


	/** Task: Sorts the first n objects in an array into ascending order.
	 * @param a an array of Comparable objects
	 * @param n an integer > 0 
	 */
	public static <T extends Comparable<? super T>>
	void insertionSort(T[] a, int n)
	{   
		insertionSort(a, 0, n-1);
	} // end insertionSort



	/** Task: Iterative insertion sort of the  objects in a range of locations in an array into ascending order.
	 * @param a an array of Comparable objects
	 * @param first an integer >= 0
	 * @param last an integer > first and < a.length
	 */    

	public static <T extends Comparable<? super T>>
	void insertionSort(T[] a, int first, int last)
	{
		T temp;
		boolean foundLocation;
		int loc;

		for ( int i = first+1; i<= last; i++)
		{
			temp = a[i]; 

			// move values over to make room
			loc = i-1;  // start with value to the left
			foundLocation = false;
			while(loc >= first  && !foundLocation)
			{
				if(a[loc].compareTo(temp) > 0)
				{
					a[loc+1]  = a[loc];
					loc--;
				}
				else
					foundLocation = true;  // found the spot
			}

			// put the value in the right place  
			a[loc+1] = temp;
		} // end for
	} // end insertionSort



	/**************************************************************
	 * ITERATIVE SHELL SORT
	 **************************************************************/

	/** Task: Sorts the first n objects in an array into ascending order.
	 * @param a an array of Comparable objects
	 * @param n an integer > 0 
	 */
	public static <T extends Comparable<? super T>>
	void shellSort(T[] a, int n)
	{   
		shellSort(a, 0, n-1);
	} // end shellSort


	/** Task: Use incremental insertion sort with different increments to 
	 * sort a range of values in the array
	 * @param a an array of Comparable objects
	 * @param first an integer >= 0
	 * @param last an integer > first and < a.length
	 */    
	public static <T extends Comparable<? super T>>
	void shellSort(T[] a, int first, int last)
	{
		int n = last - first + 1; // number of array elements
		for (int space = n/2; space > 0; space = space/2)
		{
			for (int begin = first; begin < first + space; begin++)
				incrementalInsertionSort(a, begin, last, space);
		} // end for
	} // end shellSort


	/** Task: Sorts equally spaced elements of an array into
	 * ascending order.
	 * @param a an array of Comparable objects
	 * @param first an integer >= 0 that is the index of the first
	 * array element to consider
	 * @param last an integer >= first and < a.length that is the
	 * index of the last array element to consider
	 * @param space the difference between the indices of the
	 * elements to sort 
	 */
	public static <T extends Comparable<? super T>>
	void incrementalInsertionSort(T[] a, int first, int last, int space)
	{
		int unsorted, index;
		for (unsorted = first + space; unsorted <= last;
		unsorted = unsorted + space)
		{
			T firstUnsorted = a[unsorted];
			for (index = unsorted - space; (index >= first) &&
			(firstUnsorted.compareTo(a[index]) < 0);
			index = index - space)
			{
				a[index + space] = a[index];
			} // end for
			a[index + space] = firstUnsorted;
		} // end for
	} // end incrementalInsertionSort


	/**************************************************************
	 * MERGE SORT
	 **************************************************************/


	/** Task: Sorts the first n objects in an array into ascending order.
	 * @param a an array of Comparable objects
	 * @param n an integer > 0 
	 */
	public static <T extends Comparable<? super T>>
	void mergeSort(T[] a, int n)
	{   
		mergeSort(a, 0, n-1);
	} // end mergeSort


	/** Task: Merge sort on a portion of an array.  Creates a temporary array
	 *  then calls the recursive function
	 * @param a an array of Comparable objects
	 * @param first an integer >= 0 that is the index of the first
	 * array element to consider
	 * @param last an integer >= 0 that is the index of the last
	 * array element to consider
	 */
	public static <T extends Comparable<? super T>>
	void mergeSort(T[] a, int first, int last)
	{
		T tempArray[] = (T[]) new Comparable<?>[a.length];
		mergeSort(a, tempArray, first, last);
	} // end mergeSort



	/** Task: recursively merge sort a portion of an array.
	 * @param a an array of Comparable objects
	 * @param tempArray an array used by the merge step
	 * @param first an integer >= 0 that is the index of the first
	 * array element to consider
	 * @param last an integer >= 0 that is the index of the last
	 * array element to consider
	 */
	public static <T extends Comparable<? super T>>
	void mergeSort(T[] a, T[] tempArray, int first, int last)
	{

		if(last > first)        // we have some work to do
		{
			int mid = (last+first)/2;
			mergeSort(a, tempArray, first, mid);
			mergeSort(a, tempArray, mid+1, last);
			merge(a, tempArray, first, mid+1, last);
		}

	} // end mergeSort

	/** Task: Merge the elements in two contiguous sorted sublists 
	 * @param a an array of Comparable objects
	 * @param tempArray a temporay array used in the merge
	 * @param first an integer >= 0 and < mid
	 * @param mid an integer  <= last
	 * @param last an integer  < a.length
	 */
	public static <T extends Comparable<? super T>>
	void merge(T[] a, T[] tempArray, int first, int mid, int last)
	{
		int beginHalf1 = first;
		int endHalf1 = mid - 1;
		int beginHalf2 = mid;
		int endHalf2 = last;       
		// While both subarrays are not empty, compare an element in one subarray with
		//an element in the other; then copy the smaller item into the temporary array

		int index = first; //next available location in tempArray
		while ( (beginHalf1 <= endHalf1) &&(beginHalf2 <= endHalf2) )
		{
			if (a[beginHalf1].compareTo(a[beginHalf2]) < 0)

			{
				tempArray[index] = a[beginHalf1];
				beginHalf1++;
			}
			else
			{
				tempArray[index] = a[beginHalf2];
				beginHalf2++;
			}
			index++;
		}
		// end while

		//Assertion: One subarray has been completely copied to tempArray.


		// copy any remaining values from the first subarray over to temp
		while(beginHalf1 <= endHalf1)
			tempArray[index++] = a[beginHalf1++];

		// copy any remaining values from the second subarray over to temp
		while(beginHalf2 <= endHalf2)
			tempArray[index++] = a[beginHalf2++];

		// copy values back
		for(int i=first; i<=last; i++)
		{
			a[i]  = tempArray[i];
		} //end for
	} // end merge


	/**************************************************************
	 * QUICK SORT - NO BELLS AND WHISTLES
	 *      RECURSIVE
	 *      NO MEDIAN OF THREE
	 *      NO INSERTION SORT ON SMALL ARRAYS
	 **************************************************************/


	/** Task: Sorts the first n objects in an array into ascending order.
	 * @param a an array of Comparable objects
	 * @param n an integer > 0 
	 * 
	 */
	public static <T extends Comparable<? super T>>
	void basicQuickSort(T[] a, int n)
	{   
		basicQuickSort(a, 0, n-1);
	} // end basicQuickSort




	/** Task: Recursively sorts an array into ascending order. Does not use median of three. 
	 * Does not do insertion sort on small sub arrays.
	 * 
	 * @param a an array of Comparable objects
	 * @param first an integer >= 0 that is the index of the first
	 * array element to consider
	 * @param last an integer >= 0 that is the index of the last
	 * array element to consider
	 */
	public static <T extends Comparable<? super T>>
	void basicQuickSort(T[] a, int first, int last)
	{
		if (last - first + 1 > 1)
		{
			// create the partition: Smaller | Pivot | Larger
			int pivotIndex = basicPartition(a, first, last);
			// sort subarrays Smaller and Larger
			basicQuickSort(a, first, pivotIndex-1);
			basicQuickSort(a, pivotIndex+1, last);
		} // end if
	} // end basicQuickSort



	/** Task: Partitions an array as part of quick sort into two subarrays
	 * called Smaller and Larger that are separated by a single
	 * element called the pivot.
	 * Elements in Smaller are left of the pivot and <= pivot.
	 * Elements in Larger are right of the pivot and >= pivot.
	 * @param a an array of Comparable objects
	 * @param first the integer index of the first array element;
	 * first >= 0
	 * @param last the integer index of the last array element;
	 * last >= first  last < a.length
	 * @return the index of the pivot */
	public static <T extends Comparable<? super T>>
	int basicPartition(T[] a, int first, int last)
	{
		// pivot will be the last value in the sub sequence

		int pivotIndex = last;
		T pivot = a[pivotIndex];

		// determine subarrays Smaller = a[first..endSmaller]
		// and Larger = a[endSmaller+1..last-1]
		// such that elements in Smaller are <= pivot and
		// elements in Larger are >= pivot; initially, these subarrays are empty

		int indexFromLeft = first;
		int indexFromRight = last - 1;
		boolean done = false;
		while (!done)
		{
			// starting at beginning of array, leave elements that are < pivot;
			// locate first element that is >= pivot; you will find one,
			// since last element is >= pivot
			while (a[indexFromLeft].compareTo(pivot) < 0)
				indexFromLeft++;

			// starting at end of array, leave elements that are > pivot;
			// locate first element that is <= pivot; you may not find one, so stop
			// at first.
			while (a[indexFromRight].compareTo(pivot) > 0  && indexFromRight > first)
				indexFromRight--;

			// Assertion: a[indexFromLeft] >= pivot 
			if (indexFromLeft < indexFromRight)
			{
				swap(a, indexFromLeft, indexFromRight);
				indexFromLeft++;
				indexFromRight--;
			}
			else
				done = true;
		} // end while

		// place pivot between Smaller and Larger subarrays
		swap(a, pivotIndex, indexFromLeft);
		pivotIndex = indexFromLeft;

		// Assertion:
		// Smaller = a[first..pivotIndex-1]
		// Pivot = a[pivotIndex]
		// Larger = a[pivotIndex + 1..last]
		return pivotIndex;
	} // end basicPartition

	/**************************************************************
	 * QUICK SORT - A SECOND VERSION
	 *      RECURSIVE
	 *      NO MEDIAN OF THREE
	 *      DOES INSERTION SORT ON SMALL ARRAYS
	 **************************************************************/


	/** Task: Sorts the first n objects in an array into ascending order.
	 * @param a an array of Comparable objects
	 * @param n an integer > 0 
	 * 
	 */
	public static <T extends Comparable<? super T>>
	void version2QuickSort(T[] a, int n)
	{   
		version2QuickSort(a, 0, n-1);
		insertionSort(a, 0, n-1);
	} // end version2QuickSort


	private static int MIN_SIZE = 10;
	/**
	 * set the minimum size that quick sort will do recursively
	 *
	 * @param  size   the size to use; must be > 0
	 */
	public static void setQuickSortMinimumSize(int size)
	{
		if(size > 0)
			MIN_SIZE = size;
	}




	/** Task: Recursively sorts an array into ascending order. Does not use median of three.
	 * Will do insertion sort on subarrays smaller or equal to MIN_SIZE.
	 * 
	 * @param a an array of Comparable objects
	 * @param first an integer >= 0 that is the index of the first
	 * array element to consider
	 * @param last an integer >= 0 that is the index of the last
	 * array element to consider
	 */
	public static <T extends Comparable<? super T>>
	void version2QuickSort(T[] a, int first, int last)
	{
		if (last - first + 1 > MIN_SIZE)
		{
			// create the partition: Smaller | Pivot | Larger
			int pivotIndex = basicPartition(a, first, last);
			// sort subarrays Smaller and Larger
			version2QuickSort(a, first, pivotIndex-1);
			version2QuickSort(a, pivotIndex+1, last);
		} // end if
	} // end version2QuickSort


	/**************************************************************
	 * QUICK SORT - A THIRD VERSION
	 *      RECURSIVE
	 *      MEDIAN OF THREE
	 *      DOES INSERTION SORT ON SMALL ARRAYS
	 **************************************************************/



	/** Task: Sorts the first n objects in an array into ascending order.
	 * @param a an array of Comparable objects
	 * @param n an integer > 0 
	 * 
	 */
	public static <T extends Comparable<? super T>>
	void version3QuickSort(T[] a, int n)
	{   
		version3QuickSort(a, 0, n-1);
		insertionSort(a, 0, n-1);
	} // end version3QuickSort



	/** Task: Recursively sorts an array into ascending order. Uses quick sort with
	 * median-of-three pivot selection for arrays of at least
	 * MIN_SIZE elements, and uses insertion sort for other arrays. 
	 * 
	 * @param a an array of Comparable objects
	 * @param first an integer >= 0 that is the index of the first
	 * array element to consider
	 * @param last an integer >= 0 that is the index of the last
	 * array element to consider
	 */
	public static <T extends Comparable<? super T>>
	void version3QuickSort(T[] a, int first, int last)
	{
		if (last - first + 1 > MIN_SIZE)
		{
			// create the partition: Smaller | Pivot | Larger
			int pivotIndex = partition(a, first, last);
			// sort subarrays Smaller and Larger
			version3QuickSort(a, first, pivotIndex-1);
			version3QuickSort(a, pivotIndex+1, last);
		} // end if
	} // end version3QuickSort


	/** Task: Sorts the first, middle, and last elements of an
	 * array into ascending order.
	 * @param a an array of Comparable objects
	 * @param first the integer index of the first array element; first >= 0
	 * @param mid the integer index of the middle array element
	 * @param last the integer index of the last array element;
	 * last - first >= 2, last < a.length */
	public static <T extends Comparable<? super T>>
	void sortFirstMiddleLast(T[] a, int first, int mid, int last)
	{
		order(a, first, mid); // make a[first] <= a[mid]
		order(a, mid, last); // make a[mid] <= a[last]
		order(a, first, mid); // make a[first] <= a[mid]
	} // end sortFirstMiddleLast


	/** Task: Orders two given array elements into ascending order
	 * so that a[i] <= a[j].
	 * @param a an array of Comparable objects
	 * @param i an integer >= 0 and < array.length
	 * @param j an integer >= 0 and < array.length */
	public static <T extends Comparable<? super T>>
	void order(T[] a, int i, int j)
	{
		if (a[i].compareTo(a[j]) > 0)
			swap(a, i, j);
	} // end order


	/** Task: Partitions an array as part of quick sort into two subarrays
	 *       called Smaller and Larger that are separated by a single
	 *       element called the pivot.
	 *       Elements in Smaller are left of the pivot and <= pivot.
	 *       Elements in Larger are right of the pivot and >= pivot.
	 * @param a an array of Comparable objects
	 * @param first the integer index of the first array element;
	 *       first >= 0
	 * @param last the integer index of the last array element;
	 *       last >= first; last < a.length
	 * @return the index of the pivot */
	public static <T extends Comparable<? super T>>
	int partition(T[] a, int first, int last)
	{
		int mid = (first + last)/2;        
		sortFirstMiddleLast(a, first, mid, last);

		int pivotIndex = first;
		T pivot = null;


		if(last - first + 1 > 2 )
		{

			// Assertion: The pivot is a[mid]; a[first] <= pivot and
			// a[last] >= pivot, so do not compare these two array elements
			// with pivot.

			// move pivot to next-to-last position in array

			swap(a, mid, last-1);
			pivotIndex = last-1;
			pivot = a[pivotIndex];

			// determine subarrays Smaller = a[first..endSmaller]
			// and Larger = a[endSmaller+1..last-1]
			// such that elements in Smaller are <= pivot and
			// elements in Larger are >= pivot; initially, these subarrays are empty

			int indexFromLeft = first + 1;
			int indexFromRight = last - 2;
			boolean done = false;
			while (!done)
			{
				// starting at beginning of array, leave elements that are < pivot;
				// locate first element that is >= pivot; you will find one,
				// since last element is >= pivot
				while (a[indexFromLeft].compareTo(pivot) < 0)
					indexFromLeft++;

				// starting at end of array, leave elements that are > pivot;
				// locate first element that is <= pivot; you will find one,
				// since first element is <= pivot
				while (a[indexFromRight].compareTo(pivot) > 0)
					indexFromRight--;

				assert a[indexFromLeft].compareTo(pivot) >= 0 &&
				a[indexFromRight].compareTo(pivot) <= 0;

				if (indexFromLeft < indexFromRight)
				{
					swap(a, indexFromLeft, indexFromRight);
					indexFromLeft++;
					indexFromRight--;
				}
				else
					done = true;
			} // end while

			// place pivot between Smaller and Larger subarrays
			swap(a, pivotIndex, indexFromLeft);
			pivotIndex = indexFromLeft;

			// Assertion:
			// Smaller = a[first..pivotIndex-1]
			// Pivot = a[pivotIndex]
			// Larger = a[pivotIndex + 1..last]
		}

		return pivotIndex;
	} // end partition

	/**************************************************************
	 * KTH ORDER STATISTIC - BASIC ALGORITHM THAT SORTS FIRST
	 *        ARRAY MAY BE SORTED OR UNSORTED
	 **************************************************************/    

	/** Task: Find the kth item of the first n items in sorted order
	 * @param a an array of Comparable objects
	 * @param n an integer > 0 and less than or equal to a.length
	 * @param k an integer > 0 and less than or equal to n
	 */
	public static <T extends Comparable<? super T>>
	T basicKthItem(T[] a, int k, int n)
	{   
		basicQuickSort(a, 0, n-1);
		return( a[k-1] );
	} // end kthItem


	/**************************************************************
	 * KTH ORDER STATISTIC - ALGORITHM THAT USES PARTITION
	 *        ARRAY MAY BE SORTED OR UNSORTED
	 **************************************************************/


	/** Task: Find the kth item of the first n items in sorted order
	 * @param a an array of Comparable objects
	 * @param n an integer >= 0 and less than or equal to a.length
	 * @param k an integer >= 0 and less than or equal to n
	 */
	public static <T extends Comparable<? super T>>
	T kthItem(T[] a, int k, int n)
	{   
		return kthItem(a, k-1, 0, n-1);
	} // end kthItem


	/** Task: recursively find the kth item in a sorted sublist of items
	 * @param a an array of Comparable objects
	 * @param k an integer >= 0 that is the position of the item to return.  
	 * @param first an integer >= 0 that is the index of the first
	 * array element to consider
	 * @param last an integer >= 0 that is the index of the last
	 * array element to consider
	 */
	private static <T extends Comparable<? super T>>
	T kthItem(T[] a, int k, int first, int last)
	{
		T result = a[first];
		k = ( first + last )/2;        
		if( a[k] == result)
		{
			return result;
		}
		else if( first >= last )
		{
			return null;
		}
		else if( a[k].compareTo(result) > 0)
		{
			return kthItem( a, k-1, first, last);
		}
		else 	
		{

			System.out.println("call: " + k + " " + first + " " + last + " ");
			//COMPLETE THIS RECURSIVE METHOD

			return result;
		}
	}
}// end kthItem
// end SortArray



Is This A Good Question/Topic? 0
  • +

Replies To: recursive method

#2 Dogstopper  Icon User is online

  • The Ninjaducky
  • member icon



Reputation: 2857
  • View blog
  • Posts: 10,962
  • Joined: 15-July 08

Re: recursive method

Posted 10 March 2010 - 05:23 PM

Quote

//COMPLETE THIS RECURSIVE METHOD


umm...no...but we can help...

What is going wrong here? Why is it not working the way you expected? Please give us more information to work with, as we don't read minds...Thank you.
Was This Post Helpful? 0
  • +
  • -

#3 drowninggirl  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 21-January 10

Re: recursive method

Posted 10 March 2010 - 10:53 PM

The part above that quote is what I wrote in the method. I don't know how to fix it. It's saying stack overflow. Any hints??? I'm stuck.
Was This Post Helpful? 0
  • +
  • -

#4 zim1985  Icon User is offline

  • Grand Inquisitor
  • member icon

Reputation: 74
  • View blog
  • Posts: 557
  • Joined: 19-February 10

Re: recursive method

Posted 10 March 2010 - 10:55 PM

View Postdrowninggirl, on 10 March 2010 - 08:53 PM, said:

The part above that quote is what I wrote in the method. I don't know how to fix it. It's saying stack overflow. Any hints??? I'm stuck.

That error means you are never reaching your "base case" which is where the method returns a definitive answer.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1