Algorithm Development

Algorithm in C language
An algorithm is a sequence of instructions that are carried out in a predetermined sequence in order
to solve a problem or complete a work. A function is a block of code that can be called and executed
from other parts of the program.
A set of instructions for resolving an issue or carrying out a certain activity. In computer science,
algorithms are used for a wide range of operations, from fundamental math to intricate data
processing.
One of the common algorithms used in C is the sorting algorithm. A sorting algorithm arranges a
collection of items in a certain order, such as numerically or alphabetically.
There are many sorting algorithms, each with advantages and disadvantages. The most common
sorting algorithms in C are quicksort, merge, and sort.

Features of the algorithm

It defines several important features of the algorithm, including:
1. Inputs: Algorithms must receive inputs that can be represented as values or data.
2. Output: The algorithm should produce some output. It can be a consequence of a problem
or a solution designed to solve it.
3. Clarity: Algorithms must be precisely defined, using unambiguous instructions that a
computer or other system can follow unambiguously.
4. Finiteness: The algorithm requires a limited steps. It means that it should be exited after
executing a certain number of commands.
5. Validity: The algorithm must be valid. In other words, it should be able to produce a
solution to the problem that the algorithm is designed to solve in a reasonable amount of
time.
6. Effectiveness: An algorithm must be developed by using very basic, simple, and feasible
operations so that one can trace it out by using just paper and pencil.
7. Generality: An algorithm must be general, meaning that it can be applied to a wide range
of problems rather than being specific to a single problem.

Algorithm Analysis

Algorithmic analysis is the process of evaluating algorithm performance in terms of efficiency,

complexity and other criteria. Typically, this is done to evaluate many algorithms and select the
optimal solution for a certain issue or a software.

Analysis of algorithms usually involves measuring their time and space complexity.
As with space complexity, which describes the amount of memory or disk space needed, time
complexity describes how long an algorithm determines to perform a task.

There are different ways to analyze the time complexity of algorithms, such as Big O and Omega
notation.

In addition to measuring time and space complexity, algorithm analysis also includes other criteria
such as stability, parallelism, and scalability.

 Stability - This refers to the ability of the algorithm to maintain the relative order of the
elements in the data set.
 Parallelization - This is referring to the capacity to execute operations in parallel across
several processors.
 Scalability - On the other hand, it refers to the ability of an algorithm to handle large
volumes of data and other inputs.
We put all analysis of algorithm in two types. They are:-
1. Prior-analysis.
2. Posterior analysis.

1. Prior Analysis: “Priori” means “before”. Hence Priori analysis means checking the
algorithm before its implementation. In this, the algorithm is checked when it is written in
the form of theoretical steps. This Efficiency of an algorithm is measured by assuming that
all other factors, for example, processor speed, are constant and have no effect on the
implementation. This is done usually by the algorithm designer. This analysis is
independent of the type of hardware and language of the compiler. It gives the approximate
answers for the complexity of the program.
2. Posterior analysis: “Posterior” means “after”. Hence Posterior analysis means checking
the algorithm after its implementation. In this, the algorithm is checked by implementing
it in any programming language and executing it. This analysis helps to get the actual and
real analysis report about correctness(for every possible input/s if it shows/returns correct
output or not), space required, time consumed, etc. That is, it is dependent on the language
of the compiler and the type of hardware used.

Algorithm Complexity

Algorithmic complexity is a measure to measure the efficiency and performance of the algorithm.
Algorithms are usually evaluated in terms of the time and space required to solve a problem or
achieve a specific goal.

Two factors are used in the complexity of the algorithm. They are:-
1. Time factor.
2. Space factor.

 Time factor:

1. The amount of time an algorithm needs to do a task is referred to as time complexity.It is

usually measured by the number of operations or steps an algorithm must perform to solve
a problem.
2. The time complexity of an algorithm is important because it determines how long it takes
to execute and can have a significant impact on program and system performance.
3. The time complexity of an algorithm can be expressed using Big O notation, a way of
expressing an upper bound on the time complexity of an algorithm.
4. An algorithm with time complexity O(n) means that the time required to run the algorithm
is directly proportional to the size of the input data (n).
5. Other common time complexities are O(n^2) quadratic complexity and O(log n)
logarithmic complexity.

 Space analysis:

1. On the other hand, space complexity refers to the amount of memory or storage space
required to execute the algorithm.
2. This is important because it determines the number of resources required to run algorithms
that can affect the overall performance of your application or system.
3. If the space complexity of the algorithm is O(n), it uses an amount of memory that grows
linearly with the size of the input.
If the algorithm has O(1) space complexity, it uses a fixed amount of memory regardless of the
size of the input.

How to write an algorithm

1. First define the problem you want the algorithm to solve.
For example, suppose we want to write an algorithm to find the maximum value from a list of
numbers.

2. Break the problem down into smaller, manageable steps.

o Initialize the 'max' variable to the first value in the list.

 o For each subsequent value in the list, compare with "max".
o If the value is greater than "max", set "max" to that value.
o Continue doing this until every value in the list has been compared.
o Returns the final "max" value.

3. Write your algorithm in pseudocode or a programming language.

Algorithm written in pseudo code:

MAX (list)
max = list[0]
For i = 1 the length of the list
list IF[i] > max
max = list[i]
End for
Maximum return
Maximum end

4. Test your algorithm to make sure it is correct and efficient.

You can test the algorithm by entering different lists of numbers and verifying that it returns the
maximum correct value. You can also analyze the time complexity of your algorithm to determine
how well it scales for larger inputs.
Example:-
Input: [1, 5, 2, 7, 3]
Output: 7.
Explanation: 7 is the maximum value in the list.

5. Optimize the algorithm.

Look for ways to optimize algorithms for making them faster and more efficient. This may involve
modifying pseudocode or implementing more efficient data structures or algorithms.

Basic writing of algorithms

 Example: - The sum of two integers.
Step 1 - Get started
Step 2 - Declare three integers a, b, c
Step 3 - Define the values of a and b
Step 4 - Add the values of a and b
Step 5 - Save the output of step 4 in c
Step 6 - Print c
Step 7 - Stop

Type of algorithms used in C language.

1. Sorting algorithms
2. Searching algorithms
3. Graph algorithms
4. Cryptographic Algorithms

Advantages of the algorithm

Algorithms have many advantages. They are:-
1. Speed and efficiency: Algorithms can process large amounts of data quickly and
accurately, making them useful for tasks that are too time-consuming or error-prone for
people to perform.
2. Consistency: Algorithms follow a set of predetermined guidelines. It can produce
consistent results without being influenced by personal biases and emotions.
3. Automation: Algorithms can perform tasks automatically, leaving people free to focus on
more complex or creative tasks.
4. Increased accuracy: Algorithms can often achieve higher levels of accuracy than humans,
especially when dealing with large amounts of data.
5. Better Decision Making: Algorithms help us make more informed and objective decisions
by analyzing data and identifying patterns and trends that are not easily visible to people.
6. Scalability: Algorithms can be easily scaled up or down to meet changing demands and
workloads.

Disadvantages of the algorithm

Algorithms are very useful for programming, but algorithms have drawbacks. They are:-
 1. Limited scope: Algorithms can only solve problems within their scope and may not be
able to solve complex or abstract problems.
2. Bias: Algorithms can perpetuate and reinforce biases in the data used for training, leading
to unfair results.
3. Insufficient transparency: Many algorithms conceal the process through which they
arrive at their conclusions. This could make it tough to think about or check the results.
4. Reliance on the fineness of the data: The correctness of the set of rules is heavily
dependent on the fineness and applicability of the data utilised in instruction. Inaccurate or
inaccurate effects may be the result of faulty data.
5. Restrained adaptability: Algorithms are designed to follow guidelines and won't adapt to
changing circumstances and conditions.

Prime Number program in C

Prime number in C: Prime number is a number that is greater than 1 and divided by 1 or itself. In
other words, prime numbers can't be divided by other numbers than itself or 1. For example 2, 3,
5, 7, 11, 13, 17, 19, 23.... are the prime numbers.

Let's see the prime number program in C. In this c program, we will take an input from the user
and check whether the number is prime or not.

#include<stdio.h>
int main(){
int n, i, m=0, flag=0;
printf("Enter the number to check prime:");
scanf("%d",&n);
m=n/2;
for(i=2;i<=m;i++)
{
if(n%i==0)
{
printf("Number is not prime");
flag=1;
break;
}
}
if(flag==0)
printf("Number is prime");
return 0;
}

Output:
Enter the number to check prime:56
Number is not prime
Enter the number to check prime:23
Number is prime

Random number generation

Random Function in C
In this topic, we will learn about the random function and how we can generate the random number
in the C programming language. As we know, the random function is used to find the random
number between any two defined numbers. In the C programming language, the random function
has two inbuilt functions: rand() and srand() function. Let's understand these functions in the C
language.

rand() function
In the C programming language, the rand() function is a library function that generates the random
number in the range [0, RAND_MAX]. When we use the rand() function in a program, we need
to implement the stdlib.h header file because rand() function is defined in the stdlib header file. It
does not contain any seed number. Therefore, when we execute the same program again and again,
it returns the same values.
The rand() function returns the random integers whose range from 0 to RAND_MAX. The
RAND_MAX is a symbolic constant that defines in stdlib.h header file, whose value is greater but
less than 32767 depending on the C libraries.

Generate the random numbers using the rand() function

Let's write a program to get the random number using rand() function.
num.c
1. #include <stdio.h>
2. #include <conio.h>
3. #include <stdlib.h>
4. void main()
5. {
6. // use rand() function to generate the number
7. printf (" The random number is: %d", rand());
8. printf ("\n The random number is: %d", rand());
9.
10. printf (" \n The random number is: %d", rand());
11. printf ("\n The random number is: %d", rand());
12. getch();
13. }
Generate 5 random numbers using rand() function
Let's consider a program to generate 5 random number using rand() function in C programming
language.
random.c
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i;
/* It returns the same sequence of random number
on every execution of the program. */
printf(" Random Numbers are: \n");
for (i = 0; i <5; i++)
{
printf(" %d", rand());
}
return 0;
}
Output

Random Numbers are:

41 18467 6334 26500 19169
2nd execution of the program:

Random Numbers are:

41 18467 6334 26500 19169
3rd execution of the program

Random Numbers are:

41 18467 6334 26500 19169
As we can see in the above output, it returns the same sequence of random numbers on every
execution of the programming code.
Generate 10 random numbers from 1 to 100 using rand() function
Let's consider a program to find the random number in C using rand() function.
rand_num.c
 1. #include <stdio.h>
2. #include <conio.h>
3. #include <stdlib.h>
4. int main()
5. {
6. // declare the local variables
7. int i, num;
8. printf (" Program to get the random number from 1 to 100 \n");
9. for (i = 1; i <= 10; i++)
10. {
11. num = rand() % 100 + 1; // use rand() function to get the random number
12. printf (" %d ", num);
13. getch();
14. }
15. }
Output
Program to get the random number from 1 to 100
42 68 35 1 70 25 79 59 63 65

srand() function
The srand() function is a C library function that determines the initial point to generate different
series of pseudo-random numbers. A srand() function cannot be used without using a rand()
function. The srand() function is required to set the value of the seed only once in a program to
generate the different results of random integers before calling the rand() function.
Syntax
1. int srand (unsigned int seed)
seed: It is an integer value that contains a seed for a new sequence of pseudo-random numbers.
Generate the random numbers using srand() function
Let's write a program to get the random numbers using srand() function in C.
srandNum.c
1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <time.h> // use time.h header file to use time
4.
5. int main()
6. {
7. int num, i;
8. time_t t1; // declare time variable
9.
10. printf(" Enter a number to set the limit for a random number \n");
11. scanf (" %d", &num);
12.
13. /* define the random number generator */
14. srand ( (unsigned) time (&t1)); // pass the srand() parameter
15. printf("\n"); // print the space
16. /* generate random number between 0 to 50 */
17. for (i = 0; i <num; i++)
18. {
19. printf( "%d \n", rand() % 50);
20. }
21. return 0;
22. }
Output
Enter a number to set the limit for a random number
10
44 32 23 35 6 33 1 4 22 18
2nd execution of the program:
Enter a number to set the limit for a random number
15
13 30 24 27 4 30 28 35 36 13 44

As we can see in the above Output, it returns different sequences of random numbers on every
execution of the programming code.

Euclid algorithm for gcd finding

The Euclidean algorithm is a way to find the greatest common divisor of two positive integers.
GCD of two numbers is the largest number that divides both of them. A simple way to find GCD
is to factorize both numbers and multiply common prime factors.

Basic Euclidean Algorithm for GCD:

The algorithm is based on the below facts.
 If we subtract a smaller number from a larger one (we reduce a larger number), GCD doesn’t
change. So if we keep subtracting repeatedly the larger of two, we end up with GCD.
 Now instead of subtraction, if we divide the smaller number, the algorithm stops when we find
the remainder 0.

Below is a recursive function to evaluate gcd using Euclid’s algorithm:

// C program to demonstrate Basic Euclidean Algorithm
#include <stdio.h>
// Function to return gcd of a and b
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}

// Driver code
int main()
{
int a = 10, b = 15;

// Function call
printf("GCD(%d, %d) = %d\n", a, b, gcd(a, b));
a = 35, b = 10;
printf("GCD(%d, %d) = %d\n", a, b, gcd(a, b));
a = 31, b = 2;
printf("GCD(%d, %d) = %d\n", a, b, gcd(a, b));
return 0;
}

Time Complexity: O(Log min(a, b))

Auxiliary Space: O(Log (min(a,b))
Searching-linear and binary search algorithms
Linear Search Algorithm
In this article, we will discuss the Linear Search Algorithm. 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.
Two popular search methods are Linear Search and Binary Search. So, here we will discuss the
popular searching technique, i.e., Linear Search Algorithm.
Linear search is also called as sequential search algorithm. It is the simplest searching algorithm.
In Linear search, 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 is found, then the location of the item is
returned; otherwise, the algorithm returns NULL.
It is widely used to search an element from the unordered list, i.e., the list in which items are not
sorted. The worst-case time complexity of linear search is O(n).
The steps used in the implementation of Linear Search are listed as follows -
o First, we have to traverse the array elements using a for loop.
o In each iteration of for loop, compare the search element with the current array element,
and -
o If the element matches, then return the index of the corresponding array element.
o If the element does not match, then move to the next element.
o If there is no match or the search element is not present in the given array, return -1.

Now, let's see the algorithm of linear search.

Algorithm
1. Linear_Search(a, n, val) // 'a' is the given array, 'n' is the size of given array, 'val' is the va
lue to search
2. Step 1: set pos = -1
3. Step 2: set i = 1
4. Step 3: repeat step 4 while i <= n
5. Step 4: if a[i] == val
6. set pos = i
7. print pos
 8. go to step 6
9. [end of if]
10. set i = i + 1
11. [end of loop]
12. Step 5: if pos = -1
13. print "value is not present in the array "
14. [end of if]
15. Step 6: exit

Working of Linear search

Now, let's see the working of the linear search Algorithm.
To understand the working of linear search algorithm, let's take an unsorted array. It will be easy
to understand the working of linear search with an example.
Let the elements of array are -

Let the element to be searched is K = 41

Now, start from the first element and compare K with each element of the array.

The value of K, i.e., 41, is not matched with the first element of the array. So, move to the next
element. And follow the same process until the respective element is found.
Now, the element to be searched is found. So algorithm will return the index of the element
matched.
Linear Search complexity
Now, let's see the time complexity of linear search in the best case, average case, and worst case.
We will also see the space complexity of linear search.
1. Time Complexity

Case Time Complexity

Best Case O(1)

 Average Case O(n)

Worst Case O(n)

o Best Case Complexity - In Linear search, best case occurs when the element we are
finding is at the first position of the array. The best-case time complexity of linear search
is O(1).
o Average Case Complexity - The average case time complexity of linear search is O(n).
o Worst Case Complexity - In Linear search, the worst case occurs when the element we
are looking is present at the end of the array. The worst-case in linear search could be when
the target element is not present in the given array, and we have to traverse the entire array.
The worst-case time complexity of linear search is O(n).
The time complexity of linear search is O(n) because every element in the array is compared only
once.
2. Space Complexity

Space Complexity O(1)

o The space complexity of linear search is O(1).

Implementation of Linear Search
Now, let's see the programs of linear search in different programming languages.
Program: Write a program to implement linear search in C language.
1. #include <stdio.h>
2. int linearSearch(int a[], int n, int val) {
3. // Going through array sequencially
4. for (int i = 0; i < n; i++)
5. {
6. if (a[i] == val)
7. return i+1;
8. }
9. return -1;
10. }
11. int main() {
 12. int a[] = {70, 40, 30, 11, 57, 41, 25, 14, 52}; // given array
13. int val = 41; // value to be searched
14. int n = sizeof(a) / sizeof(a[0]); // size of array
15. int res = linearSearch(a, n, val); // Store result
16. printf("The elements of the array are - ");
17. for (int i = 0; i < n; i++)
18. {
19. printf("%d ", a[i]);
20. }
21. printf("\nElement to be searched is - %d", val);
22. if (res == -1)
23. printf("\nElement is not present in the array");
24. else
25. printf("\nElement is present at %d position of array", res);
26. return 0;
27. }
Output

NOTE for the size of an array in number:

To calculate the size of an array in C, use the sizeof operator to get the total size of the array in
bytes, then divide that by the size of a single element within the array (using sizeof on a single
element from the array) to get the number of elements in the array; essentially, array_size =
sizeof(array) / sizeof(array[0]).

Binary search algorithm in C

In this article, we will discuss the Binary Search Algorithm. 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.
Linear Search and Binary Search are the two popular searching techniques. Here we will discuss
the Binary Search Algorithm.
Binary search is the search technique that works efficiently on sorted lists. Hence, to search an
element into some list using the binary search technique, we must ensure that the list is sorted.
Binary search follows the 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 the middle element is returned. Otherwise, we search into either of the halves depending upon
the result produced through the match.

Algorithm
1. Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound'
is the index of the first array element, 'upper_bound' is the index of the last array element,
'val' is the value to search
2. Step 1: set beg = lower_bound, end = upper_bound, pos = - 1
3. Step 2: repeat steps 3 and 4 while beg <=end
4. Step 3: set mid = (beg + end)/2
5. Step 4: if a[mid] = val
6. set pos = mid
7. print pos
8. go to step 6
9. else if a[mid] > val
10. set end = mid - 1
11. else
12. set beg = mid + 1
13. [end of if]
14. [end of loop]
15. Step 5: if pos = -1
16. print "value is not present in the array"
17. [end of if]
18. Step 6: exit
Working of Binary search
Now, let's see the working of the Binary Search Algorithm.
To understand the working of the Binary search algorithm, let's take a sorted array. It will be easy
to understand the working of Binary search with an example.
There are two methods to implement the binary search algorithm -
o Iterative method
o Recursive method
The recursive method of binary search follows the divide and conquer approach.
Let the elements of array are -

Let the element to search is, K = 56

We have to use the below formula to calculate the mid of the array -
1. mid = (beg + end)/2
So, in the given array -
beg = 0
end = 8
mid = (0 + 8)/2 = 4. So, 4 is the mid of the array.
Now, the element to search is found. So algorithm will return the index of the element matched.

Usage:
Databases, search engines, and data processing are just a few of the applications that use the binary
search strategy.
Characteristics:
o The array of input values must be sorted.
o With each iteration, the method shrinks the search range by half, making it particularly
efficient for huge datasets.
o The algorithm has an O (log n) worst-case time complexity.
o Finding the desired value is done by the programme using a divide-and-conquer strategy.

Implementation of Binary Search

Now, let's see the programs of Binary search in different programming languages.

Program: Write a program to implement Binary search in C language.

1. #include <stdio.h>
2. int binarySearch(int a[], int beg, int end, int val)
3. {
4. int mid;
5. if(end >= beg)
6. { mid = (beg + end)/2;
7. /* if the item to be searched is present at middle */
8. if(a[mid] == val)
9. {
10. return mid+1;
11. }
12. /* if the item to be searched is smaller than middle, then it can only be in left subarray */
13. else if(a[mid] < val)
14. {
15. return binarySearch(a, mid+1, end, val);
16. }
17. /* if the item to be searched is greater than middle, then it can only be in right subarray */
18. else
19. {
20. return binarySearch(a, beg, mid-1, val);
21. }
22. }
23. return -1;
24. }
25. int main() {
26. int a[] = {11, 14, 25, 30, 40, 41, 52, 57, 70}; // given array
27. int val = 40; // value to be searched
28. int n = sizeof(a) / sizeof(a[0])332333…; // size of array
29. int res = binarySearch(a, 0, n-1, val); // Store result
30. printf("The elements of the array are - ");
31. for (int i = 0; i < n; i++)
32. printf("%d ", a[i]);
33. printf("\nElement to be searched is - %d", val);
34. if (res == -1)
35. printf("\nEl0
36.
37.
38. ement is not present in the array");
39. else
40. printf("\nElement is present at %d position of array", res);
41. return 0;
42. }

Output

Binary Search complexity

Now, let's see the time complexity of Binary search in the best case, average case, and worst case.
We will also see the space complexity of Binary search.
1. Time Complexity

Case Time Complexity

Best Case O(1)

Average Case O(logn)

Worst Case O(logn)

o Best Case Complexity - In Binary search, best case occurs when the element to search is
found in first comparison, i.e., when the first middle element itself is the element to be
searched. The best-case time complexity of Binary search is O(1).
o Average Case Complexity - The average case time complexity of Binary search
is O(logn).
o Worst Case Complexity - In Binary search, the worst case occurs, when we have to keep
reducing the search space till it has only one element. The worst-case time complexity of
Binary search is O(logn).
2. Space Complexity
 Space Complexity O(1)

o The space complexity of binary search is O(1).

Advantages:
o For large datasets, the binary search algorithm is exceptionally efficient, and it is capable
of handling a wide range of input sizes.
o The algorithm is simple to implement in almost all programming languages.
Disadvantages:
o Before using the binary search technique, the input array must be sorted, which takes more
time and memory.
o The algorithm cannot be applied to unsorted arrays.
o The algorithm may yield inaccurate results if the input array is not sorted.
o The binary search algorithm is not appropriate for tiny datasets since the technique's
overhead may outweigh its benefits.
Conclusion:
A sorted array can be quickly searched for a specific element using the binary search technique. It
employs a divide-and-conquer strategy to cut the search range in half with each iteration, allowing
it to be highly efficient for large datasets. However, before using the binary search technique, the
input array must be sorted, which takes extra time and memory. The binary search algorithm is a
sophisticated data processing tool that is widely utilised in various sectors.

Sorting techniques, Insertion Sort, Selection Sort, Bubble Sort, Heap Sort
and Quick Sort
Sorting algorithms
C provides a rich set of data types and operators that can be used to implement various sorting
algorithms such as bubble sort, insertion sort and quick sort.
These algorithms are useful in many applications because they can be used to sort data of different
sizes and types.
There are different sorting algorithms.
They are:-
1. Bubble sort: An uncomplicated sorting algorithm that compares nearby components
repeatedly and switches them out if they are out of order.

Bubble sort is a simple and intuitive sorting algorithm. It repeatedly swaps adjacent
elements if they are in the wrong order until the array is sorted. In this algorithm, the largest
element "bubbles up" to the end of the array in each iteration. Bubble sort is inefficient for
large data sets, but it is useful for educational purposes and small data sets. In this section,
we will implement the bubble sort algorithm in C programming language.

The Algorithm for Bubble sort is:-

1. Start with an unsorted list of elements.

2. Compare the first two elements in the list. If the first element is larger than the second
element, swap them.
3. Move on to the next pair of elements and repeat step 2 until the end of the list is reached.
4. For each item on the list, repeat steps 2 and 3 once more. that is referred to as passes.
5. Repeat steps 2-4 for the entire list. As you repeat the passes, elements will "bubble up"
to their correct position in the sorted list.
6. Once a pass is completed and no swaps are made, the list is sorted, and the algorithm
can stop.
7. The final sorted list is returned.
The first step is to define the bubble sort function. This function takes an integer array and the size
of the array as its parameters. The function returns nothing as it modifies the original array.

Algorithm
In the algorithm given below, suppose arr is an array of n elements. The assumed swap function
in the algorithm will swap the values of given array elements.
1. begin BubbleSort(arr)
2. for all array elements
3. if arr[i] > arr[i+1]
4. swap(arr[i], arr[i+1])
5. end if
6. end for
7. return arr
8. end BubbleSort
Working of Bubble sort Algorithm
Now, let's see the working of Bubble sort Algorithm.
To understand the working of bubble sort algorithm, let's take an unsorted array. We are taking a
short and accurate array, as we know the complexity of bubble sort is O(n2).
Let the elements of array are -

First Pass
Sorting will start from the initial two elements. Let compare them to check which is greater.

Here, 32 is greater than 13 (32 > 13), so it is already sorted. Now, compare 32 with 26.

Here, 26 is smaller than 36. So, swapping is required. After swapping new array will look like -

Now, compare 32 and 35.

Here, 35 is greater than 32. So, there is no swapping required as they are already sorted.
Now, the comparison will be in between 35 and 10.

Here, 10 is smaller than 35 that are not sorted. So, swapping is required. Now, we reach at the end
of the array. After first pass, the array will be -
Now, move to the second iteration.
Second Pass
The same process will be followed for second iteration.

Here, 10 is smaller than 32. So, swapping is required. After swapping, the array will be -

Now, move to the third iteration.

Third Pass
The same process will be followed for third iteration.

Here, 10 is smaller than 26. So, swapping is required. After swapping, the array will be -

Now, move to the fourth iteration.

Fourth pass
Similarly, after the fourth iteration, the array will be -

Hence, there is no swapping required, so the array is completely sorted.

Now, the first step is to define the bubble sort function. This function takes an integer array and
the size of the array as its parameters. The function returns nothing as it modifies the original array.
Here is the function definition:
1. void bubble_sort(int arr[], int n) {
2. int i, j;
3. for (i = 0; i < n - 1; i++) {
4. for (j = 0; j < n - i - 1; j++) {
5. if (arr[j] > arr[j + 1]) {
6. int temp = arr[j];
7. arr[j] = arr[j + 1];
8. arr[j + 1] = temp;
9. }
10. }
11. }
12. }
The function has two loops. The outer loop runs from the first element to the second-last element
of the array. The inner loop runs from the first element to the second-last element of the unsorted
part of the array. The condition of the inner loop is n - i - 1 because the last i elements of the array
are already sorted.
In each iteration of the inner loop, we compare adjacent elements. If the left element is greater than
the right element, we swap them. After the inner loop completes, the largest element is guaranteed
to be at the end of the unsorted part of the array.

Bubble sort complexity

Now, let's see the time complexity of bubble sort in the best case, average case, and worst case.
We will also see the space complexity of bubble sort.
1. Time Complexity

Case Time Complexity

Best Case O(n)

Average Case O(n2)

Worst Case O(n2)

o Best Case Complexity - It occurs when there is no sorting required, i.e. the array is already
sorted. The best-case time complexity of bubble sort is O(n).
o Average Case Complexity - It occurs when the array elements are in jumbled order that
is not properly ascending and not properly descending. The average case time complexity
of bubble sort is O(n2).
o Worst Case Complexity - It occurs when the array elements are required to be sorted in
reverse order. That means suppose you have to sort the array elements in ascending order,
but its elements are in descending order. The worst-case time complexity of bubble sort
is O(n2).

Space Complexity

Space Complexity O(1)

Stable YES

o The space complexity of bubble sort is O(1). It is because, in bubble sort, an extra variable
is required for swapping.
o The space complexity of optimized bubble sort is O(2). It is because two extra variables
are required in optimized bubble sort.

Implementation of Bubble sort

Now, let's see the programs of Bubble sort in different programming languages.

Program: Write a program to implement bubble sort in C language.

1. #include<stdio.h>
2. void print(int arr[], int n) //function to print array elements
3. {
4. int i;
5. for(i = 0; i < n; i++)
6. {
7. printf("%d ",arr[i]);
8. }
9. }

10. void bubble_sort(int arr[], int n) // function to implement bubble sort

11. {
12. int i, j;
13. for (i = 0; i < n - 1; i++) {
14. for (j = 0; j < n - i - 1; j++) {
15. if (arr[j] > arr[j + 1]) {
16. int temp = arr[j];
17. arr[j] = arr[j + 1];
18. arr[j + 1] = temp;
19. }
20. }
21. }
22. }
23. void main() {
24. int arr[] = {64, 34, 25, 12, 22, 11, 90};
25. int n = sizeof(arr) / sizeof(arr[0]);
26. printf("unsorted array: ");
27. print(arr, n);
28. bubble_sort(arr, n);
29. printf("Sorted array: ");
30. print(arr, n);
31. }

Output
The main function creates an integer array arr of size 7 and initializes it with random numbers. We
then calculate the size of the array by dividing the size of the array by the size of an integer element.
Next, we call the bubble_sort function to sort the array. Finally, we print the sorted array using a
for loop.
When we run the program, we should see the following output:
Sorted array: 11 12 22 25 34 64 90
This output shows that our bubble sort implementation correctly sorted the array in ascending
order.
Characteristics:
 Bubble sort is a simple sorting algorithm.
 It works by repeatedly swapping adjacent elements if they are in the wrong order.
 The algorithm sorts the array in ascending or descending order.
 It has a time complexity of O(n2) in the worst case, where n is the size of the array.
Usage:
 Bubble sort is useful for educational purposes and small data sets.
 It is not suitable for large data sets because of its time complexity.
Advantages:
 Bubble sort is easy to understand and implement.
 It requires minimal additional memory space to perform the sorting.
Disadvantages:
 It is not efficient for large data sets because of its time complexity.
 It has poor performance compared to other sorting algorithms, such as quicksort and
mergesort.
Conclusion:
Bubble sort is a simple and intuitive sorting algorithm that is useful for educational
purposes and small data sets. However, its time complexity makes it inefficient for large
data sets. Therefore, it is not commonly used in real-world applications. Other sorting
algorithms, such as quick sort and merge sort, are more efficient for large data sets.

2. Insertion sort: a method of sorting that creates a sorted list one individual element at a
time by placing each one in the appropriate spot.
Insertion sort is a simple sorting algorithm that iteratively constructs a sorted section of an array
one element at a time. It is an in-place comparison-based method with an average time complexity
of O(n2).
The array is divided into two halves by the method: sorted and unsorted. The first element of the
array is first considered the sorted component, whereas the remaining items are originally
considered the unsorted component.
The algorithm subsequently compares each unsorted element to the elements in the sorted segment,
beginning at the end, and adjusts the bigger elements one position to the right until the unsorted
element is found in the correct location.

After determining the proper location, the unsorted element is placed into the sorted component at
that location.
This procedure is repeated until all of the members of the unsorted part have been inserted into the
sorted part, resulting in a fully sorted array.
The Algorithm for Insertion sort is:-

The simple steps of achieving the insertion sort are listed as follows -

Step 1 - If the element is the first element, assume that it is already sorted. Return 1.

Step2 - Pick the next element, and store it separately in a key.

Step3 - Now, compare the key with all elements in the sorted array.

Step 4 - If the element in the sorted array is smaller than the current element, then move to the next
element. Else, shift greater elements in the array towards the right.

Step 5 - Insert the value.

Step 6 - Repeat until the array is sorted.

Here is the insertion sort pseudocode:

1. for i from 1 to n-1

2. key = arr[i]
3. j=i-1
4. while j >= 0 and arr[j] > key
5. arr[j+1] = arr[j]
6. j=j-1
7. arr[j+1] = key
Working of Insertion sort Algorithm
Now, let's see the working of the insertion sort Algorithm.

To understand the working of the insertion sort algorithm, let's take an unsorted array. It will be
easier to understand the insertion sort via an example.

Let the elements of array are -

Initially, the first two elements are compared in insertion sort.

Here, 31 is greater than 12. That means both elements are already in ascending order. So, for now,
12 is stored in a sorted sub-array.

Now, move to the next two elements and compare them.

Here, 25 is smaller than 31. So, 31 is not at correct position. Now, swap 31 with 25. Along with
swapping, insertion sort will also check it with all elements in the sorted array.

For now, the sorted array has only one element, i.e. 12. So, 25 is greater than 12. Hence, the sorted
array remains sorted after swapping.

Now, two elements in the sorted array are 12 and 25. Move forward to the next elements that are
31 and 8.
Both 31 and 8 are not sorted. So, swap them.

ADVERTISEMENT

ADVERTISEMENT

After swapping, elements 25 and 8 are unsorted.

So, swap them.

Now, elements 12 and 8 are unsorted.

So, swap them too.

Now, the sorted array has three items that are 8, 12 and 25. Move to the next items that are 31 and
32.

Hence, they are already sorted. Now, the sorted array includes 8, 12, 25 and 31.
 ADVERTISEMENT

Move to the next elements that are 32 and 17.

17 is smaller than 32. So, swap them.

Swapping makes 31 and 17 unsorted. So, swap them too.

Now, swapping makes 25 and 17 unsorted. So, perform swapping again.

Now, the array is completely sorted.

Insertion sort complexity

Now, let's see the time complexity of insertion sort in best case, average case, and in worst case.
We will also see the space complexity of insertion sort.
1. Time Complexity

Case Time Complexity

Best Case O(n)

Average Case O(n2)

Worst Case O(n2)

o Best Case Complexity - It occurs when there is no sorting required, i.e. the array is already
sorted. The best-case time complexity of insertion sort is O(n).
o Average Case Complexity - It occurs when the array elements are in jumbled order that
is not properly ascending and not properly descending. The average case time complexity
of insertion sort is O(n2).
o Worst Case Complexity - It occurs when the array elements are required to be sorted in
reverse order. That means suppose you have to sort the array elements in ascending order,
but its elements are in descending order. The worst-case time complexity of insertion sort
is O(n2).
2. Space Complexity

Space Complexity O(1)

Stable YES

Implementation of insertion sort

Program: Write a program to implement insertion sort in C language.

1. #include <stdio.h>
2.
3. void insert(int a[], int n) /* function to sort an aay with insertion sort */
4. {
5. int i, j, temp;
6. for (i = 1; i < n; i++) {
7. temp = a[i];
8. j = i - 1;
9.
10. while(j>=0 && temp <= a[j]) /* Move the elements greater than temp to one position ahead fro
m their current position*/
11. {
12. a[j+1] = a[j];
13. j = j-1;
14. }
15. a[j+1] = temp;
16. }
17. }
18.
19. void printArr(int a[], int n) /* function to print the array */
20. {
21. int i;
22. for (i = 0; i < n; i++)
23. printf("%d ", a[i]);
24. }
25.
26. int main()
27. {
28. int a[] = { 12, 31, 25, 8, 32, 17 };
29. int n = sizeof(a) / sizeof(a[0]);
30. printf("Before sorting array elements are - \n");
31. printArr(a, n);
32. insert(a, n);
33. printf("\nAfter sorting array elements are - \n");
34. printArr(a, n);
35.
36. return 0;
37. }

Output:

Usage:
Insertion sort is useful for sorting small arrays and has decent speed when the input array is already
partially sorted. It is frequently used as a building piece in more advanced sorting algorithms such
as merge sort and quicksort.
Advantages:
 Easy implementation: Because the approach is simple to build and understand, it is a great
option for teaching basic sorting concepts.
 Because it sorts the array in place, insertion sort does not require any additional memory
space.
 Insertion sort is an adaptive sorting algorithm that works best with partially sorted input
arrays.
 Stable sorting means that the method keeps equal elements in the input array in the same
relative order.

Disadvantages:
o Slow for large arrays: With an average time complexity of O(n2), the algorithm is slow for
large arrays.
o Insertion sort is inefficient for random input arrays because it involves a large number of
comparisons and shifts.
o The algorithm is not suited for parallelization since each iteration is dependent on the
outcome of the preceding iteration.
Conclusion:
Insertion sort provides a straightforward and efficient approach for tiny or partially sorted arrays.
It is not ideal for huge arrays or random input, but it can be used to construct more complex sorting
algorithms. Overall, insertion sort is a solid solution for efficiently sorting small or partially sorted
arrays with little memory utilization.

Selection Sort Algorithm

In this article, we will discuss the Selection sort Algorithm. The working procedure of selection
sort is also simple. This article will be very helpful and interesting to students as they might face
selection sort as a question in their examinations. So, it is important to discuss the topic.
In selection sort, the smallest value among the unsorted elements of the array is selected in every
pass and inserted to its appropriate position into the array. It is also the simplest algorithm. It is an
in-place comparison sorting algorithm. In this algorithm, the array is divided into two parts, first
is sorted part, and another one is the unsorted part. Initially, the sorted part of the array is empty,
and unsorted part is the given array. Sorted part is placed at the left, while the unsorted part is
placed at the right.
In selection sort, the first smallest element is selected from the unsorted array and placed at the
first position. After that second smallest element is selected and placed in the second position. The
process continues until the array is entirely sorted.
The average and worst-case complexity of selection sort is O(n2), where n is the number of items.
Due to this, it is not suitable for large data sets.
Selection sort is generally used when -
o A small array is to be sorted
o Swapping cost doesn't matter
o It is compulsory to check all elements
Now, let's see the algorithm of selection sort.

Algorithm

SELECTION SORT(arr, n)
Step 1: Repeat Steps 2 and 3 for i = 0 to n-1
Step 2: CALL SMALLEST(arr, i, n, pos)
Step 3: SWAP arr[i] with arr[pos]
[END OF LOOP]
Step 4: EXIT

SMALLEST (arr, i, n, pos)

Step 1: [INITIALIZE] SET SMALL = arr[i]
Step 2: [INITIALIZE] SET pos = i
Step 3: Repeat for j = i+1 to n
if (SMALL > arr[j])
SET SMALL = arr[j]
SET pos = j
[END OF if]
[END OF LOOP]
Step 4: RETURN pos
Working of Selection sort Algorithm
Now, let's see the working of the Selection sort Algorithm.
To understand the working of the Selection sort algorithm, let's take an unsorted array. It will be
easier to understand the Selection sort via an example.
Let the elements of array are -

Now, for the first position in the sorted array, the entire array is to be scanned sequentially.
At present, 12 is stored at the first position, after searching the entire array, it is found that 8 is the
smallest value.

So, swap 12 with 8. After the first iteration, 8 will appear at the first position in the sorted array.

For the second position, where 29 is stored presently, we again sequentially scan the rest of the
items of unsorted array. After scanning, we find that 12 is the second lowest element in the array
that should be appeared at second position.

Now, swap 29 with 12. After the second iteration, 12 will appear at the second position in the
sorted array. So, after two iterations, the two smallest values are placed at the beginning in a sorted
way.

The same process is applied to the rest of the array elements. Now, we are showing a pictorial
representation of the entire sorting process.
Now, the array is completely sorted.

Selection sort complexity

Now, let's see the time complexity of selection sort in best case, average case, and in worst case.
We will also see the space complexity of the selection sort.

1. Time Complexity
Case Time Complexity

Best Case O(n2)

Average Case O(n2)

Worst Case O(n2)

o Best Case Complexity - It occurs when there is no sorting required, i.e. the array is already sorted.
The best-case time complexity of selection sort is O(n2).
 o Average Case Complexity - It occurs when the array elements are in jumbled order that is not
properly ascending and not properly descending. The average case time complexity of selection
sort is O(n2).
o Worst Case Complexity - It occurs when the array elements are required to be sorted in reverse
order. That means suppose you have to sort the array elements in ascending order, but its elements
are in descending order. The worst-case time complexity of selection sort is O(n2).

2. Space Complexity
Space Complexity O(1)

Stable YES

o The space complexity of selection sort is O(1). It is because, in selection sort, an extra variable is
required for swapping.

Implementation of selection sort

Program: Write a program to implement selection sort in C language.
1. #include <stdio.h>
2.
3. void selection(int arr[], int n)
4. {
5. int i, j, small;
6.
7. for (i = 0; i < n-1; i++) // One by one move boundary of unsorted subarray
8. {
9. small = i; //minimum element in unsorted array
10.
11. for (j = i+1; j < n; j++)
12. if (arr[j] < arr[small])
13. small = j;
14. // Swap the minimum element with the first element
 15. int temp = arr[small];
16. arr[small] = arr[i];
17. arr[i] = temp;
18. }
19. }
20.
21. void printArr(int a[], int n) /* function to print the array */
22. {
23. int i;
24. for (i = 0; i < n; i++)
25. printf("%d ", a[i]);
26. }
27.
28. int main()
29. {
30. int a[] = { 12, 31, 25, 8, 32, 17 };
31. int n = sizeof(a) / sizeof(a[0]);
32. printf("Before sorting array elements are - \n");
33. printArr(a, n);
34. selection(a, n);
35. printf("\nAfter sorting array elements are - \n");
36. printArr(a, n);
37. return 0;
38. }
Output:
After the execution of above code, the output will be -
 Heap Sort Algorithm
In this article, we will discuss the Heapsort Algorithm. Heap sort processes the elements by
creating the min-heap or max-heap using the elements of the given array. Min-heap or max-heap
represents the ordering of array in which the root element represents the minimum or maximum
element of the array.
Heap sort basically recursively performs two main operations -
o Build a heap H, using the elements of array.
o Repeatedly delete the root element of the heap formed in 1st phase.
Before knowing more about the heap sort, let's first see a brief description of Heap.
What is a heap?
A heap is a complete binary tree, and the binary tree is a tree in which the node can have the utmost
two children. A complete binary tree is a binary tree in which all the levels except the last level,
i.e., leaf node, should be completely filled, and all the nodes should be left-justified.
What is heap sort?
Heapsort is a popular and efficient sorting algorithm. The concept of heap sort is to eliminate the
elements one by one from the heap part of the list, and then insert them into the sorted part of the
list.

Working of Heap sort Algorithm

Now, let's see the working of the Heapsort Algorithm.
In heap sort, basically, there are two phases involved in the sorting of elements. By using the heap
sort algorithm, they are as follows -
o The first step includes the creation of a heap by adjusting the elements of the array.
o After the creation of heap, now remove the root element of the heap repeatedly by shifting
it to the end of the array, and then store the heap structure with the remaining elements.
Now let's see the working of heap sort in detail by using an example. To understand it more clearly,
let's take an unsorted array and try to sort it using heap sort. It will make the explanation clearer
and easier.
First, we have to construct a heap from the given array and convert it into max heap.

After converting the given heap into max heap, the array elements are -

Next, we have to delete the root element (89) from the max heap. To delete this node, we have to
swap it with the last node, i.e. (11). After deleting the root element, we again have to heapify it to
convert it into max heap.

After swapping the array element 89 with 11, and converting the heap into max-heap, the elements
of array are -
In the next step, again, we have to delete the root element (81) from the max heap. To delete this
node, we have to swap it with the last node, i.e. (54). After deleting the root element, we again
have to heapify it to convert it into max heap.

After swapping the array element 81 with 54 and converting the heap into max-heap, the elements
of array are -

In the next step, we have to delete the root element (76) from the max heap again. To delete this
node, we have to swap it with the last node, i.e. (9). After deleting the root element, we again have
to heapify it to convert it into max heap.

After swapping the array element 76 with 9 and converting the heap into max-heap, the elements
of array are -
In the next step, again we have to delete the root element (54) from the max heap. To delete this
node, we have to swap it with the last node, i.e. (14). After deleting the root element, we again
have to heapify it to convert it into max heap.

After swapping the array element 54 with 14 and converting the heap into max-heap, the elements
of array are -

In the next step, again we have to delete the root element (22) from the max heap. To delete this
node, we have to swap it with the last node, i.e. (11). After deleting the root element, we again
have to heapify it to convert it into max heap.

After swapping the array element 22 with 11 and converting the heap into max-heap, the elements
of array are -
In the next step, again we have to delete the root element (14) from the max heap. To delete this
node, we have to swap it with the last node, i.e. (9). After deleting the root element, we again have
to heapify it to convert it into max heap.

After swapping the array element 14 with 9 and converting the heap into max-heap, the elements
of array are -

In the next step, again we have to delete the root element (11) from the max heap. To delete this
node, we have to swap it with the last node, i.e. (9). After deleting the root element, we again have
to heapify it to convert it into max heap.

After swapping the array element 11 with 9, the elements of array are -

Now, heap has only one element left. After deleting it, heap will be empty.
After completion of sorting, the array elements are -

Now, the array is completely sorted.

Heap sort complexity

Now, let's see the time complexity of Heap sort in the best case, average case, and worst case. We
will also see the space complexity of Heapsort.
1. Time Complexity

Case Time Complexity

Best Case O(n logn)

Average Case O(n log n)

Worst Case O(n log n)

o Best Case Complexity - It occurs when there is no sorting required, i.e. the array is already
sorted. The best-case time complexity of heap sort is O(n logn).
o Average Case Complexity - It occurs when the array elements are in jumbled order that
is not properly ascending and not properly descending. The average case time complexity
of heap sort is O(n log n).
o Worst Case Complexity - It occurs when the array elements are required to be sorted in
reverse order. That means suppose you have to sort the array elements in ascending order,
but its elements are in descending order. The worst-case time complexity of heap sort
is O(n log n).
The time complexity of heap sort is O(n logn) in all three cases (best case, average case, and worst
case). The height of a complete binary tree having n elements is logn.
2. Space Complexity
 Space Complexity O(1)

Stable N0

o The space complexity of Heap sort is O(1).

Program: Write a program to implement heap sort in C language.

1. #include <stdio.h>
2. /* function to heapify a subtree. Here 'i' is the
3. index of root node in array a[], and 'n' is the size of heap. */
4. void heapify(int a[], int n, int i)
5. {
6. int largest = i; // Initialize largest as root
7. int left = 2 * i + 1; // left child
8. int right = 2 * i + 2; // right child
9. // If left child is larger than root
10. if (left < n && a[left] > a[largest])
11. largest = left;
12. // If right child is larger than root
13. if (right < n && a[right] > a[largest])
14. largest = right;
15. // If root is not largest
16. if (largest != i) {
17. // swap a[i] with a[largest]
18. int temp = a[i];
19. a[i] = a[largest];
20. a[largest] = temp;
21.
22. heapify(a, n, largest);
23. }
24. }
25. /*Function to implement the heap sort*/
26. void heapSort(int a[], int n)
27. {
28. for (int i = n / 2 - 1; i >= 0; i--)
29. heapify(a, n, i);
30. // One by one extract an element from heap
31. for (int i = n - 1; i >= 0; i--) {
32. /* Move current root element to end*/
33. // swap a[0] with a[i]
34. int temp = a[0];
35. a[0] = a[i];
36. a[i] = temp;
37.
38. heapify(a, i, 0);
39. }
40. }
41. /* function to print the array elements */
42. void printArr(int arr[], int n)
43. {
44. for (int i = 0; i < n; ++i)
45. {
46. printf("%d", arr[i]);
47. printf(" ");
48. }
49.
 50. }
51. int main()
52. {
53. int a[] = {48, 10, 23, 43, 28, 26, 1};
54. int n = sizeof(a) / sizeof(a[0]);
55. printf("Before sorting array elements are - \n");
56. printArr(a, n);
57. heapSort(a, n);
58. printf("\nAfter sorting array elements are - \n");
59. printArr(a, n);
60. return 0;
61. }
Output

Advantages of Heap Sort:

Efficient Time Complexity: Heap Sort has a time complexity of O(n log n) in all cases. This
makes it efficient for sorting large datasets. The log n factor comes from the height of the binary
heap, and it ensures that the algorithm maintains good performance even with a large number of
elements.
Memory Usage: Memory usage can be minimal because apart from what is necessary to hold the
initial list of items to be sorted, it needs no additional memory space to work
Simplicity: It is simpler to understand than other equally efficient sorting algorithms because it
does not use advanced computer science concepts.

Disadvantages of Heap Sort:

Costly: Heap sort is costly.
Unstable: Heap sort is unstable. It might rearrange the relative order.
Efficient: Heap Sort is not very efficient when working with highly complex data.
C program to compare the two strings
Strings can be compared either by using the string function or without using string function. First,
we will look at how we can compare the strings with the help of string function,
i.e., strcmp(), which is defined in a string.h header file.
String comparison by using string function
The string function which is pre-defined in a string.h header file is a strcmp() function. The
strcmp() function consider two strings as a parameter, and this function returns an integer value
where the integer value can be zero, positive or negative.
The syntax of the strcmp() function is given below:
1. int strcmp (const char* str1, const char* str2);
In the above syntax, two parameters are passed as strings, i.e., str1 and str2, and the return type
is int means that the strcmp() returns an integer value.
The strcmp() function compares the character of both the strings. If the first character of both the
strings are same, then this process of comparison will continue until all the characters are compared
or the pointer points to the null character '\0'.
Possible return values from the strcmp() function

Return Description
value

0 When both the strings are equal.

<0 If the ASCII value of a character of the first string is less than the ASCII
value of a character of the second string, then the function will return
negative value.

>0 If the ASCII value of a character of the first string is greater than the
ASCII value of a character of the second string, then the function will
return positive value.

Let's understand through an example.

1. #include <stdio.h>
2. #include<string.h>
3. int main()
 4. {
5. char str1[20]; // declaration of char array
6. char str2[20]; // declaration of char array
7. int value; // declaration of integer variable
8. printf("Enter the first string : ");
9. scanf("%s",str1);
10. printf("Enter the second string : ");
11. scanf("%s",str2);
12. // comparing both the strings using strcmp() function
13. value=strcmp(str1,str2);
14. if(value==0)
15. printf("strings are same");
16. else
17. printf("strings are not same");
18. return 0;
19. }
Analysis of the above program
o We have declared two arrays of char type, i.e., str1 and str2. We take the user input as
strings.
o We compare the strings by using the strcmp() function, i.e., strcmp(str1,str2). This
function will compare both the strings str1 and str2. If the function returns 0 value means
that both the strings are same, otherwise the strings are not equal.
Output:
String comparison without using strcmp() function
1. #include <stdio.h>
2. int compare(char[],char[]);
3. int main()
4. {
5. char str1[20]; // declaration of char array
6. char str2[20]; // declaration of char array
7. printf("Enter the first string : ");
8. scanf("%s",str1);
9. printf("Enter the second string : ");
10. scanf("%s",str2);
11. int c= compare(str1,str2); // calling compare() function
12. if(c==0)
13. printf("strings are same");
14. else
15. printf("strings are not same");
 16.
17. return 0;
18. }
19.
20. // Comparing both the strings.
21. int compare(char a[],char b[])
22. {
23. int flag=0,i=0; // integer variables declaration
24. while(a[i]!='\0' &&b[i]!='\0') // while loop
25. {
26. if(a[i]!=b[i])
27. {
28. flag=1;
29. break;
30. }
31. i++;
32. }
33. if(flag==0)
34. return 0;
35. else
36. return 1;
37. }
Analysis of the above program
o In the above, we have declared two arrays of char type, and we take the user input as strings.
o We have defined a compare() function which will take user input strings as a parameter,
and compare both the strings. If the function returns 0, which means that both the strings
are equal otherwise both the strings are not equal.
Output:
1. #include <stdio.h>
2. int stringcompare(char*,char*);
3. int main()
4. {
5. char str1[20]; // declaration of char array
6. char str2[20]; // declaration of char array
7. printf("Enter the first string : ");
8. scanf("%s",str1);
9. printf("\nEnter the second string : ");
10. scanf("%s",str2);
11. int compare=stringcompare(str1,str2); // calling stringcompare() function.
12. if(compare==0)
13. printf("strings are equal");
14. else
15. printf("strings are not equal");
16. return 0;
17. }
18. // Comparing both the strings using pointers
19. int stringcompare(char *a,char *b)
20. {
 21. int flag=0;
22. while(*a!='\0' && *b!='\0') // while loop
23. {
24. if(*a!=*b)
25. {
26. flag=1;
27. }
28. a++;
29. b++;
30. }
31.
32. if(flag==0)
33. return 0;
34. else
35. return 1;
36. }

Analysis of the above program

o We have created two arrays of char type str1 and str2. We take the user input as strings.
o We have defined a stringcompare() function which will take two pointers of char type as a
parameter. The 'a' pointer holds the address of str1 and 'b' pointer holds the address of str2. Inside
the function, we have created a while loop which will execute until the pointer a or b is not reached
to a null character.

Output:
Strings Concatenation in C
The concatenation of strings is a process of combining two strings to form a single string. If there
are two strings, then the second string is added at the end of the first string.
For example, Hello + javaTpoint = Hello javaTpoint
We can concatenate the strings in the following two ways:
o Concatenate two strings using loop
o Concatenate two strings using pointer
o Concatenate two strings using strcat() function
Concatenate two strings using loop
1. #include <stdio.h>
2. int main()
3. {
4. char first_string[20]; // declaration of char array variable
5. char second_string[20]; // declaration of char array variable
6. int i; // integer variable declaration
7. printf("Enter the first string");
8. scanf("%s",first_string);
9. printf("\nEnter the second string");
10. scanf("%s",second_string);
11. for(i=0;first_string[i]!='\0';i++);
 12.
13.
14. for(int j=0;second_string[j]!='\0';j++)
15. {
16.
17. first_string[i]=second_string[j];
18. i++;
19. }
20. first_string[i]='\0';
21. printf("After concatenation, the string would look like: %s", first_string);
22. return 0;
Analysis of the above program
o In the above program, we declare two strings, i.e., first_string and second_string. The
values of these two strings are taken by the user as an input.
o We will concatenate these two strings and store the result of concatenation in
the first_string
o We declare a new integer variable named 'i'. After declaration, we will run a loop that
iterates from i=0 till the null character of the first_string is encountered. When the
execution of the loop is completed, then the value of 'i' becomes equal to the length of the
string plus one.
o We will define another new loop, which is basically used to concatenate the two strings.
This loop starts from j=0 and executes until the null character of the second_string is
encountered. On each iteration, the character located at the jth position in
the second_string gets stored in the ith position of the first_string. In this way, both the
strings are combined together to form a single string.
Output
 Concatenate two strings using pointer

1. #include <stdio.h>
2. int main()
3. {
4. char string1[20]; // char array declaration
5. char string2[20]; // char array declaration
6. int i=0,j=0; // declaration of integer variables
7. char *str1; // declaration of char pointer
8. char *str2; // declaration of char pointer
9. str1=string1;
10. str2=string2;
11. printf("Enter the first string");
12. scanf("%s",string1);
13. printf("\nEnter the second string");
14. scanf("%s", string2);
15. while(string1[i]!='\0')
16. {
17.
18. ++str1;
19. i++;
20. }
21. while(string2[j]!='\0')
22. {
23. *str1=*str2;
24. str1++;
25. str2++;
26. j++;
27. }
28. printf("The concatenated string is %s",string1);
29.
30. return 0;
31. }

Analysis of the above program

o In the above program, we have declared character array variables, i.e., string1 and string2.
We take the two strings as user input and store them in the variables string1 and string2,
o We declare two char pointers str1 and str2. The str1 contains the address of string1, and
str2 contains the address of string2.
o We create a loop which iterates until the null character of string1 is encountered. When the
execution of the loop is completed, then the pointer str1 points to the location that exists
just after the location of the last character.
o We define another while loop that iterates till the null character of string2 is encountered.
On each iteration, the character stored at the jth location in the string2 is appended to the
string1 by using the statement *str1=*str2.

Output
Concatenation of two strings using strcat()
Now we will see how to concatenate two strings using strcat() function. The strcat() is an inbuilt
function defined in a string.h header file.
Let's look at the example.
1. #include <stdio.h>
2. #include<string.h>
3. int main()
4. {
5. char s1[20]; // declaration of char array
6. char s2[20]; // declaration of char array
7. printf("Enter the first string : ");
8. scanf("%s", s1);
9. printf("\nEnter the second string :");
10. scanf("%s",s2);
11. strcat(s1,s2);
12. printf("The concatenated string is : %s",s1);
13. return 0;
14. }
In the above code, we use the strcat() function to concatenate two strings. It takes two strings as a
parameter and then appends the second string at the end of the first string.
Output