CareerCup

QuickSort with findMedium to find the pivot. Use findMax on left side of pivot and findMin on right side of pivot until findMax > pivot and findMin < pivot ?

I think it should be a Merge sort:

static int [] mergeSort()
{
if(ar == null || ar.length < 2)
{
return ar;
}
int min = findMin(ar, 0, ar.length);
int max= findMax(ar,0, ar.length);
return mergeSortHelper(ar, min, max);
}

static int []mergeSortHelper(int []ar, int min, int max)
{
min > end return ar;
min = findMin(ar);
max= findMax(ar);
int pivot = findMedium(min, max);
int []left = mergeSortHelper(min,mid);
int []right = mergeSortHelper(mid+1, max);
merge(left,right);

}

static int []merge((int []left, int []right))
{
int []res = new int[left.length + right.length];
int len = Math.min(left.length, right.length);
int i=o;
int leftIndex, rightIndex;
while(i < len)
{

if(left[leftIndex]< right[rightIndex)
{
res[i++] = (left[leftIndex++];
}
else
{
res[i++] = (right[right dex++];
}
}
int k = len;
if(left.length > k)
{
while( k < left.length)
{
res[i++] = (left[k++];
}
}
else
{

while( k < left.length)
{
res[++] = (right[k++];
}
}


}

calling this function in the entire array will always resolve to the same numbers so
If it would be possible to specify a starting index on each of these functions
Then you could sort the array only using findMin(int i).
// finds Min from index i to array.length.

pseudocode:

public static void sortArray(int a[]) {
 
 for (int i - 0; i < a.length; i++) {
    int min = findMin(a.length, i);
    if (min != a[i]) {
       swap(a, min, i);       
    }
 }

}

fnSort(int arr[],l,r)
{
	for(int i=0,j=r;i<j;i++,j--)
	{
		var maxi=fnMax(arr,i,j);
		var mini=fnMax(arr,i,j);
		if(maxi!=j)
			swap(arr,maxi,j);
		if(mini!=i)	
			swap(arr,mini,i);
	}
}

@VV, I will explain why I down-voted your question, please be wise and don't retaliate. Also, if you will correct the issue with problem statement, not only I will revert my down-vote, but will also up-vote this.

Any existing sorting method can use these 3 methods in addition to the algorithm. It is obvious that problem statement is incomplete and is also stating WHAT YOU CANNOT UTILIZE --->

OR: It potentially says that these 3 methods can complete with certain magical time complexity and now having such, come up with better time complexity for the sorting.

Please, complete the problem statement.

Not clear what the exact problem statement is.
- I am assuming that we cannot iterate the array?
- No swap method is given (which internally swaps two integer based at an index )?
- The only way I can assume this can be solved is given these APIs return index instead of value.

In which case (not handling off by one errors)

int begin = 0;
int end = getMedian() * 2 -1;

while(begin < end)
{
      Swap(A, getMin(), begin);  
      Swap(B, getMax(), end);
      begin += 1;
      end - =1;
}

I am gonna assume that findMax, findMin, and findMedium all takes array A and its length as parameters and return the results in O(1) time.

If that is the case, I would use counting sort to sort the integer in O(N) time.

Any critics will be welcomed.

int* CountingSort(int* A, int len)
{
	int max = findMax(A, len);
	int min = findMin(A, len);
	int clen = max - min +1;
	int *c = new int[clen];
	int *B = new int[len];
	int i;

	for (i = 0; i <clen; i++)
		c[i] = 0;
	for(i = 0; i <len; i++)
		c[A[i]-min] += 1;
	for (i = 0; i <clen; i++)
	{
		if (i >0)
			c[i] = c[i-1]+c[i];
	}

	for (i = len-1; i >=0; i--)
	{
		B[c[A[i]-min]-1] = A[i];
		c[A[i]-min] -=1;
	}
	delete [] c;
	return B;
}

Pseudocode:

//p and r are the starting and end index of array A.
SORT(A, p, r):
    if r > p + 2:	// more than 3 elements
        q = PARTITION(A, p, r)
        SORT(A, p, q-1)
        SORT(A, q+1, r)
    elif r == p + 2:	// 3 elements
        min = findMin(A[p to r])
        mid = findMedium(A[p to r])
        max = fincMax(A[p to r])
        A[p] = min
        A[p + 1] = mid
        A[r] = max
    elif r == p + 1:	// 2 elements
        min = findMin(A[p to r])
        max = findMax(A[p to r])
        A[p] = min
        A[q] = max

PARTITION(A, p, r):
    x = findMedium(A[p to r])
    i = p - 1
    for j = p to r:
        if A[j] <= x:
            i += 1
            Swap A[i] with A[j]
    return i

Does the question really ask people to sort the array? If not, then we can just maintain four heap data structure. One for max, one for min. and two for medium. 

Run time, Log n.

void sortMMM(vector<int>& values) {
	int start = 0;
	int end = values.size()-1;
	while (start < end) {
		int min = findMin(values, start, end);
		swap(values[min], values[start]);
		if (end-start+1 > 2) {
			int max = findMax(values, start, end);
			swap(values[max], values[end]);
			int half = start + (end - start) / 2;
			int mid = findMedium(values, start, end);
			swap(values[mid], values[half]);
		}
		start = start+1;
		end = end-1;
	}
}

void sortMMM(vector<int>& values) {
	int start = 0;
	int end = values.size()-1;
	while (start < end) {
		int min = findMin(values, start, end);
		swap(values[min], values[start]);
		if (end-start+1 > 2) {
			int max = findMax(values, start, end);
			swap(values[max], values[end]);
			int half = start + (end - start) / 2;
			int mid = findMedium(values, start, end);
			swap(values[mid], values[half]);
		}
		start = start+1;
		end = end-1;
	}
}