HeapSort as a combine subroutine of MergeSort

This article is taken from my ResearchGate profile. Link . This article is under Creative Commons Licence By (cc-by).

Divide and Conquer Algorithm for Linear Search

Divide and Conquer Algorithm for Linear Search

We have seen the Binary Search Algorithm which searches for an element in a sorted array in logarithmic time. Time complexity associated with it is . 

Recurrence relation of Binary Search: 

Using the same principle of Divide, Conquer, and Combine, we can also utilize this algorithm to find an element in an unsorted array, though the time complexity will be linear .

Recurrence relation of Linear Search: 

#include<iostream>

#include<vector>

using namespace std;

int linear_search(vector<int>&v,int s,int e,int x)

{

    if(s>e)return -1;

    int m=s+(e-s)/2;

    if(v[m]==x)return m;

    int left=linear_search(v,s,m-1,x);

    int right=linear_search(v,m+1,e,x);

    if(left==-1 && right==-1)return -1;

    if(left!=-1)return left;

    else if(right!=-1)return right;

}

int main()

{

    vector<int>v={4,2,6,8,1,2,9,4};

    cout<<linear_search(v,0,v.size()-1,8);

    return 0;

}

Output: 3

Analysis of time complexity:

Sum of an array using Divide and Conquer algorithm

Sum of an array using Divide and Conquer algorithm (DAC)

Finding sum of an array is a very easy task, just add all the elements in a single pass! Time and space complexity associated with this approach is linear and constant respectively. 

In this post, I will show how we can find the sum of an array using Divide and Conquer algorithm.

First of all I would like you to have a glance at What a Divide and Conquer algorithm is? 

Divide and Conquer is an algorithmic strategy used to find solution of a particular problem by recursively breaking down the problem into sub-problems of same type, and when the base condition of the recursion is hit, assemble the results of those sub-problems to form the solution of the original problem.

This strategy often brings considerable optimizations in some while solving some problems. Some popular algorithms that implements Divide and Conquer are:

1. Quicksort

2. Mergesort

3. Binary Exponentiation

4. Quickselect

5. Straseen's algorithm (Matrix Multiplication)

6. Binary Search

The Divide and Conquer strategy can be divided into three parts:

1. Divide: Divide the larger problem into smaller sub-problems of same type.

2. Conquer: Solve the sub-problems by recursively calling until solved.

3. Combine:  Combine the sub-problems to get the final solution of the whole problem.

It becomes very easy to find the time complexity of DAC algorithms using Master Theorem.

Image given below shows how to solve recurrence relations using Master Method.

Now, coming back to the question. We have to find the sum of an array using    DAC. 

Let's formulate the solution:

Sum of an array can be found using breaking the array into two halves, add them and return the sum. Recursively break down the problem into two halves, we the array size becomes 1, return the value of that single element. So simple! 

int sum(int arr[],int start,int end)

{

    if(start==end)

    return arr[start];

    int mid=start+(end-start)/2;

    int left=sum(arr,start,mid);

    int right=sum(arr,mid+1,end);

    return left+right;

}

    int arr[]={1,2,3,-1,4,5,6,7};

    cout<<sum(arr,0,sizeof(arr)/sizeof(int)-1);

output: 27

I have traced the algorithm:

Now, let's find the time complexity of this algorithm. 

Hence, the time complexity is .

The QuickSelect Algorithm

What is QuickSelect Algorithm?

Suppose I give you an array of numbers and ask you to give me the  smallest number. How will you come out with solution?

One simple solution is to sort the array and return the element at   index, or  ARR[K-1]. 

C++ code

int kthSmallest(int *arr,int n,int k)

{

    sort(arr,arr+n);

    return arr[k-1];

}

The time complexity of this approach will be depending upon the sorting algorithm we use. Let us suppose we use the very popular comparison based sorting algorithm known as quicksort. 

Since time complexity of quicksort is  .  Therefore our naive solution will also have the same complexity of  . 

Is it a good approach?

Surely no because by sorting the whole array, we will be in the position to answer each element from k=1 to k=N ( N is the length of the array). What I want to say is we are doing extra efforts, which we can skip.

Before heading towards our goal, first let us know about the partitioning algorithm.

Partitioning Algorithm

Partitioning algorithm is a subroutine of quicksort algorithm which creates a pivot in the array and returns its index. Elements in the left hand side of the array are less than the pivot and that of right side are greater than the pivot.

for example, if the array is 3,2,1,5,6,4. Then after partitioning it will look like  1,2,3,5,6,4. 

It takes the first element and places it at some index such that all elements before it are lesser than it and all element to its right are greater than it. 

Here 3 is selected as pivot and placed at index 2. 

C++ code

int partition(int *arr,int lb,int ub)

{

    int start=lb,end=ub;

    int pivot=arr[start];

    while(start<end )

    {

        while(arr[start]<=pivot)

        ++start;

        while(arr[end]>pivot)

        --end;

        if(start<end)

        swap(arr[start],arr[end]);

    }

    swap(arr[lb],arr[end]);

    return end;

}

    

Time complexity of this partitioning algorithm is . 

QuickSelect Algorithm:

Similar to quicksort algorithm, quickselect calls partition function as it subroutine. The partition function partitions the array into two parts and returns the index of  the pivot element. 

Now, if the index of the pivot element is equal to k, then the quickselect functions returns the pivot, else if k is greater than the pivot index, then the quickselect is called for the right side of the array or if k is less than the pivot index, then the quickseleck is called for the left side of the array.

Look at the code for better understanding.

int quickSelect(int *arr,int start,int end,int k)

{

    if(start>end)

    return 0;

    int pInd=partition(arr,start,end);

    if(pInd==k)

    return arr[pInd];

    if(k>pInd)

    {  

        quickSelect(arr,pInd+1,end,k);

    }

    else

    {  

        quickSelect(arr,start,pInd-1,k);

    }

}

Now let's do the analysis of QuickSelect algorithm: