Programming Logic Concepts

UNIT I Introduction Problem Solving Aspects

 Introduction to Problem Solving Aspects :

Problem solving is the process of identifying a challenge and finding an effective way to
address it. In the context of programming logic, problem solving is essential for developing correct,
efficient, and logical computer programs. It involves understanding the problem, designing a
solution, and implementing it using programming constructs.

Key Aspects of Problem Solving in Programming:

1. Problem Definition
o Clearly understand the problem statement.
o Identify inputs, expected outputs, constraints, and requirements.
o Ask: What needs to be solved?
2. Analysis
o Break the problem into smaller components.
o Determine the relationships between data.
o Understand the logic behind the problem.
o Ask: What information is given? What do we need to find?
3. Algorithm Development
o Design a step-by-step procedure (algorithm) to solve the problem.
o Use tools like:
 Pseudocode
 Flowcharts
o Focus on the logic and sequence of operations.
4. Coding / Implementation
o Convert the algorithm into a programming language (like C, Java, or Python).
o Use proper syntax and follow logical programming structure (sequence, selection,
iteration).
5. Testing and Debugging
o Run the program with different test cases.
o Identify and fix errors (syntax, logical, runtime).
o Ensure the program works as intended.
6. Documentation and Maintenance
o Write comments and maintain clean code for understanding and future updates.
o Update the program when requirements change.

Why Problem Solving is Important in Programming

 Helps in writing efficient, reusable, and optimized code.

 Encourages logical thinking and systematic design.
 Builds a foundation for learning data structures, algorithms, and software development.
 Implementation of algorithms:
An algorithm is a process or set of rules which must be followed to complete a particular task. This is
basically the step-by-step procedure to complete any task. All the tasks are followed a particular algorithm,
from making a cup of tea to make high scalable software. This is the way to divide a task into several parts. If
we draw an algorithm to complete a task then the task will be easier to complete.

The algorithm is used for,

 To develop a framework for instructing computers.
 Introduced notation of basic functions to perform basic tasks.
 For defining and describing a big problem in small parts, so that it is very easy to execute.

Characteristics of Algorithm
An algorithm should be defined clearly.
An algorithm should produce at least one output.
An algorithm should have zero or more inputs.
An algorithm should be executed and finished in finite number of steps.
An algorithm should be basic and easy to perform.
Each step started with a specific indentation like, "Step-1",
There must be "Start" as the first step and "End" as the last step of the algorithm.

Let's take an example to make a cup of tea,

Step 1: Start
Step 2: Take some water in a bowl.
Step 3: Put the water on a gas burner.
Step 4: Turn on the gas burner
Step 5: Wait for some time until the water is boiled.
Step 6: Add some tea leaves to the water according to the requirement.
Step 7: Then again wait for some time until the water is getting colorful as tea.
Step 8: Then add some sugar according to taste.
Step 9: Again wait for some time until the sugar is melted.
Step 10: Turn off the gas burner and serve the tea in cups with biscuits.
Step 11: End

There are some basics steps to make an algorithm:

Start - Start the algorithm
Input - Take the input for values in which the algorithm will execute.
Conditions - Perform some conditions on the inputs to get the desired output.
Output - Printing the outputs.
End - End the execution.

Example 1. Swap two numbers with a third variable

Step 1: Start
Step 2: Take 2 numbers as input.
Step 3: Declare another variable as "temp".
Step 4: Store the first variable to "temp".
Step 5: Store the second variable to the First variable.
Step 6: Store the "temp" variable to the 2nd variable.
Step 7: Print the First and second variables.
Step 8: End

Example 2. Find the area of a rectangle

Step 1: Start
Step 2: Take the Height and Width of the rectangle as input.
Step 3: Declare a variable as "area"
Step 4: Multiply Height and Width
Step 5: Store the multiplication to "Area", (its look like area = Height x Width)
Step 6: Print "area";
Step 7: End

Example 3. Find the greatest between 3 numbers.

Step 1: Start
Step 2: Take 3 numbers as input, say A, B, and C.
Step 3: Check if(A>B and A>C)
Step 4: Then A is greater
Step 5: Print A
Step 6: Else
Step 7: Check if(B>A and B>C)
Step 8: Then B is greater
Step 9: Print B
Step 10: Else C is greater
Step 11: Print C
Step 12: End

Advantages of Algorithm
1. An algorithm uses a definite procedure.
2. It is easy to understand because it is a step-by-step definition.
3. The algorithm is easy to debug if there is any error happens.
4. It is not dependent on any programming language
5. It is easier for a programmer to convert it into an actual program because the algorithm divides a
problem into smaller parts.

Disadvantages of Algorithms
1. An algorithm is Time-consuming, there is specific time complexity for different algorithms.
2. Large tasks are difficult to solve in Algorithms because the time complexity may be higher, so
programmers have to find a good efficient way to solve that task.
3. Looping and branching are difficult to define in algorithms.

 Top-down design Introduction to Algorithms

An algorithm is a step-by-step procedure or set of instructions designed to perform a specific

task or solve a particular problem.

✨ Characteristics of a Good Algorithm:

Input: Clearly defined input(s)
Output: Clearly defined output(s)
Definiteness: Each step is clear and unambiguous
Finiteness: The algorithm must terminate after a finite number of steps
Effectiveness: Each operation must be basic enough to be performed exactly
📌 Examples of Simple Algorithms:
 Finding the largest of three numbers
 Calculating the factorial of a number
 Searching an element in a list (Linear Search)

Top-Down Design (Modular Design)

Top-down design is a problem-solving technique in which a problem is broken down into smaller,
manageable sub-problems (modules), and each is solved individually.
🔍 Definition:
A complex problem is divided into smaller, simpler parts, which are then solved step by step,
starting from the highest level of abstraction to the most detailed.

� Steps in Top-Down Design Approach:

1. Understand the problem

o Read and analyse the requirements.
2. Break the problem into major components
o Identify the main functions/tasks.
3. Break each component into smaller sub-tasks
o Continue until tasks are simple enough to be coded directly.
4. Develop pseudocode or flowchart
o For each sub-task, plan the logic.
5. Translate into code
o Implement the solution in a programming language.

🔄 Top-Down vs Bottom-Up Approach

Feature Top-Down Design Bottom-Up Design

Approach Starts from general to specific Starts from specific to general
Focus System as a whole Individual components
Control High-level control first Low-level details first
Example Designing main program then modules Designing modules first then integrating

🔧 Benefits of Top-Down Design:

 Simplifies complex problems
 Encourages code reuse through modularity
 Improves code readability and maintainability
 Makes debugging and testing easier

📝 Example: Calculate Student Grade (Top-Down Approach)

Main Problem: Calculate and display student grade
Sub-problems:
1. Input student marks
2. Calculate total and average
3. Determine grade based on average
4. Display result

 Algorithm: Input Student Marks

Step 1 :Start
Step 2 :Declare a variable to store number of subjects
Step 3:Declare an array to store marks
Step 4:Input the number of subjects
Step 5:Use a loop to input marks for each subject and store them in the array
Step 6:Display the entered marks (optional)
Step 7:End
C Program: Input Student Marks

#include <stdio.h>
#include<conio.h>
void main()
{
int numSubjects, i;
float marks[100]; // Array to store marks
clrscr();
// Step 1: Input number of subjects
printf("Enter the number of subjects: ");
scanf("%d", &numSubjects);

// Step 2: Input marks for each subject

for (i = 0; i < numSubjects; i++) {
printf("Enter marks for subject %d: ", i + 1);
scanf("%f", &marks[i]);
}

// Optional: Display entered marks

printf("\nEntered Marks:\n");
for (i = 0; i < numSubjects; i++) {
printf("Subject %d: %.2f\n", i + 1, marks[i]);
}
getch();
}

Output
Enter the number of subjects: 3
Enter marks for subject 1: 75
Enter marks for subject 2: 88
Enter marks for subject 3: 91

Entered Marks:
Subject 1: 75.00
Subject 2: 88.00
Subject 3: 91.00

 Program to calculate the total and average of student marks along with the algorithm.

✅ Algorithm: Calculate Total and Average

Step 1:Start
Step 2:Declare variables: number of subjects, array for marks, total, and average
Step 3:Input the number of subjects
Step 4:Use a loop to input marks and add them to total
Step 5:Calculate average = total / number of subjects
Step 6:Display total and average
Step 7:End
Program: Calculate Total and Average

#include <stdio.h>
#include<conio.h>
void main()
{
int numSubjects, i;
float marks[100], total = 0.0, average;
clrscr();
// Step 1: Input number of subjects
printf("Enter the number of subjects: ");
scanf("%d", &numSubjects);

// Step 2: Input marks and calculate total

for (i = 0; i < numSubjects; i++) {
printf("Enter marks for subject %d: ", i + 1);
scanf("%f", &marks[i]);
total += marks[i]; // Add each mark to total
}

// Step 3: Calculate average

average = total / numSubjects;

// Step 4: Display results

printf("\nTotal Marks: %.2f\n", total);
printf("Average Marks: %.2f\n", average);
getch();
}
� Output
Enter the number of subjects: 4
Enter marks for subject 1: 75
Enter marks for subject 2: 85
Enter marks for subject 3: 90
Enter marks for subject 4: 80

Total Marks: 330.00

Average Marks: 82.50

 Program that determines the grade based on the average marks, along with a simple algorithm.
✅ Algorithm: Determine Grade Based on Average
Step 1 :Start
Step 2 :Declare variables: average (float), grade (char)
Step 3 :Input the average marks
Step 4 :Use if-else statements to determine grade:
A: average ≥ 90
B: 80 ≤ average < 90
C: 70 ≤ average < 80
D: 60 ≤ average < 70
F: average < 60
Step 5 :Display the grade
Step 6 :End
Program: Determine Grade Based on Average
#include <stdio.h>
#include<conio.h>
void main()
{
float average;
char grade;
clrscr();
// Step 1: Input average marks
printf("Enter the average marks: ");
scanf("%f", &average);

// Step 2: Determine grade based on average

if (average >= 90)
grade = 'A';
else if (average >= 80)
grade = 'B';
else if (average >= 70)
grade = 'C';
else if (average >= 60)
grade = 'D';
else
grade = 'F';
// Step 3: Display the grade
printf("Grade: %c\n", grade);
getch();
}
Output: Enter the average marks: 78
Grade: C

 Efficiency of algorithms
Algorithm efficiency in problem-solving refers to how well an algorithm uses computational resources
like time and memory to solve a problem, especially as the input size increases. It's crucial for creating
effective and scalable solutions, particularly in fields like computer science and engineering.

Why Algorithm Efficiency Matters:

Performance:
Efficient algorithms lead to faster execution times and better overall system performance.
Cost Savings:
Minimizing resource usage can result in lower operational costs.
Scalability:
Efficient algorithms can handle larger datasets and more complex problems, making them suitable
for real-world applications.
Problem Solving:
By understanding and applying efficient algorithms, developers can create more effective solutions
to complex problems.
 Analysis of algorithms :
Algorithm analysis in C involves evaluating the efficiency and resource usage (time and space) of
algorithms implemented in the C programming language. It helps determine how an algorithm's performance
scales with increasing input size and aids in selecting the most efficient algorithm for a specific task.

Key Concepts in Algorithm Analysis:

 Time Complexity: Measures the amount of time an algorithm takes to run as a function of
the input size.
 Space Complexity: Measures the amount of memory an algorithm uses as a function of the
input size.
 Asymptotic Analysis: Focuses on the growth rate of time and space complexity as the input
size approaches infinity. Common notations include:
Big O (O): Represents the upper bound of the growth rate (worst-case).
Big Omega (Ω): Represents the lower bound of the growth rate (best-case).
Big Theta (Θ): Represents the tight bound of the growth rate (average-case).
 Worst-Case Analysis: Considers the input that causes the algorithm to take the longest time.
 Best-Case Analysis: Considers the input that causes the algorithm to take the shortest time.
 Average-Case Analysis: Considers the average time taken by the algorithm over all possible
inputs.
 Amortized Analysis: Analysis the average time complexity of a sequence of operations,
even if some operations are significantly slower than others.

 Flowchart and it’s symbols:

 UNIT II -Fundamentals of Algorithms

 Exchanging the value of two variables :

Method 1: Using a Temporary Variable
Step 1: temp = A
Step 2: A = B
Step 3: B = temp
Example:
A=5
B = 10
temp = A
A=B
B = temp
A = 10, B = 5

Method 2: Without Using a Temporary Variable (Using Arithmetic)

Step 1: A = A + B
Step 2: B = A - B
Step 3: A = A - B
Example:
A=5
B = 10
A = A + B # A = 15
B=A-B #B=5
A = A - B # A = 10

Program: Swap Two Numbers Using a Temporary Variable

#include <stdio.h>
#include<conio.h>
void main()
{
int A, B, temp;
clrscr();
// Input values from user
printf("Enter value of A: ");
scanf("%d", &A);

printf("Enter value of B: ");

scanf("%d", &B);

// Display before swapping

printf("\nBefore swapping:\n");
printf("A = %d, B = %d\n", A, B);

// swapping logic using a temporary variable

temp = A;
A = B;
B = temp;
 // Display after swapping
printf("\nAfter swapping:\n");
printf("A = %d, B = %d\n", A, B);
getch();
}
Sample Output:
Enter value of A: 5
Enter value of B: 10
Before swapping:
A = 5, B = 10
After swapping:
A = 10, B = 5

 Summation of set of numbers :

#include <stdio.h>
#include<conio.h>
void main()
{
int n, i, number, sum = 0;
clrscr();
// Ask user how many numbers they want to sum
printf("Enter the total number of elements: ");
scanf("%d", &n);

// Loop to get input and calculate sum

for (i = 1; i <= n; i++) {
printf("Enter number %d: ", i);
scanf("%d", &number);
sum += number; // Add number to sum
}

// Output the result

printf("The total sum is: %d\n", sum);
getch();
}
Output :
Enter the total number of elements: 4
Enter number 1: 5
Enter number 2: 10
Enter number 3: 15
Enter number 4: 20
Output:
The total sum is: 50
 Factorial computation

Input : n = 5
Output: 120
Explanation: 5! = 5 * 4 * 3 * 2 * 1 = 120

Input: n = 4
Output: 24
Explanation: 4! = 4 * 3 * 2 * 1 = 24

Input: n = 0
Output: 1

Input: n = 1
Output: 1

#include <stdio.h>
#include<conio.h>
// function to find factorial of given number
int factorial(int n)
{
int res = 1, i;
for (i = 2; i <= n; i++)
res *= i;
return res;
}

int main()
{
int num = 5;
clrscr();
printf("Factorial of %d is %d", num, factorial(num));
return 0;
getch();
}
OUTPUT: Factorial of 5 is 120
 Generation of the Fibonacci sequence: The Fibonacci sequence is a series of numbers
where each number is the sum of the two preceding ones, typically starting from 0 and 1.

0, 1, 1, 2, 3, 5, 8, 13, ...

ALGORITH :
STEP 1:Start
STEP 2: Initialize three integer variables:
first = 0 (to hold the first Fibonacci number)
second = 1 (to hold the second Fibonacci number)
next (to hold the next number in the sequence)
STEP 3:Input the number of terms n from the user.
STEP 4:Print the message: "Fibonacci Sequence:"
STEP 5: Repeat the following steps for i from 0 to n - 1:
a. If i == 0, then:
Set next = 0
b. Else if i == 1, then:
Set next = 1
c. Else, for all other values of i:
Set next = first + second
Update first = second
Update second = next
d. Print the value of next
STEP 6: End of loop
STEP 7: End

Program -
#include <stdio.h>
#include<conio.h>
void main()
{
int n, first = 0, second = 1, next, i;
clrscr();
// Asking the user for number of terms
printf("Enter the number of terms: ");
scanf("%d", &n);

printf("Fibonacci Sequence: ");

for (i = 0; i < n; i++)

{
if (i == 0)
{
next = 0;
}
else if (i == 1)
{
next = 1;
}
else
{
next = first + second;
first = second;
second = next;
 }
printf("%d ", next);
}
getch();
}

🔹Output:
Enter the number of terms: 10
Fibonacci Sequence: 0 1 1 2 3 5 8 13 21 34

 Reverses the Digits of an Integer :

#include <stdio.h>
#include<conio.h>
int main()
{
int n, reverse = 0, remainder, original;
clrscr();
printf("Enter an integer: ");
scanf("%d", &n);
original = n;
while (n != 0)
{
remainder = n % 10;
reverse = reverse * 10 + remainder;
n /= 10;
}
if (original % 10 == 0)
{
printf("Reversed number = %d", reverse);
while (original % 10 == 0)
{
printf("0");
original /= 10;
}
} else
{
printf("Reversed number = %d", reverse);
}
return 0;
getch();
}
Output Enter an integer: 2345
Reversed number = 5432

 This program takes integer input from the user. Then the while loop is used until n != 0 is false (0).
 In each iteration of the loop, the remainder when n is divided by 10 is calculated and the value of n is
reduced by 10 times.
 Inside the loop, the reversed number is computed using:
reverse = reverse * 10 + remainder;
 Let us see how the while loop works when n = 2345 .

n n != 0 remainder reverse

2345 true 5 0 * 10 + 5 = 5

234 true 4 5 * 10 + 4 = 54

23 true 3 54 * 10 + 3 = 543

2 true 2 543 * 10 + 2 = 5432

0 false - Loop terminates.

 Unit – III Factoring Methods

 The Smallest divisors of an integer

Algorithm :
STEP 1: START
STEP 2: Declare two integer variables:
num → to store the input number
i → loop counter
STEP 3: Prompt the user to enter an integer greater than 1.
STEP 4: Read the value and store it in num.
STEP 5: Check if (num <=1):
Print: "Invalid input. Enter a number greater than 1."
Else:
Continue to the next step.
STEP 6: Loop from i = 2 to i <= num:
For each i, check if (num % i == 0):
Print: "The smallest divisor of num is i"
Break the loop (since the smallest divisor is found)
STEP 7: END

#include <stdio.h>
#include<conio.h>
int main()
{
int num, i;
clrscr();
// Input from user
printf("Enter an integer greater than 1: ");
scanf("%d", &num);

// Check for valid input

if (num <= 1) {
printf("Invalid input. Enter a number greater than 1.\n");
return 1;
}

// Find the smallest divisor greater than 1

for (i = 2; i <= num; i++) {
if (num % i == 0) {
printf("The smallest divisor of %d is %d\n", num, i);
break;
}
}

return 0;
getch();
}

🔍 How It Works:
 It reads an integer from the user.

 It checks all numbers starting from 2 up to num.

  The first number that divides num exactly (i.e., num % i == 0) is the smallest divisor.

 If num is a prime number, it will print num itself, since no smaller number (other than 1)
divides it.

� Example Output:
Enter an integer greater than 1: 91
The smallest divisor of 91 is 7

 Generating Prime Numbers :

Few basic rules as it related to programming:
 Divisibility Rule: A prime number is only divisible by 1 and itself.
 Greater Than 1: Prime numbers must be greater than 1.
 No Negative or Decimal Values: Prime numbers are always positive whole numbers.
 Unique Prime Factors: Each number greater than 1 can be expressed as a product of prime
factors (important in coding for factorization).
 Number 1 is Not Prime: By definition, 1 is not a prime number because it has only one
divisor.

Algorithm :
STEP 1: Start
STEP 2: Declare the necessary variables:
i → loop counter for checking divisibility
num → current number being checked for prime
n → upper limit of the range
count → flag to check if a number is divisible (i.e., not prime)
STEP 3: Prompt the user to enter the range (i.e., value of n).
STEP 4: Read the value of n.
STEP 5: Print a message: "The prime numbers between 1 and n are:"
STEP 6: Loop through numbers from num = 2 to num <= n:
(Start from 2 since 1 is not a prime number)
a. Set count = 0 (to assume num is prime initially)
b. Loop from i = 2 to i <= num / 2:
If num % i == 0:
Set count = count + 1 (means num is divisible)
Break the inner loop (not a prime, no need to check further)
c. After inner loop, If count == 0:
Print num (it is a prime number)
STEP 7: Print a newline for clean output.
STEP 8: End
 #include <stdio.h>
#include<conio.h>
void main()
{
int i, num, n, count;
clrscr();
// Take input for the range
printf("Enter the range: ");
scanf("%d", &n);

// Print the prime numbers in the given range

printf("The prime numbers between 1 and %d are: ", n);

for (num = 2; num <= n; num++)

{ // Start from 2 since 1 is not a prime number
count = 0; // Reset the count for each number

for (i = 2; i <= num / 2; i++)

{ // Check divisors from 2 to num/2
if (num % i == 0)
{ // If divisible, it's not a prime number
count++;
break; // Exit the loop if a divisor is found
}
}

// If count is still 0, the number is prime

if (count == 0)
{
printf("%d ", num);
}
}
printf("\n"); // Print a newline for cleaner output
getch();
}
Output:
Enter the range: 50
The prime numbers between 1 and 50 are: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
 Definition and Memory Representation of Array

 Definition:
Array is a collection of elements of the same data type stored in contiguous memory locations.
 Fixed Size: Arrays have a fixed size determined at the time of declaration, and this size
cannot be changed during runtime.

 Homogeneous Elements: All elements within an array must be of the same data type, e.g.,
an array declared as int arr[5] can only store integer values.

 Indexed Access: Elements are accessed using an index, which represents the position of the
element in the array. Array indices typically start from 0.

Syntax: array_name [index];

 Memory representation: Arrays are stored in contiguous memory locations.

 When an array is declared, the compiler allocates a block of memory of the specified size for
the array.

 For example, if an integer array of five elements is declared, and each integer takes four
bytes, then 20 bytes will be allocated to the array.

 The first element is stored at the base address of the array, and subsequent elements are stored
at consecutive memory locations.

 The address of each element can be calculated by adding an offset (index multiplied by the
size of the data type) to the base address.

 Multidimensional arrays are also stored in contiguous memory locations, typically following
row-major order (meaning elements of the first row are stored first, followed by the elements
of the second row, and so on).

For example, if an int array arr has a base address of 1000 and each int takes 4 bytes:
arr[0] is at address 1000.
arr[1] is at address 1004.
arr[2] is at address 1008.
Program –
#include <stdio.h>
#include<conio.h>
void main()
{
int arr[5] = {2, 4, 8, 12, 16};
clrscr();
printf("%d ", arr[2]);
printf("%d ", arr[4]);
printf("%d ", arr[0]);
getch();
}
Output- 8 16 2
 Array order reversal
Reversing an array in C can be achieved efficiently using an in-place swapping method, which
avoids the need for a temporary array and reduces memory usage.
Examples:
Input: arr[] = [1, 4, 3, 2, 6, 5]
Output: [5, 6, 2, 3, 4, 1]
Explanation: The first element 1 moves to last position, the second element 4 moves to second-last
and so on.

Input: arr[] = [4, 5, 1, 2]

Output: [2, 1, 5, 4]
Explanation: The first element 4 moves to last position, the second element 5 moves to second last
and so on.

Algorithm :
STEP 1: Start
STEP 2: Create a function to swap two numbers
Take two numbers a and b
Use a temporary variable to swap their values
STEP 3: Create a function to reverse the array
Set left = 0 (start of array)
Set right = n - 1 (end of array)
While left < right:
Swap the elements at left and right
Increase left by 1
Decrease right by 1
STEP 4: In main function:
Create an array: {1, 4, 3, 2, 6, 5}
Find its size
Call the reverse function
Print the array
STEP 5: End

Program –
#include <stdio.h>
#include<conio.h>
// Function to swap two numbers
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

// function to reverse an array

void reverseArray(int arr[], int n)
{
// Initialize left to the beginning
// and right to the end
int left = 0, right = n - 1;
// Iterate till left is less than right
while (left < right)
{
// Swap the elements at left
// and right position
 swap(&arr[left], &arr[right]);
// Increment the left pointer
left++;
// Decrement the right pointer
right--;
}
}
void main()
{
int arr[] = { 1, 4, 3, 2, 6, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
clrscr();
reverseArray(arr, n);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
getch():
}

Output - 5 6 2 3 4 1

 Array Counting :
The Length of an array in C refers to the maximum number of elements that an array can hold.
It must be specified at the time of declaration. It is also known as the size of an array that is used to
determine the memory required to store all of its elements.
Algorithm :
STEP 1 : Start
STEP 2 : Declare an array variable arr[5]
STEP 3 : Calculate size: n = sizeof(arr) / sizeof(arr[0])
STEP 4 : Print n
STEP 5 : End

void main()
{
int arr[5] = { 1, 2, 3, 4, 5 };
// Find the size of the array arr
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d", n);
getch();
}
Output - 5

 Finding the Maximum number in a set :

Arrays are data structures that allow the user to store a collection of data of the same type. In
this article, we will learn how we can find the maximum value in an array in C.
Example
Input: arr = {5,3,1,2,4}
Output: The maximum value of the array is: 5

Algorithm
1. Initialize a variable maxVal with value arr[0].
2. Traverse through the whole array. During traversal:
I. If maxVal is less than the current value of array update the value of maxVal.
II. Else continue.
3. Exit the loop after whole traversal and Print res which denotes the maximum value in array.
// C program to find maximum value in an array
#include <stdio.h>
int main()
{
// Initialize an array
int arr[] = { 23, 12, 45, 20, 90, 89, 95, 32, 65, 19 };
// Find the size of the array
int n = sizeof(arr) / sizeof(arr[0]);
// Intialize the variable which will denote the maximum
// element
int res = arr[0];
// Find the maximum value in the array and store it in
// res
for (int i = 0; i < n; i++)
{
if (res < arr[i])
res = arr[i];
}
// print the elements of the array
printf("Array Elements: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// print the maximum value
printf("The maximum value of the array is: %d", res);
return 0;
}

Output:
Array Elements: 23 12 45 20 90 89 95 32 65 19
The maximum value of the array is: 95
 Unit IV - Searching And Sorting Methods
 Linear Search:
Linear search is a type of sequential searching algorithm. In this method, every element within the
input array is traversed and compared with the key element to be found. If a match is found in the
array the search is said to be successful; if there is no match found the search is said to be
unsuccessful and gives the worst-case time complexity.

For instance, in the given animated diagram, we are searching for an element 33. Therefore, the
linear search method searches for it sequentially from the very first element until it finds a match.
This returns a successful search.

In the same diagram, if we have to search for an element 46, then it returns an unsuccessful search
since 46 is not present in the input.

 Linear Search Algorithm

The algorithm for linear search is relatively simple. The procedure starts at the very first index of the input
array to be searched.

Step 1 − Start from the 0th index of the input array, compare the key value with the value present in the 0th
index.
Step 2 − If the value matches with the key, return the position at which the value was found.
Step 3 − If the value does not match with the key, compare the next element in the array.
Step 4 − Repeat Step 3 until there is a match found. Return the position at which the match was found.
Step 5 − If it is an unsuccessful search, print that the element is not present in the array and exit the program.

Pseudocode
procedure linear_search (list, value)
for each item in the list
if match item == value
return the item's location
end if
end for
end procedure

Program for linear search

#include<stdio.h>
#include<conio.h>
void linear_search(int a[], int n, int key)
{
int i, count = 0;
for(i = 0; i < n; i++) {
if(a[i] == key) { // compares each element of the array
printf("The element is found at %d position\n", i+1);
 count = count + 1;
}
}
if(count == 0) // for unsuccessful search
printf("The element is not present in the array\n");
}
void main()
{
int i, n, key;
int a[10] = {12, 44, 32, 18, 4, 10};
clrscr();
n = 6;
key = 18;
linear_search(a, n, key);
key = 23;
linear_search(a, n, key);
getch();
}
Output :
The element is found at 4 position
The element is not present in the array

 Binary Search:
Binary search is a fast search algorithm with run-time complexity of (log n). This search algorithm
works on the principle of divide and conquer, since it divides the array into half before searching. For this
algorithm to work properly, the data collection should be in the sorted form.

Binary search looks for a particular key value by comparing the middle most item of the collection. If a
match occurs, then the index of item is returned. But if the middle item has a value greater than the key
value, the right sub-array of the middle item is searched. Otherwise, the left sub-array is searched. This
process continues recursively until the size of a subarray reduces to zero.

Binary Search Algorithm

Binary Search algorithm is an interval searching method that performs the searching in intervals only.
The input taken by the binary search algorithm must always be in a sorted array since it divides the array
into subarrays based on the greater or lower values. The algorithm follows the procedure below –

Step 1 − Select the middle item in the array and compare it with the key value to be searched. If it is
matched, return the position of the median.
Step 2 − If it does not match the key value, check if the key value is either greater than or less than the
median value.
Step 3 − If the key is greater, perform the search in the right sub-array; but if the key is lower than the
median value, perform the search in the left sub-array.
Step 4 − Repeat Steps 1, 2 and 3 iteratively, until the size of sub-array becomes 1.
 Step 5 − If the key value does not exist in the array, then the algorithm returns an unsuccessful search.

Pseudocode
The pseudocode of binary search algorithms should look like this –

Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound
EXIT: x does not exists.
set midPoint = lowerBound + ( upperBound - lowerBound ) / 2

if A[midPoint] < x
set lowerBound = midPoint + 1

if A[midPoint] > x
set upperBound = midPoint - 1

if A[midPoint] = x
EXIT: x found at location midPoint
end while
end procedure

Program for binary search:

#include<stdio.h>
#include<conio.h>
void binary_search(int a[], int low, int high, int key)
{
int mid;
mid = (low + high) / 2;
if (low <= high)
{
if (a[mid] == key)
printf("Element found at index: %d\n", mid);
else if(key < a[mid])
binary_search(a, low, mid-1, key);
else if (a[mid] < key)
binary_search(a, mid+1, high, key);
} else if (low > high)
printf("Unsuccessful Search\n");
}
void main()
{
int i, n, low, high, key;
int a[10] = {12, 14, 18, 22, 39};
clrscr();
n = 5;
low = 0;
 high = n-1;
key = 22;
binary_search(a, low, high, key);
key = 23;
binary_search(a, low, high, key);
getch();
}
Output : Element found at index: 3
Unsuccessful Search

 Bubble Sort, Selection Sort:

The task of arranging elements of an array in a particular order is referred to as sorting. The sorting
of an array or a list is mainly done to make the searching easier. There are two types of sorting
algorithms namely, Bubble Sort and Selection Sort.

Bubble sort performs sorting of data by exchanging the elements, while the selection sort performs
sorting of data by selecting the elements.

Read this article to learn more about bubble sort and selection sort and how these two sorting
techniques are different from each other.

What is Bubble Sort?

Bubble sort is a simple sorting algorithm. Bubble sort iterates through a list and compares adjacent
pairs of elements to sort them. It swaps the elements of an array based on the adjacent elements.

The major advantage of bubble sort is that it is more efficient in comparison to selection sort.
However, it is slower in comparison to selection sort.

Bubble sort uses item exchanging to swap elements. Therefore, the elements are repeatedly swapped
in bubble sorting until all the elements are in the right order.

ALGORITHM:
STEP 1 : Start
STEP 2: Initialize array arr = [2, 0, 1, 4, 3] and size n = 5
STEP 3 : Call function Bubble_Sort(arr, n)
STEP 4: Inside Bubble_Sort, repeat for i = 1 to n - 1:
a. Set flag = false
b. Repeat for j = 0 to n - i - 1:
i. If arr[j] > arr[j + 1], then swap them and set flag = true
c. If flag == false, break the loop (array is sorted)
STEP 5: Return to main() after sorting is complete
STEP 6: Display message: "The Sorted Array by using Bubble Sort is :"
STEP 7 Print all elements of arr from index 0 to n - 1
STEP 8 :End

Program for bubble sort –

#include <stdio.h>
#include<conio.h>
// Function for bubble sort
void Bubble_Sort(int arr[], int n)
{
bool flag;
// Iterate from 1 to n - 1
for (int i = 1; i < n; ++i)
{
flag = false;
// Iterate from 0 to n - i - 1
for (int j = 0; j <= (n - i - 1); ++j)
{
if (arr[j] > arr[j + 1])
{
swap(arr[j], arr[j + 1]);
flag = true;
}
}
if (flag == false)
break;
}
}
void main()
{
int n = 5;
int arr[5] = { 2, 0, 1, 4, 3 };
clrscr();
Bubble_Sort(arr, n);
cout << "The Sorted Array by using Bubble Sort is : ";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
getch();
}

Output : The Sorted Array by using Bubble Sort is : 0 1 2 3 4

What is Selection Sort?

Selection sort is a sorting algorithm which takes either the minimum value (ascending
order) or the maximum value (descending order) in the list and places it at the proper position. The
minimum or the maximum number from the list is obtained first. Next, it selects the minimum or
maximum element from unsorted sub-array and puts it in the next position of the sorted sub-array,
and so on. Selection sort is considered as an unstable sorting algorithm.

Selection sort algorithm is relatively more efficient in comparison to bubble sort. However, the
number of comparisons made during iterations is more than the element swapping that is done. Also,
in selection sort, the location of every element in a list is previously known. This means the user only
searches for the element that needs to be inserted at a specific position. Selection sort is quick in
comparison to bubble sort and it uses item selection for sorting of elements.

Following is the 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.
Program for selection sort
#include<stdio.h>
#include<conio.h>
void Selection_Sort(int arr[], int n)
{
for(int i = 0; i < n - 1; ++i)
{
int min_index = i;
for(int j = i + 1; j < n; ++j)
{
if(arr[j] < arr[min_index])
min_index = j;
}
swap(arr[i], arr[min_index]);
}
}
void main()
{
int n = 5;
int arr[5] = {2, 0, 1, 4, 3};
Selection_Sort(arr, n);
cout<<"The Sorted Array by using Selection Sort is : ";
for(int i = 0; i < n; ++i)
printf(“%d”,arr[i]);
getch();
}

Output
The Sorted Array by using Selection Sort is : 0 1 2 3 4

The differences between Bubble Sort and Selection Sort in a tabular form -:
[Link]. Bubble Sort Selection Sort
1. Bubble sort is a simple sorting algorithm Selection sort is a sorting algorithm which takes
which continuously moves through the list either smallest value (ascending order) or largest
and compares the adjacent pairs for proper value (descending order) in the list and place it at
sorting of the elements. the proper position in the list.
2. Bubble sort compares the adjacent elements Selection sort selects the smallest element from the
and move accordingly. unsorted list and moves it at the next position of
the sorted list.
3. Bubble sort performs a large number of Selection sort performs comparatively less number
swaps or moves to sort the list. of swaps or moves to sort the list.
4. Bubble sort is relatively slower. Selection sort is faster as compared to bubble sort.
5. The efficiency of the bubble sort is less. The efficiency of the selection sort is high.
6. Bubble sort performs sorting of an array by Selection sort performs sorting of a list by the
exchanging elements. selection of element.
 Insertion Sort:
Insertion sort is a very simple method to sort numbers in an ascending or descending order.
This method follows the incremental method. It can be compared with the technique how cards are
sorted at the time of playing a game.

This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is

always sorted. For example, the lower part of an array is maintained to be sorted. An element which
is to be 'inserted' in this sorted sub-list, has to find its appropriate place and then it has to be inserted
there. Hence the name, insertion sort.

The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list
(in the same array). This algorithm is not suitable for large data sets as its average and worst case
complexity are of (n2), where n is the number of items.

Insertion Sort Algorithm

Now we have a bigger picture of how this sorting technique works, so we can derive simple steps by
which we can achieve insertion sort.
Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

Pseudocode
Algorithm: Insertion-Sort(A)
for j = 2 to [Link]
key = A[j]
i = j 1 while i > 0 and
A[i] > key A[i + 1] = A[i]
i = i -1
A[i + 1] = key

Program for insertion sort

#include <stdio.h>
#include<conio.h>
void insertionSort(int array[], int size)
{
int key, j;
for(int i = 1; i<size; i++)
{
key = array[i];//take value
j = i;
while(j > 0 && array[j-1]>key)
{
array[j] = array[j-1];
j--;
}
array[j] = key; //insert in right place
}
}
void main()
{
int n;
int arr[5] = {67, 44, 82, 17, 20}; // initialize the array
n = 5;
clrscr();
printf("Array before Sorting: ");
for(int i = 0; i<n; i++)
printf("%d ",arr[i]);
printf("\n");
insertionSort(arr, n);
printf("Array after Sorting: ");
for(int i = 0; i<n; i++)
printf("%d ", arr[i]);
printf("\n");
getch();
}

Output
Array before Sorting: 67 44 82 17 20
Array after Sorting: 17 20 44 67 82