UNIT 3

Basic Algorithms

3.1 Basic Algorithms: Searching

Searching

Searching is the process of finding some particular element in the list. If the element is present in the list, then the process is called successful and the process returns the location of that element, otherwise the search is called unsuccessful.

There are two popular search methods that are widely used in order to search some item into the list. However, choice of the algorithm depends upon the arrangement of the list.

• Linear Search
• Binary Search

Linear Search

Linear search is the simplest search algorithm and often called sequential search. In this type of searching, we simply traverse the list completely and match each element of the list with the item whose location is to be found. If the match found then location of the item is returned otherwise the algorithm return NULL.

Linear search is mostly used to search an unordered list in which the items are not sorted. The algorithm of linear search is given as follows.

Algorithm

• LINEAR_SEARCH(A, N, VAL)
• Step 1: [INITIALIZE] SET POS = -1
• Step 2: [INITIALIZE] SET I = 1
• Step 3: Repeat Step 4 while I<=N
• Step 4: IF A[I] = VAL
  SET POS = I
  PRINT POS
  Go to Step 6
  [END OF IF]
  SET I = I + 1
  [END OF LOOP]
• Step 5: IF POS = -1
  PRINT " VALUE IS NOT PRESENTIN THE ARRAY "
  [END OF IF]
• Step 6: EXIT

Complexity of algorithm

C Program

1. #include<stdio.h>   
2. Void main ()  
3. {  
4.    Int a[10] = {10, 23, 40, 1, 2, 0, 14, 13, 50, 9};  
5.    Int item, i,flag;  
6.    Printf("\nEnter Item which is to be searched\n");  
7.    Scanf("%d",&item);  
8.    For (i = 0; i< 10; i++)  
9.    {  
10.        If(a[i] == item)   
11.        {  
12.            Flag = i+1;  
13.            Break;  
14.        }   
15.        Else   
16.        Flag = 0;  
17.    }   
18.    If(flag != 0)  
19.    {  
20.        Printf("\nItem found at location %d\n",flag);  
21.    }  
22.    Else  
23.    {  
24.        Printf("\nItem not found\n");   
25.    }  
26. }   

Output:

Enter Item which is to be searched

20

Item not found

Enter Item which is to be searched

23

Item found at location 2

Java Program

1. Import java.util.Scanner;  
2.  
3. Public class Leniear_Search {  
4. Public static void main(String[] args) {  
5.    Int[] arr = {10, 23, 15, 8, 4, 3, 25, 30, 34, 2, 19};  
6.    Int item,flag=0;   
7.    Scanner sc = new Scanner(System.in);  
8.    System.out.println("Enter Item ?");  
9.    Item = sc.nextInt();  
10.    For(int i = 0; i<10; i++)  
11.    {  
12.        If(arr[i]==item)  
13.        {  
14.            Flag = i+1;  
15.            Break;  
16.        }  
17.        Else   
18.            Flag = 0;   
19.    }  
20.    If(flag != 0)  
21.    {  
22.        System.out.println("Item found at location" + flag);  
23.    }  
24.    Else   
25.        System.out.println("Item not found");  
26.      
27. }  
28. }  

Output:

Enter Item ?

23

Item found at location 2

Enter Item ?

22

Item not found

C# Program

1. Using System;  
2.                  
3. Public class LinearSearch  
4. {  
5.    Public static void Main()  
6.    {  
7.        Int item, flag = 0;  
8.        Int[]  a= {10, 23, 5, 90, 89, 34, 12, 34, 1, 78};   
9.        Console.WriteLine("Enter the item value");  
10.        Item = Convert.ToInt32(Console.ReadLine());  
11.        For(int i=0;i<10;i++)  
12.        {  
13.            If(item == a[i])  
14.            {  
15.                Flag = i+1;  
16.                Break;  
17.            }  
18.            Else   
19.                Flag = 0;   
20.        }  
21.        If(flag != 0 )   
22.        {  
23.            Console.WriteLine("Item Found at Location " + flag);  
24.        }  
25.        Else   
26.            Console.WriteLine("Item Not Found");  
27.          
28.    }  
29. }  

Output:

Enter the item value

78

Item Found at Location 10

Enter the item value

22

Item not found

Python Program

1. Arr = [10,2,3,4,23,5,21,45,90,100];  
2. Item = int(input("Enter the item which you want to search "));  
3. For i in range (0,len(arr)):  
4.    If arr[i] == item:  
5.        Flag = i+1;  
6.        Break;  
7.    Else:   
8.        Flag = 0;   
9. If flag != 0:   
10.    Print("Item found at location %d" % (flag));  
11. Else :   
12.    Print("Item not found");  

Output:

Enter the item which you want to search 2

Item found at location 2

Enter the item which you want to search 101

Item not found

Binary Search

Binary search is the search technique which works efficiently on the sorted lists. Hence, in order to search an element into some list by using binary search technique, we must ensure that the list is sorted.

Binary search follows divide and conquer approach in which, the list is divided into two halves and the item is compared with the middle element of the list. If the match is found then, the location of middle element is returned otherwise, we search into either of the halves depending upon the result produced through the match.

Binary search algorithm is given below.

BINARY_SEARCH(A, lower_bound, upper_bound, VAL)

• Step 1: [INITIALIZE] SET BEG = lower_bound
  END = upper_bound, POS = - 1
• Step 2: Repeat Steps 3 and 4 while BEG <=END
• Step 3: SET MID = (BEG + END)/2
• Step 4: IF A[MID] = VAL
  SET POS = MID
  PRINT POS
  Go to Step 6
  ELSE IF A[MID] > VAL
  SET END = MID - 1
  ELSE
  SET BEG = MID + 1
  [END OF IF]
  [END OF LOOP]
• Step 5: IF POS = -1
  PRINT "VALUE IS NOT PRESENT IN THE ARRAY"
  [END OF IF]
• Step 6: EXIT

Complexity

Example

Let us consider an array arr = {1, 5, 7, 8, 13, 19, 20, 23, 29}. Find the location of the item 23 in the array.

In 1st step :

1. BEG = 0   
2. END = 8ron  
3. MID = 4   
4. a[mid] = a[4] = 13 < 23, therefore  

In Second step:

1. Beg = mid +1 = 5   
2. End = 8  
3. Mid = 13/2 = 6    
4. a[mid] = a[6] = 20 < 23, therefore;   

In third step:

1. Beg = mid + 1 = 7   
2. End = 8   
3. Mid = 15/2 = 7  
4. a[mid] = a[7]   
5. a[7] = 23 = item;   
6. Therefore, set location = mid;   
7. The location of the item will be 7.   

Binary Search Program using Recursion

C program

1. #include<stdio.h>  
2. Int binarySearch(int[], int, int, int);  
3. Void main ()  
4. {  
5.    Int arr[10] = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};  
6.    Int item, location=-1;   
7.    Printf("Enter the item which you want to search ");  
8.    Scanf("%d",&item);  
9.    Location = binarySearch(arr, 0, 9, item);  
10.    If(location != -1)   
11.    {  
12.        Printf("Item found at location %d",location);  
13.    }  
14.    Else  
15.    {  
16.        Printf("Item not found");  
17.    }  
18. }   
19. Int binarySearch(int a[], int beg, int end, int item)  
20. {  
21.    Int mid;  
22.    If(end >= beg)   
23.    {     
24.        Mid = (beg + end)/2;  
25.        If(a[mid] == item)  
26.        {  
27.            Return mid+1;  
28.        }  
29.        Else if(a[mid] < item)   
30.        {  
31.            Return binarySearch(a,mid+1,end,item);  
32.        }  
33.        Else   
34.        {  
35.            Return binarySearch(a,beg,mid-1,item);  
36.        }  
37.      
38.    }  
39.    Return -1;   
40. }  

Output:

Enter the item which you want to search

19

Item found at location 2

Java

1. Import java.util.*;  
2. Public class BinarySearch {  
3. Public static void main(String[] args) {  
4.    Int[] arr = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};  
5.    Int item, location = -1;  
6.    System.out.println("Enter the item which you want to search");  
7.    Scanner sc = new Scanner(System.in);  
8.    Item = sc.nextInt();  
9.    Location = binarySearch(arr,0,9,item);  
10.    If(location != -1)  
11.    System.out.println("the location of the item is "+location);  
12.    Else   
13.        System.out.println("Item not found");  
14.    }  
15. Public static int binarySearch(int[] a, int beg, int end, int item)  
16. {  
17.    Int mid;  
18.    If(end >= beg)   
19.    {     
20.        Mid = (beg + end)/2;  
21.        If(a[mid] == item)  
22.        {  
23.            Return mid+1;  
24.        }  
25.        Else if(a[mid] < item)   
26.        {  
27.            Return binarySearch(a,mid+1,end,item);  
28.        }  
29.        Else   
30.        {  
31.            Return binarySearch(a,beg,mid-1,item);  
32.        }  
33.      
34.    }  
35.    Return -1;   
36. }  
37. }  

Output:

Enter the item which you want to search

45

The location of the item is 5

C#

1. Using System;  
2.                  
3. Public class LinearSearch  
4. {  
5.    Public static void Main()  
6.    {  
7.    Int[] arr = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};  
8.    Int location=-1;   
9.    Console.WriteLine("Enter the item which you want to search ");  
10.    Int item = Convert.ToInt32(Console.ReadLine());  
11.    Location = binarySearch(arr, 0, 9, item);  
12.    If(location != -1)   
13.    {  
14.        Console.WriteLine("Item found at location "+ location);  
15.    }  
16.    Else  
17.    {  
18.        Console.WriteLine("Item not found");  
19.    }  
20. }   
21. Public static int binarySearch(int[] a, int beg, int end, int item)  
22. {  
23.    Int mid;  
24.    If(end >= beg)   
25.    {     
26.        Mid = (beg + end)/2;  
27.        If(a[mid] == item)  
28.        {  
29.            Return mid+1;  
30.        }  
31.        Else if(a[mid] < item)   
32.        {  
33.            Return binarySearch(a,mid+1,end,item);  
34.        }  
35.        Else   
36.        {  
37.            Return binarySearch(a,beg,mid-1,item);  
38.        }  
39.      
40.    }  
41.    Return -1;   
42.  
43.    }  
44. }  

Output:

Enter the item which you want to search

20

Item found at location 3

Python

1. Def binarySearch(arr,beg,end,item):  
2.    If end >= beg:  
3.        Mid = int((beg+end)/2)  
4.        If arr[mid] == item :  
5.            Return mid+1  
6.        Elif arr[mid] < item :   
7.            Return binarySearch(arr,mid+1,end,item)  
8.        Else:   
9.            Return binarySearch(arr,beg,mid-1,item)  
10.    Return -1  
11.      
12.  
13. Arr=[16, 19, 20, 23, 45, 56, 78, 90, 96, 100];  
14. Item = int(input("Enter the item which you want to search ?"))  
15. Location = -1;   
16. Location = binarySearch(arr,0,9,item);  
17. If location != -1:   
18.    Print("Item found at location %d" %(location))  
19. Else:   
20.    Print("Item not found")  

Output:

Enter the item which you want to search ?

96

Item found at location 9

Enter the item which you want to search ?

101

Item not found

Binary Search function using Iteration

1. Int binarySearch(int a[], int beg, int end, int item)  
2. {  
3.    Int mid;  
4.    While(end >= beg)   
5.    {     
6.        Mid = (beg + end)/2;  
7.        If(a[mid] == item)  
8.        {  
9.            Return mid+1;  
10.        }  
11.        Else if(a[mid] < item)   
12.        {  
13.            Beg = mid + 1;  
14.        }  
15.        Else   
16.        {  
17.            End = mid - 1;   
18.        }  
19.      
20.    }  
21.    Return -1;   
22. }   

3.2 Basic Sorting Algorithms (Bubble and Selection)

Bubble Sort

In Bubble sort, Each element of the array is compared with its adjacent element. The algorithm processes the list in passes. A list with n elements requires n-1 passes for sorting. Consider an array A of n elements whose elements are to be sorted by using Bubble sort. The algorithm processes like following.

1. In Pass 1, A[0] is compared with A[1], A[1] is compared with A[2], A[2] is compared with A[3] and so on. At the end of pass 1, the largest element of the list is placed at the highest index of the list.
2. In Pass 2, A[0] is compared with A[1], A[1] is compared with A[2] and so on. At the end of Pass 2 the second largest element of the list is placed at the second highest index of the list.
3. In pass n-1, A[0] is compared with A[1], A[1] is compared with A[2] and so on. At the end of this pass. The smallest element of the list is placed at the first index of the list.

Algorithm :

• Step 1: Repeat Step 2 For i = 0 to N-1
• Step 2: Repeat For J = i + 1 to N - I
• Step 3: IF A[J] > A[i]
  SWAP A[J] and A[i]
  [END OF INNER LOOP]
  [END OF OUTER LOOP
• Step 4: EXIT

Complexity

C Program

1. #include<stdio.h>  
2. Void main ()  
3. {  
4.    Int i, j,temp;   
5.    Int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};   
6.    For(i = 0; i<10; i++)  
7.    {  
8.        For(j = i+1; j<10; j++)  
9.        {  
10.            If(a[j] > a[i])  
11.            {  
12.                Temp = a[i];  
13.                a[i] = a[j];  
14.                a[j] = temp;   
15.            }   
16.        }   
17.    }   
18.    Printf("Printing Sorted Element List ...\n");  
19.    For(i = 0; i<10; i++)  
20.    {  
21.        Printf("%d\n",a[i]);  
22.    }  
23. }  

Output:

Printing Sorted Element List . . .

7

9

10

12

23

34

34

44

78

101

C++ Program

1. #include<iostream>  
2. Using namespace std;  
3. Int main ()  
4. {  
5.    Int i, j,temp;   
6.    Int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};   
7.    For(i = 0; i<10; i++)  
8.    {  
9.        For(j = i+1; j<10; j++)  
10.        {  
11.            If(a[j] < a[i])  
12.            {  
13.                Temp = a[i];  
14.                a[i] = a[j];  
15.                a[j] = temp;   
16.            }   
17.        }   
18.    }   
19.    Cout <<"Printing Sorted Element List ...\n";  
20.    For(i = 0; i<10; i++)  
21.    {  
22.        Cout <<a[i]<<"\n";  
23.    }  
24.    Return 0;  
25. }  

Output:

Printing Sorted Element List ...

7

9

10

12

23

23

34

44

78

101

Java Program

1. Public class BubbleSort {  
2.    Public static void main(String[] args) {  
3.    Int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
4.    For(int i=0;i<10;i++)  
5.    {  
6.        For (int j=0;j<10;j++)  
7.        {  
8.            If(a[i]<a[j])  
9.            {  
10.                Int temp = a[i];  
11.                a[i]=a[j];  
12.                a[j] = temp;   
13.            }  
14.        }  
15.    }  
16.    System.out.println("Printing Sorted List ...");  
17.    For(int i=0;i<10;i++)  
18.    {  
19.        System.out.println(a[i]);  
20.    }  
21. }  
22. }  

Output:

Printing Sorted List . . .

7

9

10

12

23

34

34

44

78

101

C# Program

1. Using System;  
2.                      
3. Public class Program  
4. {  
5.    Public static void Main()  
6.    {  
7.        Int i, j,temp;   
8.    Int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};   
9.    For(i = 0; i<10; i++)  
10.    {  
11.        For(j = i+1; j<10; j++)  
12.        {  
13.            If(a[j] > a[i])  
14.            {  
15.                Temp = a[i];  
16.                a[i] = a[j];  
17.                a[j] = temp;   
18.            }   
19.        }   
20.    }   
21.    Console.WriteLine("Printing Sorted Element List ...\n");  
22.    For(i = 0; i<10; i++)  
23.    {  
24.        Console.WriteLine(a[i]);  
25.    }  
26.    }  
27. }  

Output:

Printing Sorted Element List . . .

7

9

10

12

23

34

34

44

78

101

Python Program

1. a=[10, 9, 7, 101, 23, 44, 12, 78, 34, 23]  
2. For i in range(0,len(a)):  
3.    For j in range(i+1,len(a)):  
4.        If a[j]<a[i]:  
5.            Temp = a[j]  
6.            a[j]=a[i]  
7.            a[i]=temp  
8. Print("Printing Sorted Element List...")  
9. For i in a:   
10.    Print(i)  

Output:

Printing Sorted Element List . . .

7

9

10

12

23

34

34

44

78

101

Rust Program

1. Fn main()  
2. {  
3.    Let mut temp;  
4. Let mut a: [i32; 10] = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];  
5.    For i in 0..10  
6.    {  
7.        For j in (i+1)..10  
8.        {  
9.            If a[j] < a[i]  
10.            {  
11.                Temp = a[i];  
12.                a[i] = a[j];  
13.                a[j] = temp;   
14.            }  
15.        }   
16.    }   
17.    Println!("Printing Sorted Element List ...\n");  
18.    For i in &a  
19.    {  
20.        Println!("{} ",i);  
21.    }  
22. }  

Output:

Printing Sorted Element List . . .

7

9

10

12

23

34

34

44

78

101

4

JavaScript Program

1. <html>  
2. <head>  
3. <title>   
4. Bubble Sort   
5. </title>   
6. </head>   
7. <body>  
8. <script>   
9.    Var a = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];  
10.    For(i=0;i<10;i++)  
11.    {  
12.        For (j=0;j<10;j++)  
13.        {  
14.            If(a[i]<a[j])  
15.            {  
16.                 Temp = a[i];  
17.                a[i]=a[j];  
18.                a[j] = temp;   
19.            }  
20.        }  
21.    }  
22.    Txt = "<br>";  
23.    Document.writeln("Printing Sorted Element List ..."+txt);  
24.    For(i=0;i<10;i++)  
25.    {  
26.        Document.writeln(a[i]);  
27.        Document.writeln(txt);  
28.    }  
29.    </script>   
30.    </body>  
31. </html>  

Output:

Printing Sorted Element List ...

7

9

10

12

23

23

34

44

78

101

PHP Program

1. <html>  
2. <head>  
3. <title>Bubble Sort</title>  
4. </head>  
5. <body>  
6. <?php  
7.    $a = array(10, 9, 7, 101, 23, 44, 12, 78, 34, 23);  
8.    For($i=0;$i<10;$i++)  
9.    {  
10.        For ($j=0;$j<10;$j++)  
11.        {  
12.            If($a[$i]<$a[$j])  
13.            {  
14.                 $temp = $a[$i];  
15.                $a[$i]=$a[$j];  
16.                $a[$j] = $temp;   
17.            }  
18.        }  
19.    }  
20.    Echo "Printing Sorted Element List ...\n";  
21.    For($i=0;$i<10;$i++)  
22.    {  
23.        Echo $a[$i];  
24.        Echo "\n";  
25.    }  
26. ?>  
27. </body>  
28. </html>  

Output:

Printing Sorted Element List ...

7

9

10

12

23

23

34

44

78

101

Selection Sort

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.

The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right.

This algorithm is not suitable for large data sets as its average and worst case complexities are of Ο(n2), where n is the number of items.

How Selection Sort Works?

Consider the following depicted array as an example.

For the first position in the sorted list, the whole list is scanned sequentially. The first position where 14 is stored presently, we search the whole list and find that 10 is the lowest value.

So we replace 14 with 10. After one iteration 10, which happens to be the minimum value in the list, appears in the first position of the sorted list.

For the second position, where 33 is residing, we start scanning the rest of the list in a linear manner.

We find that 14 is the second lowest value in the list and it should appear at the second place. We swap these values.

After two iterations, two least values are positioned at the beginning in a sorted manner.

The same process is applied to the rest of the items in the array.

Following is a pictorial depiction of the entire sorting process −

Now, let us learn some programming aspects of selection sort.

Algorithm

Step 1 − Set MIN to location 0

Step 2 − Search the minimum element in the list

Step 3 − Swap with value at location MIN

Step 4 − Increment MIN to point to next element

Step 5 − Repeat until list is sorted

Pseudocode

Procedure selection sort

List  : array of items

n     : size of list

For i = 1 to n - 1

/* set current element as minimum*/

Min = i   

/* check the element to be minimum */

For j = i+1 to n

If list[j] < list[min] then

Min = j;

End if

End for

/* swap the minimum element with the current element*/

If indexMin != i  then

Swap list[min] and list[i]

End if

End for

End procedure

Selection Sort Program

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.

Implementation in C

#include <stdio.h>

#include <stdbool.h>

#define MAX 7

Int intArray[MAX] = {4,6,3,2,1,9,7};

Void printline(int count) {

Int i;

For(i = 0;i < count-1;i++) {

Printf("=");

}

Printf("=\n");

}

Void display() {

Int i;

Printf("[");

// navigate through all items

For(i = 0;i < MAX;i++) {

Printf("%d ", intArray[i]);

}

Printf("]\n");

}

Void selectionSort() {

Int indexMin,i,j;

// loop through all numbers

For(i = 0; i < MAX-1; i++) {

// set current element as minimum

IndexMin = i;

// check the element to be minimum

For(j = i+1;j < MAX;j++) {

If(intArray[j] < intArray[indexMin]) {

IndexMin = j;

}

}

If(indexMin != i) {

Printf("Items swapped: [ %d, %d ]\n" , intArray[i], intArray[indexMin]);

// swap the numbers

Int temp = intArray[indexMin];

IntArray[indexMin] = intArray[i];

IntArray[i] = temp;

}         

Printf("Iteration %d#:",(i+1));

Display();

}

} 

Void main() {

Printf("Input Array: ");

Display();

Printline(50);

SelectionSort();

Printf("Output Array: ");

Display();

Printline(50);

}

If we compile and run the above program, it will produce the following result −

Output

Input Array: [4 6 3 2 1 9 7 ]

==================================================

Items swapped: [ 4, 1 ]

Iteration 1#:[1 6 3 2 4 9 7 ]

Items swapped: [ 6, 2 ]

Iteration 2#:[1 2 3 6 4 9 7 ]

Iteration 3#:[1 2 3 6 4 9 7 ]

Items swapped: [ 6, 4 ]

Iteration 4#:[1 2 3 4 6 9 7 ]

Iteration 5#:[1 2 3 4 6 9 7 ]

Items swapped: [ 9, 7 ]

Iteration 6#:[1 2 3 4 6 7 9 ]

Output Array: [1 2 3 4 6 7 9 ]

==================================================

3.3 Finding roots of Equations

The standard form of a quadratic equation is:

Ax2 + bx + c = 0, where

a, b and c are real numbers and

a != 0

The term b2-4ac is known as the discriminant of a quadratic equation. It tells the nature of the roots.

• If the discriminant is greater than 0, the roots are real and different.
• If the discriminant is equal to 0, the roots are real and equal.
• If the discriminant is less than 0, the roots are complex and different.

Program to Find Roots of a Quadratic Equation

#include <math.h>

#include <stdio.h>

Int main() {

Double a, b, c, discriminant, root1, root2, realPart, imagPart;

Printf("Enter coefficients a, b and c: ");

Scanf("%lf %lf %lf", &a, &b, &c);

Discriminant = b * b - 4 * a * c;

// condition for real and different roots

If (discriminant > 0) {

Root1 = (-b + sqrt(discriminant)) / (2 * a);

Root2 = (-b - sqrt(discriminant)) / (2 * a);

Printf("root1 = %.2lf and root2 = %.2lf", root1, root2);

}

// condition for real and equal roots

Else if (discriminant == 0) {

Root1 = root2 = -b / (2 * a);

Printf("root1 = root2 = %.2lf;", root1);

}

// if roots are not real

Else {

RealPart = -b / (2 * a);

ImagPart = sqrt(-discriminant) / (2 * a);

Printf("root1 = %.2lf+%.2lfi and root2 = %.2f-%.2fi", realPart, imagPart, realPart, imagPart);

}

Return 0;

}

Output

Enter coefficients a, b and c: 2.3

4

5.6

Root1 = -0.87+1.30i and root2 = -0.87-1.30i

In this program, the sqrt() library function is used to find the square root of a number.

3.4 Functions: Functions (including using built in libraries)

In c, we can divide a large program into the basic building blocks known as function. The function contains the set of programming statements enclosed by {}. A function can be called multiple times to provide reusability and modularity to the C program. In other words, we can say that the collection of functions creates a program. The function is also known as procedureor subroutinein other programming languages.

Advantage of functions in C

There are the following advantages of C functions.

• By using functions, we can avoid rewriting same logic/code again and again in a program.
• We can call C functions any number of times in a program and from any place in a program.
• We can track a large C program easily when it is divided into multiple functions.
• Reusability is the main achievement of C functions.
• However, Function calling is always a overhead in a C program.

Function Aspects

There are three aspects of a C function.

• Function declaration A function must be declared globally in a c program to tell the compiler about the function name, function parameters, and return type.

• Function call Function can be called from anywhere in the program. The parameter list must not differ in function calling and function declaration. We must pass the same number of functions as it is declared in the function declaration.

• Function definition It contains the actual statements which are to be executed. It is the most important aspect to which the control comes when the function is called. Here, we must notice that only one value can be returned from the function.

The syntax of creating function in c language is given below:

1. Return_type function_name(data_type parameter...){  
2. //code to be executed  
3. }  

Types of Functions

There are two types of functions in C programming:

1. Library Functions: are the functions which are declared in the C header files such as scanf(), printf(), gets(), puts(), ceil(), floor() etc.
2. User-defined functions: are the functions which are created by the C programmer, so that he/she can use it many times. It reduces the complexity of a big program and optimizes the code.

Return Value

A C function may or may not return a value from the function. If you don't have to return any value from the function, use void for the return type.

Let's see a simple example of C function that doesn't return any value from the function.

Example without return value:

1. Void hello(){  
2. Printf("hello c");  
3. }  

If you want to return any value from the function, you need to use any data type such as int, long, char, etc. The return type depends on the value to be returned from the function.

Let's see a simple example of C function that returns int value from the function.

Example with return value:

1. Int get(){  
2. Return 10;  
3. }  

In the above example, we have to return 10 as a value, so the return type is int. If you want to return floating-point value (e.g., 10.2, 3.1, 54.5, etc), you need to use float as the return type of the method.

1. Float get(){  
2. Return 10.2;  
3. }  

Now, you need to call the function, to get the value of the function.

Different aspects of function calling

A function may or may not accept any argument. It may or may not return any value. Based on these facts, There are four different aspects of function calls.

• Function without arguments and without return value
• Function without arguments and with return value
• Function with arguments and without return value
• Function with arguments and with return value

Example for Function without argument and return value

Example 1

1. #include<stdio.h>  
2. Void printName();  
3. Void main ()  
4. {  
5.    Printf("Hello ");  
6.    PrintName();  
7. }  
8. Void printName()  
9. {  
10.    Printf("Javatpoint");  
11. }  

Output

Hello Javatpoint

Example 2

1. #include<stdio.h>  
2. Void sum();  
3. Void main()  
4. {  
5.    Printf("\nGoing to calculate the sum of two numbers:");  
6.    Sum();  
7. }  
8. Void sum()  
9. {  
10.    Int a,b;   
11.    Printf("\nEnter two numbers");  
12.    Scanf("%d %d",&a,&b);   
13.    Printf("The sum is %d",a+b);  
14. }  

Output

Going to calculate the sum of two numbers:

Enter two numbers 10

24

The sum is 34

Example for Function without argument and with return value

Example 1

1. #include<stdio.h>  
2. Int sum();  
3. Void main()  
4. {  
5.    Int result;   
6.    Printf("\nGoing to calculate the sum of two numbers:");  
7.    Result = sum();  
8.    Printf("%d",result);  
9. }  
10. Int sum()  
11. {  
12.    Int a,b;   
13.    Printf("\nEnter two numbers");  
14.    Scanf("%d %d",&a,&b);  
15.    Return a+b;   
16. }  

Output

Going to calculate the sum of two numbers:

Enter two numbers 10

24

The sum is 34

Example 2: program to calculate the area of the square

1. #include<stdio.h>  
2. Int sum();  
3. Void main()  
4. {  
5.    Printf("Going to calculate the area of the square\n");  
6.    Float area = square();  
7.    Printf("The area of the square: %f\n",area);  
8. }  
9. Int square()  
10. {  
11.    Float side;  
12.    Printf("Enter the length of the side in meters: ");  
13.    Scanf("%f",&side);  
14.    Return side * side;  
15. }  

Output

Going to calculate the area of the square

Enter the length of the side in meters: 10

The area of the square: 100.000000

Example for Function with argument and without return value

Example 1

1. #include<stdio.h>  
2. Void sum(int, int);  
3. Void main()  
4. {  
5.    Int a,b,result;   
6.    Printf("\nGoing to calculate the sum of two numbers:");  
7.    Printf("\nEnter two numbers:");  
8.    Scanf("%d %d",&a,&b);  
9.    Sum(a,b);  
10. }  
11. Void sum(int a, int b)  
12. {  
13.    Printf("\nThe sum is %d",a+b);      
14. }  

Output

Going to calculate the sum of two numbers:

Enter two numbers 10

24

The sum is 34

Example 2: program to calculate the average of five numbers.

1. #include<stdio.h>  
2. Void average(int, int, int, int, int);  
3. Void main()  
4. {  
5.    Int a,b,c,d,e;   
6.    Printf("\nGoing to calculate the average of five numbers:");  
7.    Printf("\nEnter five numbers:");  
8.    Scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);  
9.    Average(a,b,c,d,e);  
10. }  
11. Void average(int a, int b, int c, int d, int e)  
12. {  
13.    Float avg;   
14.    Avg = (a+b+c+d+e)/5;   
15.    Printf("The average of given five numbers : %f",avg);  
16. }  

Output

Going to calculate the average of five numbers:

Enter five numbers:10

20

30

40

50

The average of given five numbers : 30.000000

Example for Function with argument and with return value

Example 1

1. #include<stdio.h>  
2. Int sum(int, int);  
3. Void main()  
4. {  
5.    Int a,b,result;   
6.    Printf("\nGoing to calculate the sum of two numbers:");  
7.    Printf("\nEnter two numbers:");  
8.    Scanf("%d %d",&a,&b);  
9.    Result = sum(a,b);  
10.    Printf("\nThe sum is : %d",result);  
11. }  
12. Int sum(int a, int b)  
13. {  
14.    Return a+b;  
15. }  

Output

Going to calculate the sum of two numbers:

Enter two numbers:10

20

The sum is : 30  

Example 2: Program to check whether a number is even or odd

1. #include<stdio.h>  
2. Int even_odd(int);  
3. Void main()  
4. {  
5. Int n,flag=0;  
6. Printf("\nGoing to check whether a number is even or odd");  
7. Printf("\nEnter the number: ");  
8. Scanf("%d",&n);  
9. Flag = even_odd(n);  
10. If(flag == 0)  
11. {  
12.    Printf("\nThe number is odd");  
13. }  
14. Else   
15. {  
16.    Printf("\nThe number is even");  
17. }  
18. }  
19. Int even_odd(int n)  
20. {  
21.    If(n%2 == 0)  
22.    {  
23.        Return 1;  
24.    }  
25.    Else   
26.    {  
27.        Return 0;  
28.    }  
29. }  

Output

Going to check whether a number is even or odd

Enter the number: 100

The number is even

C Library Functions

Library functions are the inbuilt function in C that are grouped and placed at a common place called the library. Such functions are used to perform some specific operations. For example, printf is a library function used to print on the console. The library functions are created by the designers of compilers. All C standard library functions are defined inside the different header files saved with the extension .h. We need to include these header files in our program to make use of the library functions defined in such header files. For example, To use the library functions such as printf/scanf we need to include stdio.h in our program which is a header file that contains all the library functions regarding standard input/output.

The list of mostly used header files is given in the following table.

3.5 Parameter passing in functions

A function is a block of codes that performs a specific task and may return value. The main() function is the first user defined function invoked by the compiler. While it is possible to write any code within main function, it leads number of problems. The program may become too large and complex and it is difficult to test, debugg and maintain the complex code. For that reason, We use function to place independent code in separate modules called function or subprogram. In order to make a program using function, we need to perform the followling three steps.

• Function declaration
• Function definition
• Function call

Function declaration

Like variables, all the functions must be declared. Function declaration statement includes function name, what function will take and what function will return.

Syntax :

Return-type function-name(argument list);

Return-type : type of value function will return.

Function-name : any valid C identifier.

Argument list : represents the type and number of value function will take, values are sent by the calling statement.

Example for declaration of function

If we want to return the sum of two integer numbers and function will take two numbers as argument then the function declaration statement will be:

Int Add(int, int);

Function definition

Function definition includes the actual working or implementation.

Syntax for defining function

Return-type function-name(argument list)

{

- - - - - - - - - -

Body of function

- - - - - - - - - -

}

The body of function contains the number of statements to perform specific task.

Example for definition of function

The body of function for calculating sum of two integer numbers.

Int Add(int x,int y)

{

Int sum;

Sum = x + y;

Return sum;

}

Function call or Function invoke

To execute function we must call it. A function can be called or invoked by using function name followed by list of arguments (values) that function definition will recieve to perform task.

Syntax for calling or invoke function

Var = function-name(val1,val2...n);

Var can be any variable that will recieve value returning from function definition.

Example for calling or invoke function

Considering the above example, function calling statement should be :

Int rs;

Rs = Add(10,20);        //calling statement

Printf("\nThe sum is : %d",rs);

Passing argument to a function

Like normal variable, pointer variable can be passed as function argument and it can return from function.

There are two approaches to passing argument to a function:

• Call by Value
• Call by Reference/Address

Call by Value

In this approach, the values are passed as function argument to the definition of function.

Example of call by value

#include<stdio.h>

Void main()

{

Int A=10,B=20;

Printf("\nValues before calling %d, %d",A,B);

Fun(A,B);                           //Statement     1

Printf("\nValues after  calling %d, %d",A,B);

}

Void fun(int X,int Y)                   //Statement     2

{

X=11;

Y=22;

}

Output :

Values before calling 10, 20

Values after  calling 10, 20

In the above example, statement 1 is passing the values of A and B to the calling function fun(). Fun() will recieve the value of A and B and put it into X and Y respectively. X and Y are value type variables and are local to fun(). Any changes made by value type variables X and Y will not effect the values of A and B.

Call by Reference

In this approach, the references/addresses are passed as function argument to the definition of function.

Example of call by reference

#include<stdio.h>

Void main()

{

Int A=10,B=20;

Printf("\nValues before calling %d, %d",A,B);

Fun(&A,&B);                           //Statement     1

Printf("\nValues after  calling %d, %d",A,B);

}

Void fun(int *X,int *Y)                   //Statement     2

{

*X=11;

*Y=22;

}

Output :

Values before calling 10, 20

Values after  calling 11, 22

In the above example, statement 1 is passing the reference of A and B to the calling function fun(). Fun() must have pointer formal arguments to recieve the reference of A and B. In statement 2 *X and *Y is recieving the reference A and B. *X and *Y are reference type variables and are local to fun(). Any changes made by reference type variables *X and *Y will change the values of A and B respectively.

Difference between Call by Value and Call by Reference.

3.6 Call by value

Call by value and Call by reference in C

There are two methods to pass the data into the function in C language, i.e., call by value and call by reference.

Let's understand call by value and call by reference in c language one by one.

Call by value in C

• In call by value method, the value of the actual parameters is copied into the formal parameters. In other words, we can say that the value of the variable is used in the function call in the call by value method.
• In call by value method, we cannot modify the value of the actual parameter by the formal parameter.
• In call by value, different memory is allocated for actual and formal parameters since the value of the actual parameter is copied into the formal parameter.
• The actual parameter is the argument which is used in the function call whereas formal parameter is the argument which is used in the function definition.

Let's try to understand the concept of call by value in c language by the example given below:

1. #include<stdio.h>  
2. Void change(int num) {    
3.    Printf("Before adding value inside function num=%d \n",num);    
4.    Num=num+100;    
5.    Printf("After adding value inside function num=%d \n", num);    
6. }    
7. Int main() {    
8.    Int x=100;    
9.    Printf("Before function call x=%d \n", x);    
10.    Change(x);//passing value in function    
11.    Printf("After function call x=%d \n", x);    
12. Return 0;  
13. }    

Output

Before function call x=100

Before adding value inside function num=100

After adding value inside function num=200

After function call x=100

Call by Value Example: Swapping the values of the two variables

1. #include <stdio.h>  
2. Void swap(int , int); //prototype of the function   
3. Int main()  
4. {  
5.    Int a = 10;  
6.    Int b = 20;   
7.    Printf("Before swapping the values in main a = %d, b = %d\n",a,b); // printing the value of a and b in main  
8.    Swap(a,b);  
9.    Printf("After swapping values in main a = %d, b = %d\n",a,b); // The value of actual parameters do not change by changing the formal parameters in call by value, a = 10, b = 20  
10. }  
11. Void swap (int a, int b)  
12. {  
13.    Int temp;   
14.    Temp = a;  
15.    a=b;  
16.    b=temp;  
17.    Printf("After swapping values in function a = %d, b = %d\n",a,b); // Formal parameters, a = 20, b = 10   
18. }  

Output

Before swapping the values in main a = 10, b = 20

After swapping values in function a = 20, b = 10

After swapping values in main a = 10, b = 20 

Call by reference in C

• In call by reference, the address of the variable is passed into the function call as the actual parameter.
• The value of the actual parameters can be modified by changing the formal parameters since the address of the actual parameters is passed.
• In call by reference, the memory allocation is similar for both formal parameters and actual parameters. All the operations in the function are performed on the value stored at the address of the actual parameters, and the modified value gets stored at the same address.

Consider the following example for the call by reference.

1. #include<stdio.h>  
2. Void change(int *num) {    
3.    Printf("Before adding value inside function num=%d \n",*num);    
4.    (*num) += 100;    
5.    Printf("After adding value inside function num=%d \n", *num);    
6. }      
7. Int main() {    
8.    Int x=100;    
9.    Printf("Before function call x=%d \n", x);    
10.    Change(&x);//passing reference in function    
11.    Printf("After function call x=%d \n", x);    
12. Return 0;  
13. }    

Output

Before function call x=100

Before adding value inside function num=100

After adding value inside function num=200

After function call x=200

Call by reference Example: Swapping the values of the two variables

1. #include <stdio.h>  
2. Void swap(int *, int *); //prototype of the function   
3. Int main()  
4. {  
5.    Int a = 10;  
6.    Int b = 20;   
7.    Printf("Before swapping the values in main a = %d, b = %d\n",a,b); // printing the value of a and b in main  
8.    Swap(&a,&b);  
9.    Printf("After swapping values in main a = %d, b = %d\n",a,b); // The values of actual parameters do change in call by reference, a = 10, b = 20  
10. }  
11. Void swap (int *a, int *b)  
12. {  
13.    Int temp;   
14.    Temp = *a;  
15.    *a=*b;  
16.    *b=temp;  
17.    Printf("After swapping values in function a = %d, b = %d\n",*a,*b); // Formal parameters, a = 20, b = 10   
18. }  

Output

Before swapping the values in main a = 10, b = 20

After swapping values in function a = 20, b = 10

After swapping values in main a = 20, b = 10 

Difference between call by value and call by reference in c

3.7 Passing arrays to functions: idea of call by reference

In C, there are various general problems which requires passing more than one variable of the same type to a function. For example, consider a function which sorts the 10 elements in ascending order. Such a function requires 10 numbers to be passed as the actual parameters from the main function. Here, instead of declaring 10 different numbers and then passing into the function, we can declare and initialize an array and pass that into the function. This will resolve all the complexity since the function will now work for any number of values.

As we know that the array_name contains the address of the first element. Here, we must notice that we need to pass only the name of the array in the function which is intended to accept an array. The array defined as the formal parameter will automatically refer to the array specified by the array name defined as an actual parameter.

Consider the following syntax to pass an array to the function.

1. Functionname(arrayname);//passing array  

Methods to declare a function that receives an array as an argument

There are 3 ways to declare the function which is intended to receive an array as an argument.

First way:

1. Return_type function(type arrayname[])  

Declaring blank subscript notation [] is the widely used technique.

Second way:

1. Return_type function(type arrayname[SIZE])  

Optionally, we can define size in subscript notation [].

Third way:

1. Return_type function(type *arrayname)  

You can also use the concept of a pointer. In pointer chapter, we will learn about it.

C language passing an array to function example

1. #include<stdio.h>  
2. Int minarray(int arr[],int size){    
3. Int min=arr[0];    
4. Int i=0;    
5. For(i=1;i<size;i++){    
6. If(min>arr[i]){    
7. Min=arr[i];    
8. }    
9. }//end of for    
10. Return min;    
11. }//end of function    
12.    
13. Int main(){      
14. Int i=0,min=0;    
15. Int numbers[]={4,5,7,3,8,9};//declaration of array    
16.  
17. Min=minarray(numbers,6);//passing array with size    
18. Printf("minimum number is %d \n",min);    
19. Return 0;  
20. }    

Output

Minimum number is 3

C function to sort the array

1. #include<stdio.h>   
2. Void Bubble_Sort(int[]);  
3. Void main ()    
4. {    
5.    Int arr[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};     
6.    Bubble_Sort(arr);    
7. }    
8. Void Bubble_Sort(int a[]) //array a[] points to arr.   
9. {  
10. Int i, j,temp;     
11.    For(i = 0; i<10; i++)    
12.    {    
13.        For(j = i+1; j<10; j++)    
14.        {    
15.            If(a[j] < a[i])    
16.            {    
17.                Temp = a[i];    
18.                a[i] = a[j];    
19.                a[j] = temp;     
20.            }     
21.        }     
22.    }     
23.    Printf("Printing Sorted Element List ...\n");    
24.    For(i = 0; i<10; i++)    
25.    {    
26.        Printf("%d\n",a[i]);    
27.    }  
28. }  

Output

Printing Sorted Element List ...

7 

9 

10 

12 

23

23 

34 

44 

78 

101 

Returning array from the function

As we know that, a function cannot return more than one value. However, if we try to write the return statement as return a, b, c; to return three values (a,b,c), the function will return the last mentioned value which is c in our case. In some problems, we may need to return multiple values from a function. In such cases, an array is returned from the function.

Returning an array is similar to passing the array into the function. The name of the array is returned from the function. To make a function returning an array, the following syntax is used.

1. Int * Function_name() {  
2. //some statements;   
3. Return array_type;  
4. }  

To store the array returned from the function, we can define a pointer which points to that array. We can traverse the array by increasing that pointer since pointer initially points to the base address of the array. Consider the following example that contains a function returning the sorted array.

1. #include<stdio.h>   
2. Int* Bubble_Sort(int[]);  
3. Void main ()    
4. {    
5.    Int arr[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};     
6.    Int *p = Bubble_Sort(arr), i;  
7.    Printf("printing sorted elements ...\n");  
8.    For(i=0;i<10;i++)  
9.    {  
10.        Printf("%d\n",*(p+i));  
11.    }  
12. }    
13. Int* Bubble_Sort(int a[]) //array a[] points to arr.   
14. {  
15. Int i, j,temp;     
16.    For(i = 0; i<10; i++)    
17.    {    
18.        For(j = i+1; j<10; j++)    
19.        {    
20.            If(a[j] < a[i])    
21.            {    
22.                Temp = a[i];    
23.                a[i] = a[j];    
24.                a[j] = temp;     
25.            }     
26.        }     
27.    }     
28.    Return a;  
29. }  

Output

Printing Sorted Element List ...

7 

9  

10 

12 

23

23 

34 

44 

78 

101 

Reference:

1. Byron Gottfried, Schaum's Outline of Programming with C, McGraw-Hill

2. A.K. Sharma, Computer Fundamentals and Programming in C, Universities Press, 2nd Edition, 2018.

3. E. Balaguruswamy, Programming in ANSI C, Tata McGraw-Hill

4. Brian W. Kernighan and Dennis M. Ritchie, the C Programming Language, Prentice Hall of India.