Algorithms in C

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Agenda

● Algorithms
● Recursion
● Searching Algorithms
● Sorting Algorithms
[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
[email protected]
WNPDBIKTGR
Algorithms

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 What is an Algorithm?

● It is a step by step approach to solve a particular problem.

● It gives a crisp solution.

[email protected]
WNPDBIKTGR

● It can be understood by non-technical people as well.

● It’s free of programming language constructs.

● There can be multiple possible algorithm to solve a given problem.

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 What is an Algorithmic Analysis?

● It is a step by step approach to solve a particular problem.

● It gives a crisp solution.

[email protected]
WNPDBIKTGR

● It helps in the identification of optimal algorithm

● It helps in understanding the trade-off of time and space requirement.

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Algorithmic Analysis- Types

● There are different types of algorithmic analysis

○ Best case
○ Average case
[email protected]
WNPDBIKTGR ○ Worst case

● Worst case is computed always for the analysis as it dictates maximum

resource requirements.

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Time Complexity
● It determines the total number of unit operations to be undertaken to
solve a particular problem.

● Unit operation is an operation that is independent and can’t be broken

[email protected]
WNPDBIKTGR down in simpler operation.

● It is independent of architecture.

● It is computed on the basis of algorithm itself.

● It’s a high priority criteria in optimal algorithm selection.

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Time Complexity- Example 1

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Time Complexity- Example 2

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Space Complexity

● It determines the total space to be allocated in order to solve a

particular problem.
[email protected]
●
WNPDBIKTGR It is the extra memory that an algorithm needs for its implementation.

● It involves the memory of computers.

● It’s a low priority criteria in optimal algorithm selection.

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Space Complexity- Example 1

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Space Complexity- Example 2

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
[email protected]
WNPDBIKTGR
Recursion

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 What is Recursion?

● Recursion is about function calling itself.

● It comes intuitive when a function is breakable into subproblems.

[email protected]
WNPDBIKTGR

● There are many data structures which are recursive in nature.

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Steps of recursion

● Base condition

● Logic
[email protected]
WNPDBIKTGR

● Recursive call

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Recursion vs Iteration

● Recursion is about function calling itself whereas iteration can’t call

itself.
[email protected]
●
WNPDBIKTGR There is always some space complexity associated with recursion.

● Recursion implicitly works with stack data structure. There is no such

requirement in iteration.

● Recursion is slower than iteration.

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Tail Recursion

● Here the recursive call is the last step of implementation.

● This is a faster approach of recursion.

[email protected]
WNPDBIKTGR

● No activation record maintenance is required here.

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Tail Recursion- Example

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Non-Tail Recursion

● Here the recursive call is the not the last step of implementation.

● This is a slower approach of recursion.

[email protected]
WNPDBIKTGR

● Activation record maintenance is required here.

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Non-Tail Recursion- Example

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Direct Recursion

● When call within function call is made on the same function.

● f(){
[email protected]
WNPDBIKTGR f()
}

● Only one function is involved here.

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Direct Recursion- Example

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Indirect Recursion
● When call within function call is made on the different function.

● f1(){
f2()
}
[email protected]
WNPDBIKTGR

f2(){
f1()
}

● More than one functions are involved here.

This file is meant for personal use by [email protected] only.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Indirect Recursion- Example

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Recursion- Time Complexity

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Recursion- Space Complexity

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Binary Search Algorithm
[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 What is Binary Search?
● Binary Search is one of the searching techniques.
● It can be used on sorted array.
● This searching technique follows the divide and conquer strategy and
search space always reduces to half in every iteration.
[email protected]
WNPDBIKTGR
● This is a very efficient technique for searching but it needs some order
on which partition of the array will occur.

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Binary Search - Iterative Algorithm
binarySearch(arr, size)
loop until beg is not equal to end
midIndex = (beg + end)/2
if (item == arr[midIndex] )
[email protected]
WNPDBIKTGR
return midIndex
else if (item > arr[midIndex] )
beg = midIndex + 1
else
end = midIndex - 1

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Binary Search - Recursive Algorithm
binarySearch(arr, item, beg, end)
if beg<=end
midIndex = (beg + end) / 2
if item == arr[midIndex]
[email protected]
WNPDBIKTGR
return midIndex
else if item < arr[midIndex]
return binarySearch(arr, item, midIndex + 1, end)
else
return binarySearch(arr, item, beg, midIndex - 1)
return -1
This file is meant for personal use by [email protected] only.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Binary Search - Demonstration

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Binary Search – Implementation 1
int binarySearch(int arr[], int item, int beg, int end) {
while (beg <= end) {
int midIndex = beg + (end - beg) / 2;
if (arr[midIndex] == item)
[email protected]
WNPDBIKTGR
return midIndex;
if (arr[midIndex] > item)
beg = midIndex + 1;
else
end = midIndex - 1;
}
return -1;
}
This file is meant for personal use by [email protected] only.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Binary Search – Implementation 2
int binarySearch(int arr[], int item, int beg, int end) {
if (end >= beg) {
int midIndex = beg + (end - beg) / 2;
if (arr[midIndex] == item)
[email protected]
WNPDBIKTGR
return midIndex;
if (arr[midIndex] < item)
return binarySearch(arr, item, beg, midIndex - 1);
return binarySearch(arr, item, midIndex + 1, end);
}
return -1;
}
This file is meant for personal use by [email protected] only.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Selection Sort Algorithm
[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 What is Selection Sort?

● It is a simple sort algorithm that revolves around the ‘comparison’.

● In each iteration, one element gets placed.
● We choose the minimum element in the array and place is at the
beginning of the array by swapping with the front element.
[email protected]
WNPDBIKTGR
● We can also do this by choosing maximum element and placing it at the
rear end.
● Selection sort basically selects an element in every iteration and place it
at the appropriate position.

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Selection Sort - Algorithm

selectionSort(arr, n)
iterate (n - 1) times
set the first unsorted element index as the min
for each of the unsorted elements
[email protected]
WNPDBIKTGR
if element < currentMin
set element's index as new min
swap element at min with first unsorted position
end selectionSort

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Selection Sort - Demonstration

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Selection Sort - Demonstration Cont.

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Selection Sort - Implementation

void selectionSort(int arr[], int size) {

for (int j = 0; j < size - 1; j++) {
int min = j;
for (int i = j + 1; i < size; i++) {
[email protected]
WNPDBIKTGR
if(arr[i]<arr[min])
min = i;
}
int tmp = arr[j];
arr[j] = arr[min];
arr[min] = tmp;
}
} This file is meant for personal use by [email protected] only.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Insertion Sort Algorithm
[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 What is Insertion Sort?
● It is one of the easiest and brute force sorting algorithms
● Insertion sort is used to sort elements in either ascending or descending order
● In insertion sort, we maintain a sorted part and unsorted part
● It works just like playing cards i.e picking one card and sorting it with the cards that we
[email protected]
WNPDBIKTGR have in our hand already which in turn are sorted
● With every iteration, one item from unsorted is moved to the sorted part
● First element is picked and considered as sorted
● Then we start picking from 2nd elements onwards and start comparison
with elements in sorted part.
● We shift the elements from sorted by one element until an appropriate
location is not found for the picked element
● This continues till all the elements get exhausted
This file is meant for personal use by [email protected] only.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Insertion Sort - Algorithm

insertionSort(arr, size)
consider 1st element as sorted part
for each element from i=2 to n-1
[email protected] tmp = arr[i]
WNPDBIKTGR
for j=i-1 to 0
If a[j]>tmp
Then right shift it by one position
put tmp at current j

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Insertion Sort - Demonstration

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning.
Sharing All Rights
or publishing theReserved. Unauthorized
contents in use
part or full is or distribution
liable prohibited
for legal action.
 Insertion Sort - Demonstration Cont.

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Insertion Sort - Implementation
void insertionSort(int arr[], int size) {
for (int i = 1; i < size; i++) {
int tmp = arr[i];
int j = i - 1;
[email protected]
WNPDBIKTGR while (j >= 0 && tmp < arr[j]) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = tmp;
}
}
This file is meant for personal use by [email protected] only.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Quick Sort Algorithm
[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 What is Quick Sort?

● It is one of the most widely used sorting algorithm

● It follows divide and conquer paradigm
● Recursion is used in quicksort implementation
● In each recursive call, a pivot is chosen then the array is partitioned in such a way
[email protected]
WNPDBIKTGR that all the elements less than pivot lie to the left and all the elements greater
than pivot lie to the right
● After every call, the chosen pivot occupies its correct position in
the array which it is supposed to as in sorted array
● So with each step, our problem gets reduced by 2 which leads to
quick sorting
● Pivot can be an element. Example: last element of current array,
first element of current array, random pivot, etc.
This file is meant for personal use by [email protected] only.
Proprietary content. ©Great
SharingLearning. All Rights
or publishing Reserved.inUnauthorized
the contents part or full is use or for
liable distribution prohibited
legal action.
 Quick Sort - Algorithm

quickSort(arr, beg, end)

if (beg < end)
pivotIndex = partition(arr,beg, end)
[email protected]
WNPDBIKTGR
quickSort(arr, beg, pivotIndex -1)
quickSort(arr, pivotIndex + 1, end)

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Partition - Algorithm

partition(arr, beg, end)

set end as pivotIndex
pIndex = beg - 1
for i = beg to end-1
[email protected]
WNPDBIKTGR
if arr[i] < pivot
swap arr[i] and arr[pIndex]
pIndex++
swap pivot and arr[pIndex+1]
return pIndex + 1

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Quick Sort - Demonstration

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Quick Sort - Implementation

void quickSort(int[] a,int p,int r)

{
if(p<r)
[email protected]{
WNPDBIKTGR
int q=partition(a,p,r);
quickSort(a,p,q-1);
quickSort(a,q+1,r);
}
}

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Quick Sort – Implementation Cont.
int partition_function(int arr[], int l, int h){
int pivot = arr[h]; // pivot is the last element
int pIndex = (l - 1); // Index of smaller element
for (int j = l; j <= h- 1; j++){
[email protected]
WNPDBIKTGR
if (arr[j] < p){
i++;
swap_elements(&arr[i], &arr[j]);
}
}
swap_elements(&arr[i + 1], &arr[h]);
return (i + 1);
This file is meant for personal use by [email protected] only.
} Proprietary content. ©Great
SharingLearning. All Rights
or publishing Reserved.inUnauthorized
the contents part or full is use or for
liable distribution prohibited
legal action.
 Merge Sort Algorithm
[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 What is Merge Sort?

• In merge sort, the problem is divided into two sub problems in every
iteration
• Hence efficiency is increased drastically
• It follows divide and conquer approach
[email protected]
WNPDBIKTGR • Divide break the problem into 2 sub problem which continues until
problem set is left with one element only
• Conquer basically merges the 2 sorted array into the
original array

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Merge Sort - Algorithm

mergeSort(arr, left, right)

if left > right
return
mid = (left+right)/2
[email protected]
WNPDBIKTGR mergeSort(arr, left, mid)

mergeSort(arr, mid+1, right)

merge(arr, left, mid, right)
end

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Merge Sort - Demonstration

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great
SharingLearning. All Rights
or publishing Reserved.inUnauthorized
the contents part or full is use or for
liable distribution prohibited
legal action.
 Merge - Algorithm

• Create 2 subarrays Left and Right

• Create 3 iterators i, j and k
• Insert elements in Left and Right ( i & j)
• k - Replace the values in the original array
[email protected]
WNPDBIKTGR • Pick the larger elements from Left and Right & place them in the correct
position
• If there are no elements in either Left or Right, pick up
the remaining elements either from Left or Right and
insert in original array

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Merge - Demonstration

[email protected]
WNPDBIKTGR

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Merge Sort - Implementation

void mergeSort(int arr[], int start, int right) {

if (start < right) {
int mid = (start + right) / 2;
mergeSort(arr, start, mid);
[email protected]
WNPDBIKTGR
mergeSort(arr, mid + 1, right);
merge(arr, start, mid, right);
}
}

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Merge Sort – Implementation Cont.

void merge(int arr[], int start, int mid, int end) {

int len1 = mid - start + 1;
int len2 = end - mid;
[email protected]
WNPDBIKTGR
int leftArr[len1], rightArr[len2];

for (int i = 0; i < len1; i++)

leftArr[i] = arr[start + i];
for (int j = 0; j < len2; j++)
rightArr[j] = arr[mid + 1 + j];
This file is meant for personal use by [email protected] only.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Merge Sort – Implementation Cont.
int i, j, k;
i = 0;
j = 0;
k = start;
while (i < len1 && j < len2) {
[email protected]
WNPDBIKTGRif (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
This file is meant for personal use by [email protected] only.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Merge Sort – Implementation Cont.

while (i < len1) {

arr[k] = leftArr[i];
i++;
WNPDBIKTGRk++;
[email protected]

}
while (j < len2) {
arr[k] = rightArr[j];
j++;
k++;
}
} Proprietary content. ©Great
This file is meant for personal use by [email protected] only.
Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Quick Sort Vs Merge Sort
QUICK SORT MERGE SORT
Splitting of array depends on the Splitting of array generally done on half
value of pivot and other array
elements
Worst case time complexity
[email protected] is O(n2) Worst case time complexity is O(nlogn)
WNPDBIKTGR
It takes less n space than merge sort It takes more n space than quick sort
It work faster than other sorting It has a consistent speed on any size of
algorithms for small data set like data
Selection sort etc
It is in-place It is out-place
Not stable Stable
This file is meant for personal use by [email protected] only.
Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.
 Summary

● Algorithm and its analysis

● What is Recursion?
● Binary Search
● Sorting Algorithms
[email protected]
WNPDBIKTGR
○ Selection Sort
○ Insertion Sort
○ Quick Sort
○ Merge Sort

This file is meant for personal use by [email protected] only.

Proprietary content. ©Great Learning. All Rights Reserved. Unauthorized use or distribution prohibited
Sharing or publishing the contents in part or full is liable for legal action.