DHA Suffa University
Department of Computer Science
CS 201L – Data Structures and Algorithms Lab
Spring 2019
Lab 08 – Recursion and Sorting Algorithms
Objective:
To learn about recursion and tracing of a recursive function.
To learn about the sorting Algorithms (Quick Sort and Merge Sort)
Recursion:
A function calling itself within its body is called recursive function. You can use recursion as an
alternative to iteration (looping). While using recursion, programmers need to be careful to
define an exit condition from the function, otherwise it will go into an infinite loop.
The recursive algorithms that we write will generally consist of an if statement with the
following form:
if this is a simple case
solve it
else
redefine the problem using recursion
Example01: Multiplying two numbers with recursive function.
Algorithm: multiply(m , n)
1. ans = 0
2. If (n == 1)
ans = m
else
ans = m + multiply (m , n-1)
3. return ans
Tracing a Recursive function:
Hand tracing an algorithm’s execution provides us with valuable insight into how that algorithm
works. We can trace the execution of a recursive function, and now we will illustrate how to do
this by studying the execution of a recursive function that returns a value.
In Example01, we wrote the algorithm for recursive function multiply(int firstNum, int
secondNum). We can trace the execution of the function call multiply(6, 3) by drawing an
activation frame corresponding to each call of the function. An activation frame shows the
parameter values for each call and summarizes the execution of the call.
Quick Sort:
Quick sort is a fast sorting algorithm, which is used not only for educational purposes, but widely applied
in practice. On the average, it has O(n log n) complexity, making quicksort suitable for sorting big data
[Link] are many different versions of quickSort that pick pivot in different ways.
● Always pick first element as pivot.
● Always pick last element as pivot
● Pick a random element as pivot.
● Pick median as pivot
Example 1:
#include <iostream>
void swap(int num1, int num2){
int temp = num1;
num1 = num2;
num2 = temp;
} //end swap
int partition (int *array, int start, int end){
//selecting pivot as last element
int pivot = array[end];
int pIndex = start;
for (int i = start; i < end-1; i++){
if (array [i] <= pivot){
swap(array [i], array [pIndex]);
pIndex = pIndex +1;
}//end if
}//end for i
swap(array [pIndex], array [end]);
return pIndex;
} //end partition
void quickSort(int *array, int start, int end){
//base casse to check whenever starting index is less than last
index
if (start < end){
// return the index for partition to pIndex
int pIndex = partition (array, start, end);
quickSort(array, start, pIndex - 1);
quickSort (array, pIndex + 1, end);
} //end if
} //end quickSort
//print array
void printArray(int *array, int n){
for (int i=0; i<n; i++)
std::cout << array[i] << " ";
} //end printArray
int main(){
int array[12]= {19, 6, 28, 1, 35, 69, 4, 2, 100, 99, 102, 13};
std::cout << "Array before sorting: " <<std::endl;
printArray(array, 12);
quickSort(array, 0, 11);
std::cout <<std::endl <<"Array after sorting: "<<std::endl;
//printArray(array, 12);
for (int i=0; i<12; i++)
std::cout << array[i] << " ";
return 0;
}
Merge Sort:
Merge sort is a sorting technique based on divide and conquer technique. With worst-case time
complexity being Ο(n log n), it is one of the most respected algorithms.
Merge sort first divides the array into equal halves and then combines them in a sorted manner.
How it works
Merge sort keeps on dividing the list into equal halves until it can no more be divided. By
definition, if it is only one element in the list, it is sorted. Then, merge sort combines the smaller
sorted lists keeping the new list sorted too.
I. If there is only one element in the list, it is already sorted, return.
II. Divide the list recursively into two halves until it can no more be divided.
III. Merge the smaller lists into new list in sorted order
Figure 4.1: Merge sort
Example 4:
#include<iostream>
void merge(int *A,int *L,int leftCount,int *R,int rightCount) {
int i,j,k;
i = 0; j = 0; k =0;
while(i<leftCount && j< rightCount)
{
if(L[i] < R[j])
{
A[k] = L[i];
k++;
i++;
}
else
{
A[k] = R[j];
k++;
j++;
}
}
while(i < leftCount)
{
A[k] = L[i];
k++;
i++;
}
while(j < rightCount)
{
A[k] = R[j];
k++;
j++;
}
}
void divide(int *A,int n) {
int mid,i, *L, *R;
if(n < 2)
{
return;
}
mid = n/2;
L = new int [mid];
R = new int [n-mid];
for(i = 0;i<mid;i++)
{
L[i] = A[i];
}
for(i = mid;i<n;i++)
{
R[i-mid] = A[i];
}
divide(L,mid);
divide(R,n-mid);
Merge(A,L,mid,R,n-mid);
}
int main() {
int A[] = {6,2,3,1,9,10,15,13,12,17};
int i;
divide(A,10);
for(i = 0;i < 10;i++)
{
std::cout << A[i] << std::endl;
}
return 0;
}