Max Min

algorithm.md

###MaxMin Theorem - A divide and conquer approach

####Some Assumptions

• The variables minimum_of_this_scope will be holding the minimum value in the scope [first_index, last_index], i.e. the minimum out of { array[first_index], array[first_index+1], .. , array[last_index] }
• Similarly, maximum_of_this_scope will be holding the maximum value in the scope.
• Although they are being passed as an arguement, they will be making use of pass by reference to store the maximum/minimum values. We have two values and hence simple return will not be working.

MAXMIN(array, first_index, last_index, minimum_of_this_scope, maximum_of_this_scope):
	IF first_index == last_index:
		/* We are looking at a scope with single element only.  */
		minimum_of_this_scope = maximum_of_this_scope = array[first_index]

	ELSE IF last_index - first_index == 1:
		/* A scope with two elements. The smaller one will be the minimum and the other will be maximum. */
		IF array[first_index] > array[last_index]:
			minimum_of_this_scope = array[last_index]
			maximum_of_this_scope = array[first_index]
		ELSE
			minimum_of_this_scope = array[first_index]
			maximum_of_this_scope = array[last_index]
		END IF

	ELSE
		/* There's more element. Divide the scopes into smaller ones */
		middle_index = FLOOR[(first_index + last_index)/2]
		max_min(array, first_index, middle_index, minimum_from_half1, maximum_from_half1)
		max_min(array, middle_index + 1, last_index, minimum_from_half2, maximum_from_half2)
		
		/* Compare the results from smaller halves and then assign the maximum and minimum for this scope. */
		IF minimum_from_half1 < minimum_from_half2:
			minimum_of_this_scope = minimum_from_half1
		ELSE
			minimum_of_this_scope = minimum_from_half2
		END IF

		IF maximum_from_half1 > maximum_from_half2:
			maximum_of_this_scope = maximum_from_half1
		ELSE
			maximum_of_this_scope = maximum_from_half2
		END IF		
	END IF
END MAXMIN

For zero based indexing, the method should be called with MAXMIN(array, 0, size - 1, &minimum, &maximum)
References of the variables(maximum & minimum) are used and hence after completion, they will be containig the desired result.

Generally if we are making use of linear comparison, it will take 2n comparisons to compute both minimum and maximum together, while this way the number of comparisons are reduced to 3n/2 - 2. If we are talking about time complexity, they both are winded up to O(n), but the divide and conquer approach will make lesser comparison than the linear one.

maxmin.c

/*
	MAX MIN in array
	0 based indexing
	** for TURBO C, remove // from commented statements
*/

#include<stdio.h>
//#include<conio.h>

void max_min(int *arr, int first_index, int last_index, int *min_value, int *max_value){
	int middle_index, min_of_1, min_of_2, max_of_1, max_of_2;

	if(first_index == last_index){
		*min_value = *max_value = arr[first_index];
	}else if(last_index - first_index == 1){
		if(arr[first_index] > arr[last_index]){
			*min_value = arr[last_index];
			*max_value = arr[first_index];
		}else{
			*min_value = arr[first_index];
			*max_value = arr[last_index];
		}
	}else{
		middle_index =  (first_index + last_index)/2;
		max_min(arr, first_index, middle_index, &min_of_1, &max_of_1);
		max_min(arr, middle_index + 1, last_index, &min_of_2, &max_of_2);

		*min_value = (min_of_1 < min_of_2) ? min_of_1 : min_of_2;
		*max_value = (max_of_1 > max_of_2) ? max_of_1 : max_of_2;
	}
}


int main(){
	int arr[] = { 111, -1, 423, 1003, 32, 45, -18, 231, 2918, 1028 };
	int minimum, maximum;

	max_min(arr, 0, 9, &minimum, &maximum);

	printf("\nMinimum in array: %d\nMaximum in array: %d", minimum, maximum);
	printf("\n");
	//getch();
	return 0;
}

Maxmin.java

/*
	MAX MIN in array
	0 based indexing
	Save File as Maxmin.java
*/

class Maxmin_wrapper{
	/* Since java's call by reference needs a reference to a object, this class will be used as a wrapper */
	public int maximum;
	public int minimum;
}

public class Maxmin{
	public static void max_min(int[] arr, int first_index, int last_index, Maxmin_wrapper result){
		int middle_index;
		Maxmin_wrapper result_of_1 = new Maxmin_wrapper();
		Maxmin_wrapper result_of_2 = new Maxmin_wrapper();

		if(first_index == last_index){
			result.minimum = result.maximum = arr[first_index];
		}else if(last_index - first_index == 1){
			if(arr[first_index] > arr[last_index]){
				result.minimum = arr[last_index];
				result.maximum = arr[first_index];
			}else{
				result.minimum = arr[first_index];
				result.maximum = arr[last_index];
			}
		}else{
			middle_index =  (first_index + last_index)/2;
			max_min(arr, first_index, middle_index, result_of_1);
			max_min(arr, middle_index + 1, last_index, result_of_2);

			result.minimum = (result_of_1.minimum < result_of_2.minimum) ? result_of_1.minimum : result_of_2.minimum;
			result.maximum = (result_of_1.maximum > result_of_2.maximum) ? result_of_1.maximum : result_of_2.maximum;
		}
	}

	public static void main(String s[]){
		int arr[] = { 111, -1, 423, 1003, 32, 45, -18, 231, 2918, 1028 };
		Maxmin_wrapper result = new Maxmin_wrapper();

		max_min(arr, 0, 9, result);

		System.out.print("\nMinimum in array: " + result.minimum + "\nMaximum in array: " + result.maximum);
		System.out.print("\n");
	}
}