Wednesday, May 21, 2014

Find nth minimum element in an array.

unsigned long partitionArray(int arr[], unsigned long left, unsigned long right)
{
unsigned long pivot = (rand() % (right - left + 1)) + left;
SWAP(arr[left], arr[pivot]);
unsigned long i = left + 1;
for(unsigned long j = left + 1; j <= right; ++j)
{
if(arr[j] < arr[left])
{
swap(arr[j], arr[i]);
++i;
}
}
swap(arr[i-1], arr[left]);
return i-1;
}

int RSelect(int arr[], int left, int right, int n)
{
if(left == right && left == n)
return arr[left];
int pivotIndex = partitionArray(arr, left ,right);
if(pivotIndex + 1 == n)
return arr[pivotIndex];
else if(pivotIndex + 1 > n)
return RSelect(arr, left, pivotIndex - 1, n);
else
return RSelect(arr, pivotIndex + 1, right, n);
}

Friday, May 9, 2014

Find second-largest number in the array in at most n+log2n−2 comparisons.

int* findMax(int *arr, int i, int j, int len)
{
if(i == j)
{
int* comp = new int[len];
comp[0] = 1;
comp[1] = arr[i];
return comp;
}
int *comp1 = findMax(arr, i, i+(j-i)/2, len);
int *comp2 = findMax(arr, 1+i+(j-i)/2, j, len);
if(comp1[1] > comp2[1])
{
int k = comp1[0] + 1;
comp1[0] = k;
comp1[k] = comp2[1];
delete [] comp2;
return comp1;
}
else
{
int k = comp2[0] + 1;
comp2[0] = k;
comp2[k] = comp1[1];
delete [] comp1;
return comp2;
}
}

int findSecondMax(int *arr, int len)
{
int *compared =  findMax(arr, 0, len-1, len);
int *max2Arr = findMax(compared, 2, compared[0], compared[0] + 1);
int max2 = max2Arr[1];
delete [] max2Arr;
return max2;
}

Number of inversions in an array

Problem: Find the number of pairs (i, j) of an array A indices with i < j and A[i] > A[j].

Solution:

unsigned long countSplitInversions(int *arr, unsigned long mid, unsigned long len)
{
vector<int> tempVect(arr, arr + mid);
unsigned long count = 0;
unsigned long i = 0, j = mid, k = 0;
for(; i < mid && j < len;)
{
if(arr[j] < tempVect[i])
{
arr[k++] = arr[j++];
count += (mid - i);
}
else
{
arr[k++] = tempVect[i++];
}
}
if(j < len)
{
while(j < len)
arr[k++] = arr[j++];
}
else if(i < mid)
{
while(i < mid)
arr[k++] = tempVect[i++];
}
return count;
}

unsigned long countInversions(int *arr, unsigned long len)
{
if(len == 1)
return 0;
unsigned long mid = len/2;
unsigned long leftInversions = countInversions(arr, mid);
unsigned long rightInversions = countInversions(arr + mid, len - mid);
unsigned long splitInversions = countSplitInversions(arr, mid, len);
return leftInversions + rightInversions + splitInversions;
}