Category Archives: Divide and Conquer
Counting the number of inversions in a list
 First count the inversions in the left part
 Count the inversions in the right part
 Count the inversions if they are merged using modified merge procedure
 Adding the three counts gives the actual result
 Take two pointers to start of the two arrays.
 Compare the two elements to see which element goes to the sorted list first.
 Increment the corresponding index.
 Repeat the above steps until we reach the end of either of them.
 Add the remaining elements if any.
Computing the power of a given number
int absn = abs(n);
if( absn == 0 )
return 1.0;
else if( absn == 1)
{
return (n < 0) ? (1/x) : x;
}
double temp = pow(x, absn/2);
double result;
{
result = temp*temp;
}
else
{
result = temp*temp*x;
}
return ( n < 0 )? (1/result) : result;
}
Finding an element in a circularly sorted array
For example let us consider the array [12, 15, 6, 8, 10], the element 8 is found at index 3.
We can design an algorithm like this. We first check if the middle element equals the target element. If so, we return the mid.
Otherwise we check to see if the left half is sorted or right half is sorted. In any case only one portion will be sorted. We have to narrow down our search based on the range of elements which the target belongs to .
if( arr[low] <= arr[mid]) //left half is sorted
{
//If target lies in first half
if( s >= arr[low] && s < arr[mid] )
high = mid – 1;
else
low = mid + 1; // narrow down to right half
}
else // Right half is sorted
{
if( s > arr[mid] && s <= arr[high] )
low = mid + 1;
else
high = mid – 1;
}
Here is the iterative implementation of the above algorithm. This algorithm runs in O( log n ) time complexity.
How many times a sorted array is rotated?
For example the array [4, 5, 1, 2, 3] is (right) rotated twice.
Before proceeding to find a solution, let’s note some observations.
To find the number of rotations, we have to find the smallest element in the array. If we find the index of the smallest element in the array, that will indicate the number of rotations.
In the above example, the smallest number is 1 which is located at index ‘2’. We can easily verify that the array is rotated twice.
A simple approach could be to use a linear search to find the least number and return it’s index. This approach will obviously take O(n) time. Can we perform better than that?
Yes, it can be done by utilizing the sorted property of the array. Here is how we can do this.
Just like Binary search, we can use divide and conquer approach. We write a recursive function which will take the array, lower and upper bound as its parameters.
We first check whether the array is sorted from the beginning (not rotated). This can be done by checking if array[low] <= array[high]. If it is not rotated, we can simply return the index low.
Next we check if the middle element is the smallest element by comparing it with the previous and next elements.
If this condition is satisfied, then we return mid. One caution while calculating the next and previous indices is to consider the array boundaries. We have to assume that the array is circular.
//if mid is at 0, consider last element as previous
int prev = (mid – 1 + len) % len;
//if mid is the last element, consider next element as the first
int next = (mid + 1) % len;
Next, we check which portion is already sorted. If the left portion is properly sorted (without rotations), we search in the right half. Otherwise we search in the left half.
return findRotations(arr, mid+1, high);
else
return findRotations(arr, low, mid1);
Even more simplified version of the algorithm is given below.
int findRotationCount(const vector<int>& arr)
{
int low = 0, high = arr.size()  1;
while( arr[low] > arr[high] )
{
int mid = low + (high  low)/2;
if( arr[mid] > arr[high] )
low = mid + 1;
else
high = mid;
}
return low;
}
int findRotateCount(const vector<int>& arr, int low, int high)
{
if( arr[low] > arr[high] )
{
int mid = low + (highlow)/2;
if( arr[mid] > arr[high] )
return findRotateCount( arr, mid+1, high);
else
return findRotateCount( arr, low, mid);
}
else
return low;
}
How does Quicksort work?
Quick sort works as follows.
A random element from the array is chosen as a pivot element. A pivot element is a special element which divides the array into left part and right part. All the elements to the left of pivot ( left part) must be less than or equal to pivot, and all the elements to the right of pivot( right part) must be greater than pivot.
At this point it is easy to understand that the pivot element is in it’s position and only left, and right parts needs to be sorted. We use recursive call to sort these parts.
Here partition process is the key to sorting.
Consider the following example to understand the partitioning process.
4

7

3

6

9

2

8

5

1

2

1

3

4

9

6

8

5

7

You can get a good understanding of the whole procedure if we look at the following animation (Image courtesy: Wikipedia).
Here is the C++ code for quick sort.This procedure runs in O(n log n) time in average case. But in the worst case, It can take up to O(n^2) time.
#include <iostream>
using namespace std;
void quick_sort(int[], int, int);
int main()
{
int array[] = {4,7,3,6,9,2,8,5,1};
quick_sort(array,0,8);
for( int i = 0; i < 9; i++ )
{
cout<<array[i]<<" ";
}
return 0;
}
void quick_sort(int array[], int l, int h)
{
if( l < h)
{
int left = l; //starting index of the array
int right = h;// ending index of the array
int pivot = array[left];//take left most element as pivot
while ( left < right)
{
//decrement right pointer as long as the element
//at this index is greater than pivot
while ( array[right] > pivot )
right;
//increment left pointer as long as the element
//at this index is less than or eqal to pivot
while ( array[left] <= pivot )
left++;
//swap the elements if left and right do not overlap
if( left < right)
{
swap( array[left], array[right] );
}
}
//right is the correct position for pivot,
//so swap the first element(chosen as pivot) with 'right'
swap(array[l],array[right]);
//recursively call quick sort for left and right parts
quick_sort(array, l, right1);
quick_sort( array, right+1,h);
}
}
How does a merge sort work?
In this method we divide the array into two halves. We recursively sort these two parts and merge them into single array. Here the base case for recursion is just one element i.e no need to sort an array with just one element.
For example let us consider an array of 5 elements
[3,2,1,5,4]
It is divided into two subarrays [3,2,1] and [5,4]. We apply merge sort recursively on both the subarrays and merge them to become a single sorted array.
Here is how the first subarray gets sorted.
[3,2,1] is divided into [3,2] and [1]. No need sort the second subarray because it just contains one element.
[3,2] is divided into [3], [2].
The merge procedure combines the arrays [3], [2] into sorted subarray [2,3].
Then the subarray [2,3] is merged with [1] to become [1,2,3]
Finally [1,2,3] gets merged with [4,5] to become [1,2,3,4,5] which is fully sorted.
The merge procedure works as follows. The input to the merge procedure is two sorted subarrays.
We initialize two pointers to the first elements of two subarrays. We copy the lesser element among them to a temporary array and advance the corresponding pointer to the next element. We repeat this procedure until atleast one of the subarrays becomes empty.
Finally we copy the nonempty subarray elements to the temporary array.
Here is the Java implementation of merge sort.
public class Main {
public static void main(String[] args)
{
int [] array = {51,126,98,12,3,34,269,73,6,88};
mergeSort( array, 0, array.length1);
for( int i = 0; i < array.length; i++)
{
System.out.print(array[i] + " ");
}
}
public static void mergeSort(int[] array, int left, int right )
{
if( left < right)// If the array has at least one element
{
int mid = (left + right) / 2;
mergeSort(array, left, mid);
mergeSort(array, mid+1, right);
merge(array, left, mid+1, right);
}
}
public static void merge(int [] array, int l, int m, int r)
{
//We need a temporary array of size rl+1 for the merged elements
int [] temp = new int[rl+1];
int i = l; //index of first subarray
int j = m; //index of second sub array
int k = 0;
while( i < m && j <= r)
{
if( array[i] < array[j])
{
temp[k++] = array[i++];
}
else
{
temp[k++] = array[j++];
}
}
//copy if there are any elements remaining in any half
while( i < m )
{
temp[k++] = array[i++];
}
while ( j <= r )
{
temp[k++] = array[j++];
}
//copy sorted elements from temp to original array
for( i = l,j=0 ; i <= r; i++,j++)
{
array[i] = temp[j];
}
}
}
This code runs in O(n log n) time in the worst case also. But it is not an inplace sorting mechanism because we use a temporary array in the merge procedure.