Unit-5

Introduction Algorithms
• Roots of quadratic equation Algorithm

step 1: Start
step 2: Read a,b,c
step 3: intilize d<-(b*b)-(4*a*c)
step 4: intilize r<-b/2*a
step 5: if d>0 go to step 6
else go to step8
step 6: r1=r+(sqrt(d)/2*a) and r2=r-(sqrt(d)/2*a)
step 7: print roots are real and distinct ,first root r1,second root r2
step 8: if d=0 go to step9
else go to step10
step 9: print roots are real and equal,-r
step 10: d=-d
step 11: im=sqrt(d)/2*a
step 12: print roots are imaginary ,first root r+i im,second root r-i im
step 13: stop
• Algorithm to find the smallest and largest numbers
in an array
• Input the array elements.
• Initialize small = large = arr[0]
• Repeat from i = 2 to n.
• if(arr[i] > large)
• large = arr[i]
• if(arr[i] < small)
• small = arr[i]
• Print small and large.
 Searching
• A simple approach is to do linear search, i.e
• Start from the leftmost element of arr[] and one
by one compare x with each element of arr[]
• If x matches with an element, return the index.
• If x doesn’t match with any of elements,
• return -1.
• Input : arr[] = {10, 20, 80, 30, 60, 50, 110, 100,
130, 170}
• x = 110;
• Output : 6
• Element x is present at index 6
• Input : arr[] = {10, 20, 80, 30, 60, 50, 110, 100,
130, 170}
• x = 175;
• Output : -1
• Element x is not present in arr[].
• Binary Search: Search a sorted array by
repeatedly dividing the search interval in half.
Begin with an interval covering the whole
array. If the value of the search key is less than
the item in the middle of the interval, narrow
the interval to the lower half. Otherwise
narrow it to the upper half. Repeatedly check
until the value is found or the interval is
empty.
• We basically ignore half of the elements just
after one comparison.
• Compare x with the middle element.
• If x matches with middle element, we return
the mid index.
• Else If x is greater than the mid element, then
x can only lie in right half subarray after the
mid element. So we recur for right half.
• Else (x is smaller) recur for the left half.
 Sorting
• Introduction:A Sorting Algorithm is used to rearrange a given
array or list elements according to a comparison operator on
the elements. The comparison operator is used to decide
the new order of element in the respective data structure.
• Arranging the data in ascending or descending order is
known as sorting.
• Sorting is very important from the point of view of our
practical life.
• The best example of sorting can be phone numbers in our
phones. If, they are not maintained in an alphabetical order
we would not be able to search any number effectively.
• Many methods are used for sorting, such as:
1. Bubble sort
2. Selection sort
3. Insertion sort
• Bubble sort
• This is one of the most simple algorithm.
• The logic for this sort is that if the numbers are to be arranged in
an ascending order then the largest number will be pushed at the
end of the list.
• This process will be continued till all the numbers are placed in the
proper order.
• Every number will be scanned with the succeeding number and
they are swapped if the top number is larger than the succeeding
number.
• If the list is scanned once, it is called as a pass.
• Even if the list is passed once only the largest number is pushed at
the end the rest of the numbers are still not placed.
• For this, we may have to repeat this step many times to get the list
sorted properly.
• Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the
adjacent elements if they are in wrong order.
• Example:
First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and
swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5),
algorithm does not swap them.
• Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
• Now, the array is already sorted, but our algorithm does not know if it is completed.
The algorithm needs one whole pass without any swap to know it is sorted.
• Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
• void bubblesort(int a[ ], int n)
{
int p, c, i, j, temp;
p = n-1;
c = n;
for(i=1; i<=p; i++)
{
for(j=1; j<=c; j++);
{
if(a[j] > a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
• Selection sort
• This method of sorting is faster than the bubble sort as the
movement of data is minimized.
• Say we want to arrange data in ascending order, the largest
number is selected and placed at the end of the list.
• When the next pass takes place the second largest number is
selected and placed second last.
• This process is repeated until all the elements are placed in
the correct order.
• With each pass the elements are reduced by 1 as one
element is sorted and placed in a position.
• The selection sort algorithm sorts an array by
repeatedly finding the minimum element
(considering ascending order) from unsorted part
and putting it at the beginning. The algorithm
maintains two subarrays in a given array.
• 1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.
• In every iteration of selection sort, the minimum
element (considering ascending order) from the
unsorted subarray is picked and moved to the
sorted subarray.
• Following example explains the above steps:
• Example:
• arr[] = 64 25 12 22 11
• // Find the minimum element in arr[0...4]
• // and place it at beginning
• 11 25 12 22 64
• // Find the minimum element in arr[1...4]
• // and place it at beginning of arr[1...4]
• 11 12 25 22 64
• // Find the minimum element in arr[2...4]
• // and place it at beginning of arr[2...4]
• 11 12 22 25 64
• // Find the minimum element in arr[3...4]
• // and place it at beginning of arr[3...4]
• 11 12 22 25 64
• void selectionsort (int x[], int n)
{
int i, index, j, l;
for (i=n ; i>0; i--)
{
l=x[1];
i=1;
for(j=1; j<=i; j++)
{
if(x[j] > l)
{
l = x[j];
index = j;
}
}
x[index] = x[i];
x[i]=l;
}
}
• Insertion sort:
It is more efficient than bubble sort.
• The logic for this is that every element is
picked up and inserted in the proper place i.e.
if we pick up one element for inserting, all the
other elements will be put in the proper order.
• Insertion sort is a simple sorting algorithm that works
similar to the way you sort playing cards in your hands.
The array is virtually split into a sorted and an unsorted
part. Values from the unsorted part are picked and
placed at the correct position in the sorted part.
• Algorithm
To sort an array of size n in ascending order:
1: Iterate from arr[1] to arr[n] over the array.
2: Compare the current element (key) to its predecessor.
3: If the key element is smaller than its predecessor,
compare it to the elements before. Move the greater
elements one position up to make space for the
swapped element.
• Example:
12, 11, 13, 5, 6
• Let us loop for i = 1 (second element of the array) to 4 (last
element of the array)
• i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6
• i = 2. 13 will remain at its position as all elements in A[0..I-1] are
smaller than 13
11, 12, 13, 5, 6
• i = 3. 5 will move to the beginning and all other elements from 11
to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6
• i = 4. 6 will move to position after 5, and elements from 11 to 13
will move one position ahead of their current position.
5, 6, 11, 12, 13
• void insertionsort (int x[], int n)
{
int i,j,k;
for (i=1 ; i<=n; i++)
{
k=x[i];
for(j=i-1; j>=i && k<x[j]; j--)
{
x[j+1] = x[j];
}
x[j+1] = y;
}
}
• Asymptotic Notations
• Asymptotic notations are the mathematical notations used to describe
the running time of an algorithm when the input tends towards a
particular value or a limiting value.
• For example: In bubble sort, when the input array is already sorted, the
time taken by the algorithm is linear i.e. the best case.
• But, when the input array is in reverse condition, the algorithm takes the
maximum time (quadratic) to sort the elements i.e. the worst case.
• When the input array is neither sorted nor in reverse order, then it takes
average time. These durations are denoted using asymptotic notations.
• There are mainly three asymptotic notations: Theta notation, Omega
notation and Big-O notation.
• Theta Notation (Θ-notation)
• Theta notation encloses the function from
above and below. Since it represents the
upper and the lower bound of the running
time of an algorithm, it is used for analyzing
the average case complexity of an algorithm.
• Omega Notation (Ω-notation)
• Omega notation represents the lower bound
of the running time of an algorithm. Thus, it
provides best case complexity of an algorithm.

• https://www.programiz.com/dsa/asymptotic-notations
• Efficiency of an algorithm depends on two parameters:
• 1. Time Complexity
• 2. Space Complexity
• Time Complexity: Time Complexity is defined as the
number of times a particular instruction set is executed
rather than the total time is taken. It is because the
total time taken also depends on some external factors
like the compiler used, processor’s speed, etc.
• Space Complexity: Space Complexity is the total
memory space required by the program for its
execution.
• Time Complexity of Linear Search Algorithm is
Best:O(1)Average:O(n)
• Time Complexity of Binary Search Algorithm
is Best:O(1)Average:O(log2n).
• the complexity of bubble sort is only O(n).
the complexity of selection sort is only O(n2).
• the complexity ofinsertion sort is only O(n).
 Time complexities

• Selection sort : Best:Ω(n^2)

• Avgθ(n^2)
• WorstO(n^2)
• Bubble Sort: Best:Ω(n)
• θ(n^2)
• O(n^2)
• Insertion Sort: Ω(n)
• θ(n^2)
• O(n^2)
• How Insertion Sort Works?
• We take an unsorted array for our example.
• 14 33 27 10 35 19 42 44
• Insertion sort compares the first two elements.
• 14 33 27 10 35 19 42 44
• It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted sub-list.
• 14 33 27 10 35 19 42 44
• Insertion sort moves ahead and compares 33 with 27.
• 14 33 27 10 35 19 42 44
• And finds that 33 is not in the correct position.
• It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here we see that the
sorted sub-list has only one element 14, and 27 is greater than 14. Hence, the sorted sub-list
remains sorted after swapping.
• By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10.
• These values are not in a sorted order.
• So we swap them.
• However, swapping makes 27 and 10 unsorted.
• Hence, we swap them too.
• Again we find 14 and 10 in an unsorted order.
• We swap them again. By the end of third iteration, we have a sorted sub-list of 4 items.
•
https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm