Sorting Algorithms

Bubble Sort

 Process: Pass through the array multiple times. During each pass, adjacent elements
are compared and swapped if they are in the wrong order.

 Steps:

o Start from the beginning and compare each pair of elements.

o Swap if the left element is greater than the right.

o Repeat until the array is sorted (you can optimize by reducing the length of each
pass).

 Best Case (O(n)): If the array is already sorted, only one pass is required.

Selection Sort

 Process: Divides the array into a sorted section (starting empty) and an unsorted
section.

 Steps:

o For each position, find the smallest element in the unsorted section.

o Swap it with the element at the current position.

o Continue until all elements are sorted.

 Advantage: Uses a fixed number of swaps (n-1), making it useful for cases where
swapping is costly.
Insertion Sort

 Process: Builds the sorted section of the array one element at a time.

 Steps:

o Start with the second element (first element is considered sorted).

o Pick the current element and move it back through the sorted section, inserting it
in its correct position.

o Repeat until all elements are sorted.

 Best Case (O(n)): Very efficient for nearly sorted arrays, making only necessary shifts.

2. Linear Search

 Process: Starts at the first element and moves through the array one-by-one.

 Steps:

o Check each element of the array from start to end.

o If the target element is found, return its index.

o If the loop ends without finding it, return -1 or indicate "not found."

 Best Case: O(1) if the element is at the first position.

1. Linear Search

 Concept: A straightforward approach that searches through the array sequentially.

 Process:

o Start at the first element.

 o Check each element one-by-one until the target is found or the end of the array is
reached.

o If found, return the index; if not, return -1.

 Time Complexity:

o Worst and Average Case: O(n), where n is the number of elements.

o Best Case: O(1), if the element is at the start of the array.

 Use Case: Works for unsorted data and small arrays but is inefficient for large datasets.-

2. Binary Search

 Concept: Efficient search algorithm that requires the array to be sorted. It repeatedly
divides the search interval in half.

 Process:

o Start with the middle element of the array.

o If the middle element matches the target, return its index.

o If the middle element is greater than the target, search the left half. If it’s smaller,
search the right half.

o Repeat until the target is found or the interval is empty.

 Time Complexity:

o Worst and Average Case: O(log n), which is much faster than linear search for
large arrays.

o Best Case: O(1), if the target is at the middle.

  Use Case: Preferred for large, sorted datasets due to its efficiency.

Aspect Bubble Sort Selection Sort Insertion Sort

Repeatedly swaps Finds the minimum Builds the sorted section

adjacent elements if element from the unsorted one element at a time by
Process they’re out of order. part and moves it to the inserting each element in its
 sorted part. correct position.
Time Worst & Average: O(n²), Worst, Average, Best: Worst & Average: O(n²),
Complexity Best: O(n) O(n²) Best: O(n)
Space
Complexity O(1) O(1) O(1)
High (frequent adjacent Moderate (shifts elements
Swaps swaps) Low (at most n-1 swaps) instead of frequent swaps)
Inefficient for large Slower due to repeated Efficient for small or nearly
Efficiency arrays minimum searches sorted arrays
When minimizing swaps is
Best Use Small arrays or nearly important, but not for large Small, partially sorted, or
Case sorted data arrays nearly sorted arrays

Functions in C

Definition

A function is a block of code that performs a specific task and can be reused
throughout the program.

Function Components

1. Function Declaration Statement:

2. This is the declaration or prototype of the function, which informs the

compiler about the function’s name, return type, and parameters
before it’s used.

return_type function_name(parameters);

a. Example:
int add(int, int); // Function declaration

3. Function Definition:
This is where the function's actual code is written. It includes the body that
executes when the function is called.

return_type function_name(parameters) {
// Function body
}

a. Example:
int add(int a, int b) {
return a + b; // Function definition
}

4. Function Call Statement:

This is where the function is called or invoked in the program. When the
function is called, it executes its defined task.

function_name(arguments);

a. Example:
int result = add(3, 5); // Function call

5. Calling Function:

This is the function from where another function is called. The calling
function initiates the execution of a called function.

a. Example: In int result = add(3, 5);, the function that

contains this call is the calling function.

6. Called Function:

This is the function that is invoked by the calling function. It executes its
defined task and can return a value to the calling function.
 a. Example: add(3, 5) is the called function in this case.

7. Parameters/Arguments:

a. Parameters are the variables declared in the function definition

that accept the values passed during the function call.
i. Example: In int add(int a, int b), a and b are
parameters.
b. Arguments are the actual values passed to the function when it
is called.
i. Example: In add(3, 5), 3 and 5 are the arguments.

8. Return Statement:

The return statement is used in a function to return a value back to the

calling function. If the function has a return type, the return statement will
return a value of that type.

return value;

a. Example:
return a + b; // Return the result to the calling function

Terminology Summary

Term Definition
Function A statement declaring the function’s signature.
Declaration
Function The full definition of the function that contains the code.
Definition
Function The statement that calls the function to execute.
Call
Statement
Calling The function that invokes another function.
Function
Called The function that is called and executed.
Function
Parameters/ Parameters are variables in the function, while arguments
Arguments are actual values passed during the call.
Return The statement that sends a value back to the calling
Statement function.

Example Code

#include <stdio.h>

// Function declaration
int add(int, int);

int main() {
int result = add(3, 5); // Function call
printf("Sum is: %d\n", result);
return 0;
}

// Function definition
int add(int a, int b) {
return a + b; // Return statement
}

Advantages of Functions

1. Modularity

2. Functions help break down a large program into smaller,

manageable pieces (modules). Each function performs a
specific task, making the program more organized and easier
to manage.

a. Example: A complex task like sorting or searching can

be divided into separate functions, making each part
independently testable and understandable.

3. Debugging is Easy

Since a function is isolated from the rest of the program, it is

easier to identify and fix bugs within specific parts of the
program. When an error occurs, you can quickly isolate the issue
to a particular function.

a. Example: If a function isn’t working correctly, you

can test it independently by providing specific inputs
and checking the output, without needing to test the
entire program.

4. Reusability

Once a function is written, it can be reused in multiple places

throughout the program, reducing the need to rewrite the same
code. This makes programs shorter, easier to maintain, and less
error-prone.

a. Example: A function that calculates the area of a

rectangle can be used anywhere in the program, just by
calling it with different values.

5. Clarity

Functions improve the clarity of a program by encapsulating

complex logic. With meaningful function names, you can make your
code more readable and understandable, which is particularly
helpful for others (or yourself) reading your code in the
future.

a. Example: Instead of writing out the logic for

calculating the area of a rectangle every time, you
can simply call a function named calculateArea(),
which makes the code much clearer and more readable.

Summary of Advantages

Advantag Description
e
Modularit Breaks the program into smaller, manageable parts,
y improving organization.
Debuggin Errors can be isolated to specific functions, making them
g is Easy easier to fix.
Reusabilit Once written, functions can be used multiple times, saving
y effort and reducing redundancy.
Clarity Makes code more readable and understandable by
encapsulating complex logic.

Types of Functions in C

1. Library Functions

2. These are predefined functions that are provided by C libraries to

perform common tasks. They are part of the C standard library, and
you don’t need to define them yourself. To use them, you need to
include the relevant header files.

a. Example: Functions like printf(), scanf(), strlen(), sqrt(),

etc., are all library functions.
b. Usage: You can call them directly in your program to perform
tasks like input/output, mathematical calculations, and string
manipulations without having to write the code yourself.

Example Code:

#include <stdio.h> // Library for input/output functions

#include <math.h> // Library for mathematical functions

int main() {
int num = 25;
printf("Square root of %d is %.2f\n", num, sqrt(num)); //
Using the library function sqrt()
return 0;
}

3. User-Defined Functions

These are functions created by the programmer to perform specific tasks

required in the program. You define the function by specifying its return
type, name, parameters (if any), and the body where the logic is
implemented. User-defined functions help make code modular and reusable.

a. Example: Functions like add(), multiply(), etc., are user-

defined functions.
b. Usage: When a task is too specific or doesn’t exist as a library
function, you write a user-defined function to handle it.

Example Code:

#include <stdio.h>

// User-defined function to add two numbers

int add(int a, int b) {
return a + b;
}

int main() {
int result = add(3, 5); // Calling the user-defined
function add()
printf("Sum is: %d\n", result);
return 0;
}
Summary of Types
Type of Function Description
Library Functions Predefined functions provided by C libraries for
common tasks.
User-Defined Functions created by the programmer for specific
Functions tasks.

Actual Arguments

Actual arguments (also known as actual parameters) are the values or

variables that are passed to the function when it is called. These arguments
are used by the function during its execution.

 Where used: In the function call.

 Example: When calling a function, the values you pass to the
function’s parameters are the actual arguments.
Example Code:

#include <stdio.h>

// Function declaration
void printSum(int a, int b);

int main() {
int x = 5, y = 10;
printSum(x, y); // x and y are the actual arguments
return 0;
}

// Function definition
void printSum(int a, int b) {
printf("Sum is: %d\n", a + b);
}

 Here, x and y are actual arguments passed to the printSum()

function.

Formal Arguments

Formal arguments (also known as formal parameters) are the variables

that are declared in the function definition. They act as placeholders for the
actual arguments that are passed to the function during the call.

 Where used: In the function definition.

 Example: In the function definition, the parameters (e.g., a and b) are
the formal arguments that receive the values passed from the actual
arguments.

Example Code:

#include <stdio.h>

// Function declaration
void printSum(int a, int b); // a and b are formal arguments

int main() {
int x = 5, y = 10;
printSum(x, y); // x and y are the actual arguments
return 0;
}

// Function definition
void printSum(int a, int b) {
printf("Sum is: %d\n", a + b); // a and b are formal
arguments
}

 In the function printSum(), a and b are formal arguments, and they

receive the values of x and y (actual arguments) when the function is
called.

Summary:

Argumen Description Example

t Type
Actual The actual values or variables passed x, y in printSum(x,
Argumen to the function during the call. y);
ts
Formal The variables defined in the function a, b in void
Argumen signature to receive values. printSum(int a,
ts int b)

Return Type in Functions

The return type of a function specifies the type of value the function will
return to the calling function after its execution. It defines the data type of
the value that will be sent back, such as int, float, char, etc. If a function
does not return a value, its return type is specified as void.
Examples of Return Types

1. Return Type with a Value

2. If a function returns an integer value, its return type will be int. Here's
an example:

int add(int a, int b) {

return a + b; // The return type is int, and the function
returns an integer value
}

3. Return Type with void

If a function does not return any value, its return type is void. Here’s an
example:

void printMessage() {
printf("Hello, World!"); // No return value, so the return
type is void
}

4. Return Type with float

A function can also return a float, for example:

float divide(int a, int b) {

return (float)a / b; //The return type is float, and the
function returns a floating-point value
}
Summary

 The return type defines the type of the value the function will return.
 If no value is returned, the return type is void.
 The return type must match the type of the value returned by the
function.

Summary of Return Statement

Type of Function Return Statement
Functions with Return Type Returns a value of the specified type back
(e.g., int, float) to the calling function.
Functions with void Return Exits the function without returning any
Type value.

1. Function without Arguments and without Return Type

 Description: The function does not take any input (no arguments) and
does not return any value (void return type). It performs a task
independently when called.

 Use Case: Ideal for tasks that don’t need input or output, like printing
a fixed message.

Example:

#include <stdio.h>

void greet() { // No arguments, void return type

printf("Hello, World!\n");

int main() {

greet(); // Calls greet, prints message

return 0;

2. Function without Arguments and with Return Type

  Description: The function does not take any input but returns a value
to the calling function.

 Use Case: Suitable when you need to perform a task without inputs
but want to return a result, like generating a constant or calculated
value.

Example:

#include <stdio.h>

int getNumber() { // No arguments, returns int

return 10; // Returns a constant value

int main() {

int num = getNumber(); // Calls getNumber, stores result in num

printf("Number is: %d\n", num);

return 0;

3. Function with Arguments and without Return Type

 Description: The function takes input arguments but does not return
a value (void return type). It processes the input directly.

 Use Case: Useful when a task needs input but doesn’t need to send a
result back, such as printing the sum of two numbers.

Example:

#include <stdio.h>
void add(int a, int b) { // Arguments, void return type

printf("Sum is: %d\n", a + b); // Directly outputs result

int main() {

add(5, 10); // Calls add with arguments 5 and 10

return 0;

4. Function with Arguments and with Return Type

 Description: The function takes input arguments and returns a value

to the calling function.

 Use Case: Ideal for calculations or tasks where input is needed, and
the result should be returned to be used further.

Example:

#include <stdio.h>

int multiply(int a, int b) { // Arguments, returns int

return a * b; // Returns the result of multiplication

int main() {

int product = multiply(4, 5); // Calls multiply, stores result in product

printf("Product is: %d\n", product);

return 0;
}

Summary Table

Category Argume Return Example Function

nts Type Declaration

1. No arguments, no No void void greet();

return type

2. No arguments, with No Non-void int getNumber();

return type

3. With arguments, no Yes void void add(int, int);

return type

4. With arguments, Yes Non-void int multiply(int, int);

with return type

Function Description Syntax/ Example

Type Declaration Explanation

1. Function - No arguments void - Used for simple

without (input values) functionName(voi tasks where no
Arguments are taken. d); input is needed and
and without - No value is no output is
Return Type returned; simply returned.
performs a task. - Example: A
function to print a
message.

2. Function - No arguments int - Used for

without are taken. functionName(voi generating or
Arguments - A value is d); fetching a constant
and with returned to the or calculated value
Return Type calling function. without needing
 inputs.
- Example: A
function that
returns a fixed
number.

3. Function - Takes void - Used for tasks

with arguments functionName(int, needing input,
Arguments (inputs) when int); where only an
and without called. action is performed,
Return Type - No value is such as printing a
returned; only calculated result.
performs an - Example: A
action with function that takes
provided inputs. two numbers and
prints their sum
without returning it.

4. Function - Takes int - Used for tasks

with arguments functionName(int, where input values
Arguments (inputs) when int); are needed and a
and with called. result is to be used
Return Type - Returns a further by the
value back to calling function.
the calling - Example: A
function based function that takes
on inputs. two numbers as
input, calculates
their product, and
returns the result.

1. Call by Value

 Definition: In the Call by Value mechanism, a function receives a

copy of each argument's value. This means any modifications made to
the parameter within the function do not affect the original argument
outside the function.

 How It Works: When a function is called, C creates a new memory

location for each argument passed. The values from the caller are
copied to these new memory locations in the function.
  Use Cases: Suitable when you want to ensure that the original
variables remain unchanged after the function execution, such as in
mathematical operations where you only need the result but don’t
want to change the original values.

Example:

#include <stdio.h>

void addTen(int x) { // Call by Value

x = x + 10; // Modifies local copy of x

printf("Inside function: %d\n", x); // Prints modified value (local copy)

int main() {

int num = 20;

addTen(num); // Passes a copy of num

printf("Outside function: %d\n", num); // Original num remains unchanged

return 0;

Output:

Inside function: 30

Outside function: 20

 Explanation: addTen receives a copy of num. Changing x doesn’t

affect num in main().

2. Call by Reference

 Definition: In the Call by Reference mechanism, a function receives

the memory address (or reference) of the original variable rather than
a copy of its value. Changes made to the parameter directly affect the
original variable outside the function.
  How It Works: The function is given the address of each argument
(usually using pointers in C). Thus, any modification done inside the
function directly affects the original value stored at that address.

 Use Cases: Useful when you want the function to modify the original
data, such as in swapping operations or updating values in a larger
data structure.

Example:

#include <stdio.h>

void addTen(int *x) { // Call by Reference (pointer to int)

*x = *x + 10; // Modifies value at the address of x

printf("Inside function: %d\n", *x); // Prints modified value

int main() {

int num = 20;

addTen(&num); // Passes address of num

printf("Outside function: %d\n", num); // Original num is modified

return 0;

Output:

Inside function: 30

Outside function: 30

 Explanation: addTen directly modifies num by accessing its memory

location, so num is changed in main() as well.

Differences and Similarities between Call by Value and Call by

Reference

Aspect Call by Value Call by Reference

Passing A copy of the variable’s The address (reference) of

Mechanism value is passed to the the variable is passed to the
function. function.
Effect on Changes inside the Changes inside the function
Original function do not affect the directly modify the original
Variable original variable. variable.

Memory More memory is used Less memory is used since

Usage because a copy of the no additional copy is
value is created. created.

Use of Not required. Required to access the

Pointers original variable’s address.

Safety Safer, as it prevents Less safe, as it can

unintended changes to unintentionally alter the
original data. original data.

Performance Slightly slower due to Faster as no copying is

copying overhead, needed; operates directly on
especially for large data. original data.

Similarities:

 Both mechanisms are used for passing arguments to functions in C.

 The choice depends on whether the original data should be modified or

left unchanged.

Syntax Differences
Mechanism Function Declaration and Function Call
Definition
Call by Value void functionName(int x); functionName(var);
- Parameter is a regular - Passes value of
variable var
Call by void functionName(int *x); functionName(&var);
Reference - Parameter is a pointer - Passes address of
variable var