Time to mergesort N elements Time to mergesort N2 elements plus time to merge two arrays each N2 elements.

PPS

Unit -7Recursion Q1. Define recursion. A1. In programming languages, if a program allows you to call a function inside the same function, then it is called a recursive call of the function.void recursion() {recursion(); /* function calls itself */}int main() { recursion();}The C programming language supports recursion, i.e., a function to call itself. But while using recursion, programmers has to be careful to define an exit condition from the function, otherwise it will go into an infinite loop.Recursive functions are useful to solve many mathematical problems, such as calculating the factorial of a number, generating Fibonacci series, etc.The following example calculates the factorial of a given number using a recursive function −#include <stdio.h>unsigned long long int factorial(unsigned int i) { if(i<= 1) { return 1; } return i * factorial(i - 1);}int main() { int i = 12;printf("Factorial of %d is %d\n", i, factorial(i)); return 0;}When the above code is compiled and executed, it produces the following result –Factorial of 12 is 479001600The following example generates the Fibonacci series for a given number using a recursive function −#include <stdio.h>int fibonacci(int i) { if(i == 0) { return 0; } if(i == 1) { return 1; } return fibonacci(i-1) + fibonacci(i-2);}int main() { int i; for (i = 0; i< 10; i++) {printf("%d\t\n", fibonacci(i)); } return 0;}When the above code is compiled and executed, it produces the following result −0 1 1 2 3 5 8 13 21 34 Q2. Explain the different ways of solving problems?A2. Recursion is a common form of the general-purpose problem-solving technique called divide and conquer''. The principle of divide-and-conquer, is that you solve a given problem P in 3 steps:

divide P into several subproblems, P1,P2,...Pn.

solve, however you can, each of the subproblems to get solutions S1...Sn.

Use S1...Sn to construct a solution to the original problem, P.

This is often recursive, because in order to solve one or more of the subproblems, you might use this very same strategy. For instance, you might solve P1 be subdividing it into P1a,P1b..., solving each one of them, and putting together their solutions to get the solution S1 to problem P1.Suppose we wished to sort the values in array X between positions FIRST and LAST. We can solve this directly in two very simple cases:FIRST=LAST:there is one number to be sorted, nothing needs to be done.FIRST+1=LAST:there are 2 numbers to be sorted; compare them and, if they are out of order, swap them.Otherwise, there are too many numbers to be sorted all at once, so we divide the problem into two subproblems by dividing the array into two parts:

P1: sort the numbers in X between positions FIRST and M; the answer is S1.

P2: sort the numbers in X between positions M+1 and LAST; the answer is S2.

The final answer is obtained by combining S1 and S2 in an appropriate way. The method for combining them is called merging', and it is a simple, efficient process. The exact way we divide up the array does not affect the correctness of this strategy: M can be any value at all, FIRST<M<LAST. Certain values of M correspond to well-known sorting algorithms:M = 1gives rise to the sorting algorithm called insertion sort.M = the midpoint between FIRST and LASTgives rise to the MergeSort algorithm. Q3. Write a program to find Fibonacci series?A3. Program to print Fibonacci series using recursion.#include<stdio.h>#include<conio.h> int Fibonacci(int);void main(){ int n, i, c=0;// n is no. of terms in Fibonacci series.printf(“Enter no. of terms in Fibonacci series”);scanf("%d",&n);printf("Fibonacci series\n"); for( i= 1 ; i<= n ; i++ ) {printf("%d\n", Fibonacci(c));c++; }getch();}int Fibonacci(int x){ if ( x == 0 ) return 0; else if ( x == 1 ) return 1; else return ( Fibonacci(x-1) + Fibonacci(x-2) );}Q4. Write a program to find the factorial of a number using recursion?A4.Program to find factorial of a number using recursion.

Q5. Write a program to reverse a string using recursion?A5. Recursive function (reverse) takes string pointer (str) as input and calls itself with next location to passed pointer (str+1). Recursion continues this way, when pointer reaches ‘\0’, all functions accumulated in stack print char at passed location (str) and return one by one.

Q6. Explain quick sort?A6. Quick sort is most efficient method of sorting .It uses divide and conquer strategy to sort the elements. In quicksort, we divide the array of items to be sorted into two partitions and then call the quicksort procedure recursively to sort the two partitions. For this we choose a pivot element and arrange all elements such that all the elements in the left part are less than the pivot and all those in the right part are greater than it.Algorithm to implement Quick Sort is as follows.Consider array A of size n to be sorted. p is pivot element. Index positions of first and last element of array A is denoted by ‘first’ and ‘last’.

Intially first=0 and last=n–1.

Increment first till A[first]<=p

Decrement last till A[last]>=p

If first < last then swap A[first] with A[last].

If first > last then swap p with A[last] and thus position of p is found. Pivot p is placed such that all elements to its left are less than it and all elements right to it are greater than it. Let us assume that j is final position of p. Then A[0] to A[j–1] are less than p and A [j + 1] to A [n–1]are greater than p.

Now we consider left part of array A i.e A[0] to A[j–1].Repeat step 1,2,3 and 4. Apply same procedure for right part of array.

We continue with above steps till no more partitions can be made for every subarray.

C function for Quick sort

x=0,y=n–1

void Quicksort(A,x,y)

{

if(x<y)

{

first=x;

last=y;

p=A[x];

while(first<last)

{

while(A[first]<p)

first++;

while(A[last]>p)

last ––;

if(first<last)

swap(A[first],A[last])

}

swap(A[x],A[y])

Quicksort(A,x,last–1);

Quicksort(A,first+1,y);

}

We will see examples on Quick sortExample : Apply Quicksort on array A= {27,6,39,2,65,12,57,18,49,19}

Here again first<last so we swap A[first] and A[last]. Swapping 65 and 18 we get Repeat step 2,3 and 4.

Now First>last so we swap pivot p with A[last]. Swapping 27 and 12 we get

Here we complete Pass 1.Now pivot element is 27 and it divides array in left and right partition. We can see that elements less than pivot are in left partition and elements greater than pivot are in right partition. Now we continue same procedure for left and right partition. Here we see results of corresponding passes. Pass 2 :

Pass 3 :

Pass 4 :

Pass 5 :

Pass 6 :

Pass 7 :

We will see another example.Example : Apply Quicksort on array A={21,55,49,38,13,93,87,9}Pass 1 :

Considering right partition

Hence the right partition is sorted . Final sorted array is

Q7. Explain merge sort?A7. Merge Sort is based on divide and conquer strategy. It divides the unsorted list into n sublists such that each sublist contains one element. Each sublist is then sorted and merged until there is only one sublist. Step 1 : Divide the list into sublists such that each sublist contains only one element. Step 2 : Sort each sublist and Merge them. Step 3 : Repeat Step 2 till the entire list is sorted. Example : Apply Merge Sort on array A= {85,24,63,45,17,31,96,50} Step1 : A contains 8 elements. First we divide the list into two sublists such that each sublist contains 4 elements. Then we divide each sublist of 4 elements into sublist of two elements each. Finally every sublist contains only one element.

Fig. 4.4Step 2 : Now we start from bottom. Compare 1st and 2nd element. Sort and merge them. Apply this for all bottom elements. Thus we got 4 sublists as follows

Step 3 : Repeat this sorting and merging until entire list is sorted. Thus above four sublists are sorted and merged to form 2 sublists.

Finally above 2 sublists are again sorted and merged in one sublist.

We will see one more example on merge sort.Algorithm for Merge Sort: Let x = no. of elements in array A y = no. of elements in array B C = sorted array with no. of elements n n = x+y Following algorithm merges a sorted x element array A and sorted y element array B into a sorted array C, with n = x + y elements. We must always keep track of the locations of the smallest element of A and the smallest element of B which have not yet been placed in C. Let LA and LB denote these locations, respectively. Also, let LC denote the location in C to be filled. Thus, initially, we set LA : = 1, LB : = 1 and LC : = 1. At each step , we compare A[LA] and B[LB] and assign the smaller element to C[LC]. Then LC:= LC + 1, LA: = LA + 1, if new element has come from A . LB: = LB + 1, if new element has come from B. Furthermore, if LA> x, then the remaining elements of B are assigned to C;

LB >y, then the remaining elements of A are assigned to C. Thus the algorithm becomes MERGING ( A, x, B, y, C) 1. [Initialize ] Set LA : = 1 , LB := 1 AND LC : = 1 2. [Compare] Repeat while LA <= x and LB <= y If A[LA] < B[LB] , then (a) [Assign element from A to C ] set C[LC] = A[LA] (b) [Update pointers ] Set LC := LC +1 and LA = LA+1 Else (a) [Assign element from B to C] Set C[LC] = B[LB] (b) [Update Pointers] Set LC := LC +1 and LB = LB +1 [End of loop] 3. [Assign remaining elements to C] If LA >x , then Repeat for K= 0 ,1,2,........,y–LB Set C[LC+K] = B[LB+K] [End of loop] Else Repeat for K = 0,1,2,......,x–LA Set C[LC+K] = A[LA+K] [End of loop] 4. Exit

Program for Merge Sort

#include<stdio.h>

#define MAX 50

void mergeSort(int A[],int first,intmid,int high);

void divide(int A[],int first,int last);

int main(){

int merge[MAX],i,n;

printf("Enter the total number of elements: ");

scanf("%d",&n);

printf("Enter the elements which to be sort: ");

for(i=0;i<n;i++){

scanf("%d",&merge[i]);

}

divide(merge,0,n–1);

printf("After merge sorting elements are: ");

for(i=0;i<n;i++){

printf("%d ",merge[i]);

}

return 0;

}

void divide(int A[],int first, int last)

{

int mid;

if(first<last){

mid=(first+last)/2;

divide(A,first,mid);

divide(A,mid+1,last);

mergeSort(A,first,mid,last);

}

void mergeSort(int A[],int first,intmid,int last)

{

int i,m,k,l,temp[MAX];

l=first;

i=first;

m=mid+1;

while((l<=mid)&&(m<=last)){

if(A[l]<=A[m]){

temp[i]=A[l];

l++;

}

else{

temp[i]=A[m];

m++;

}

i++;

}

if(l>mid){

for(k=m;k<=last;k++){

temp[i]=arr[k];

i++;

}

else{

for(k=l;k<=mid;k++){

temp[i]=arr[k];

i++;

}

for(k=first;k<=last;k++){

A[k]=temp[k];

}

Output : Enter the total number of elements: 5 Enter the elements which to be sort: 3 1 6 4 7 After merge sorting elements are: 1 3 4 6 7Complexity of Merge Sort :

Time to mergesort N elements = Time to mergesort N/2 elements plus time to merge two arrays each N/2 elements. Time to merge two arrays each N/2 elements is linear, i.e. N Thus we have: (1) T(1) = 1 (2) T(N) = 2T(N/2) + N Dividing (2) by N we get: (3) T(N) / N = T(N/2) / (N/2) + 1 N is a power of two, so we can write (4) T(N/2) / (N/2) = T(N/4) / (N/4) +1 (5) T(N/4) / (N/4) = T(N/8) / (N/8) +1 (6) T(N/8) / (N/8) = T(N/16) / (N/16) +1 (7) ……
(8) T(2) / 2 = T(1) / 1 + 1 Adding equations (3) through (8), the sum of their left–hand sides will be equal to the sum of their right–hand sides:T(N) / N + T(N/2) / (N/2) + T(N/4) / (N/4) + … + T(2)/2 = T(N/2) / (N/2) + T(N/4) / (N/4) + ….+ T(2) / 2 + T(1) / 1 + LogN(LogN is the sum of 1s in the right–hand sides) After crossing the equal term, we get (9) T(N)/N = T(1)/1 + LogN T(1) is 1, hence we obtain(10) T(N) = N + NlogN = O(NlogN) Hence the complexity of the MergeSort algorithm is O(NlogN).

Explain the difference between quick and merge sort?

Quick Sort	Merge Sort
An efficient sorting serving as a systematic method for placing the elements of an array in order	An efficient general purpose comparison based sorting algorithms
Sorts the elements by comparing each element with the pivot	Divides the array into 2 subarrays again and again until one element is left
Suitable for small arrays	Works for any type of array
Works faster for small data sets	Works in consistent speed for all data sheets
Requires minimum space	Requires more space

2. Write a program for merge sort?ANSWER-

Program for Merge Sort

#include<stdio.h>

#define MAX 50

void mergeSort(int A[],int first,intmid,int high);

void divide(int A[],int first,int last);

int main(){

int merge[MAX],i,n;

printf("Enter the total number of elements: ");

scanf("%d",&n);

printf("Enter the elements which to be sort: ");

for(i=0;i<n;i++){

scanf("%d",&merge[i]);

}

divide(merge,0,n–1);

printf("After merge sorting elements are: ");

for(i=0;i<n;i++){

printf("%d ",merge[i]);

}

return 0;

}

void divide(int A[],int first, int last)

{

int mid;

if(first<last){

mid=(first+last)/2;

divide(A,first,mid);

divide(A,mid+1,last);

mergeSort(A,first,mid,last);

}

void mergeSort(int A[],int first,intmid,int last)

{

int i,m,k,l,temp[MAX];

l=first;

i=first;

m=mid+1;

while((l<=mid)&&(m<=last)){

if(A[l]<=A[m]){

temp[i]=A[l];

l++;

}

else{

temp[i]=A[m];

m++;

}

i++;

}

if(l>mid){

for(k=m;k<=last;k++){

temp[i]=arr[k];

i++;

}

else{

for(k=l;k<=mid;k++){

temp[i]=arr[k];

i++;

}

for(k=first;k<=last;k++){

A[k]=temp[k];

}

Output : Enter the total number of elements: 5 Enter the elements which to be sort: 3 1 6 4 7 After merge sorting elements are: 1 3 4 6 7 Q8. Explain the complexity of merge sort?A8. Time to mergesort N elements = Time to mergesort N/2 elements plus time to merge two arrays each N/2 elements. Time to merge two arrays each N/2 elements is linear, i.e. N Thus we have: (1) T(1) = 1 (2) T(N) = 2T(N/2) + N Dividing (2) by N we get: (3) T(N) / N = T(N/2) / (N/2) + 1 N is a power of two, so we can write (4) T(N/2) / (N/2) = T(N/4) / (N/4) +1 (5) T(N/4) / (N/4) = T(N/8) / (N/8) +1 (6) T(N/8) / (N/8) = T(N/16) / (N/16) +1 (7) ……
(8) T(2) / 2 = T(1) / 1 + 1 Adding equations (3) through (8), the sum of their left–hand sides will be equal to the sum of their right–hand sides:T(N) / N + T(N/2) / (N/2) + T(N/4) / (N/4) + … + T(2)/2 = T(N/2) / (N/2) + T(N/4) / (N/4) + ….+ T(2) / 2 + T(1) / 1 + LogN(LogN is the sum of 1s in the right–hand sides) After crossing the equal term, we get (9) T(N)/N = T(1)/1 + LogN T(1) is 1, hence we obtain(10) T(N) = N + NlogN = O(NlogN) Hence the complexity of the MergeSort algorithm is O(NlogN). Q9. Write a program for quick sort.A9.

Program for Quick Sort:

#include<stdio.h>

void quicksort(int A[10],int,int);

int main(){

int A[20],n,i;

printf("Enter size of the array: ");

scanf("%d",&n);

printf("Enter %d elements: ",n);

for(i=0;i<n;i++)

scanf("%d",&A[i]);

quicksort(A,0,n–1);

printf("Sorted elements: ");

for(i=0;i<n;i++)

printf(" %d",A[i]);

return 0;

}

void quicksort(int A[20],int first, int last)

{

int pivot,j,temp,i;

if(first<last){

pivot=first;

i=first;

j=last;

while(i<j){

while(A[i]<=A[pivot]&&i<last)

i++;

while(A[j]>A[pivot])

j––;

if(i<j){

temp=A[i];

A[i]=A[j];

A[j]=temp;

}

temp=A[pivot];

A[pivot]=A[j];

A[j]=temp;

quicksort(A,first,j–1);

quicksort(A,j+1,last);

}

Output : Enter size of the array: 5 Enter 5 elements: 3 8 0 1 2 Sorted elements: 0 1 2 3 8 Complexity of Quick Sort The time to sort the file is equal to

the time to sort the left partition with i elements, plus

the time to sort the right partition with N–i–1 elements, plus

the time to build the partitions

Q10. Explain the complexity of quick sort?A10. For an array, in which partitioning leads to unbalanced subarrays, to an extent where on the left side there are no elements, with all the elements greater than the pivot, hence on the right side.And if keep on getting unbalanced subarrays, then the running time is the worst case, which is O(n2)If partitioning leads to almost equal subarrays, then the running time is the best, with time complexity as O(n*log n).Worst Case Time Complexity [ Big-O ]: O(n2)Best Case Time Complexity [Big-omega]: O(n*log n)Average Time Complexity [Big-theta]: O(n*log n)Space Complexity: O(n*log n)

Sign Up