CSL 102-

Data Structures
Module 1

Computer Science and Engineering

Indian Institute of Information Technology, Nagpur.

1
24-02-2026
 Types and Operations:

Types: Refers to the different data types used in a programming language, such as
integers, floats, characters, etc.
Operations: Involves the actions or manipulations that can be performed on these
data types, like addition, subtraction, multiplication, etc.
 Data types

• Each variable in C has an associated data type.

• It specifies the type of data that the variable can store like integer, character,
floating, double
• The data types in C can be classified as follows:

Types Data Types

Basic Data Type int, char, float, double

Derived Data Type array, pointer, structure, union

Enumeration Data Type enum

Void Data Type void

 Data types

• The basic data types are integer-based and floating-point based. C language
supports both signed and unsigned literals.

Type Storage size Value range

char 1 byte -128 to 127 or 0 to 255
unsigned char 1 byte 0 to 255
signed char 1 byte -128 to 127
int 2 or 4 bytes -32,768 to 32,767 or -2,147,483,648 to 2,147,483,647
unsigned int 2 or 4 bytes 0 to 65,535 or 0 to 4,294,967,295
short 2 bytes -32,768 to 32,767
unsigned short 2 bytes 0 to 65,535
long 8 bytes or (4bytes -9223372036854775808 to 9223372036854775807
for 32 bit OS)
unsigned long 8 bytes 0 to 18446744073709551615
 Data types
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <float.h> CHAR_BIT : 8
int main(int argc, char** argv) CHAR_MAX : 127
{ CHAR_MIN : -128
printf("CHAR_BIT : %d\n", CHAR_BIT); INT_MAX : 2147483647
printf("CHAR_MAX : %d\n", CHAR_MAX); INT_MIN : -2147483648
printf("CHAR_MIN : %d\n", CHAR_MIN); LONG_MAX : 2147483647
printf("INT_MAX : %d\n", INT_MAX); LONG_MIN : -2147483648
printf("INT_MIN : %d\n", INT_MIN); SCHAR_MAX : 127
printf("LONG_MAX : %ld\n", (long) LONG_MAX); SCHAR_MIN : -128
printf("LONG_MIN : %ld\n", (long) LONG_MIN); SHRT_MAX : 32767
printf("SCHAR_MAX : %d\n", SCHAR_MAX); SHRT_MIN : -32768
printf("SCHAR_MIN : %d\n", SCHAR_MIN); UCHAR_MAX : 255
printf("SHRT_MAX : %d\n", SHRT_MAX); UINT_MAX : 4294967295
printf("SHRT_MIN : %d\n", SHRT_MIN); ULONG_MAX : 4294967295
printf("UCHAR_MAX : %d\n", UCHAR_MAX); USHRT_MAX : 65535
printf("UINT_MAX : %u\n", (unsigned int) UINT_MAX);
printf("ULONG_MAX : %lu\n", (unsigned long) ULONG_MAX);
printf("USHRT_MAX : %d\n", (unsigned short) USHRT_MAX);
return 0;
 Floating Point

Type Storage size Value range Precision

float 4 byte 1.2E-38 to 3.4E+38 6 decimal places

double 8 byte 2.3E-308 to 1.7E+308 15 decimal places

long double 10 byte 3.4E-4932 to 19 decimal places

1.1E+4932
 Floating-Point Types

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <float.h> Storage size for float : 4
int main(int argc, char** argv) FLT_MAX : 3.40282e+038
{ FLT_MIN : 1.17549e-038
printf("Storage size for float : %d \n", sizeof(float)); -FLT_MAX : -3.40282e+038
printf("FLT_MAX : %g\n", (float) FLT_MAX); -FLT_MIN : -1.17549e-038
printf("FLT_MIN : %g\n", (float) FLT_MIN); DBL_MAX : 1.79769e+308
printf("-FLT_MAX : %g\n", (float) -FLT_MAX); DBL_MIN : 2.22507e-308
printf("-FLT_MIN : %g\n", (float) -FLT_MIN); -DBL_MAX : -1.79769e+308
printf("DBL_MAX : %g\n", (double) DBL_MAX); 23000.000000
printf("DBL_MIN : %g\n", (double) DBL_MIN);
printf("-DBL_MAX : %g\n", (double) -DBL_MAX);
float a=2.3e4;
printf("%f",a);
return 0;
}
 Iterative constructs and loop invariants

Structured programming is a programming paradigm that uses controlled structures

like sequences, selections, and iterations to enhance the clarity, efficiency, and
maintainability of a computer program.

It aims to reduce complexity and make code more understandable by avoiding the
use of "goto" statements and encouraging the use of subroutines or functions.
 C Loops

Loops in programming are used to repeat a block of code until the specified
condition is met.

A loop statement allows programmers to execute a statement or group of

statements multiple times without repetition of code.

There are mainly two types of loops in C Programming:

1. Entry Controlled loops: In Entry controlled loops the test condition is checked
before entering the main body of the loop. For Loop and While Loop is Entry-
controlled loops.

2. Exit Controlled loops: In Exit controlled loops the test condition is evaluated at
the end of the loop body. The loop body will execute at least once, irrespective
of whether the condition is true or false. do-while Loop is Exit Controlled loop.
 C Loops

Loop Type Description

first Initializes, then condition check, then

for loop executes the body and at last, the update is
done.

first Initializes, then condition checks, and

while
then executes the body, and updating can be
loop
inside the body.

do-while do-while first executes the body and then the

loop condition check is done.
 C Loops: for loop in C

The for loop in C language is used to

iterate the statements or a part of the
program several times. #include<stdio.h>
int main()
It is frequently used to traverse the {
data structures like the array and int i=0;
linked list. for(i=1;i<=10;i++)
{ OUTPUT
printf("%d \n",i); 1
} 2
return 0; 3
} 4
5
6
7
8
9
10
 Print table for the given number using
C for loop

#include<stdio.h> OUTPUT
int main() Enter a number: 2
{ 2
int i=1,number=0;
4
printf("Enter a number: ");
scanf("%d",&number); 6
for(i=1;i<=10;i++) 8
{ 10
printf("%d \n",(number*i)); 12
14
} 16
return 0; 18
}
20
 Output

#include <stdio.h>
int main()
{ OUTPUT
int a,b,c; 35 36
for(a=0,b=12,c=23;a<2;a++) {

printf("%d ",a+b+c);
}
}
 Output

#include <stdio.h>
int main()
{ OUTPUT
int n;// variable declaration Enter the value of n :3
printf("Enter the value of n :"); 1 2 3 4 5 6 7 8 9 10
scanf("%d",&n); 2 4 6 8 10 12 14 16 18 20
for(int i=1;i<=n;i++) // outer loop 3 6 9 12 15 18 21 24 27 30
{
for(int j=1;j<=10;j++) // inner loop
{
printf("%d\t",(i*j)); // printing the value.
}
printf("\n");
}
 Output

#include <stdio.h>
int main() { OUTPUT
int i, j, rows; Enter the value of n :5
printf("Enter the number of rows: "); *
scanf("%d", &rows); **
for (i = 1; i <= rows; ++i) ***
{ ****
for (j = 1; j <= i; ++j) *****
{
printf("* ");
}
printf("\n");
}
return 0;
}
 Output

#include <stdio.h>
int main() {
int i, j, rows;
printf("Enter the number of rows: "); OUTPUT
scanf("%d", &rows); Enter the value of n :5
for (i = 1; i <= rows; ++i) 1
{ 12
for (j = 1; j <= i; ++j) 123
{ 1234
printf("%d ", j); 12345
}
printf("\n");
}
return 0;
}
 C Loops: do while

1. The do-while loop continues

until a given condition
satisfies.
2. It is also called post tested
loop
3. simple program of while loop
that prints table of 1.
 C Loops: while loop

1. While loop is also known as a

pre-tested loop.

2. In general, a while loop

allows a part of the code to
be executed multiple times
depending upon a given
boolean condition.

3. It can be viewed as a
repeating if statement. The
while loop is mostly used in
the case where the number
of iterations is not known in
advance.
 C Loops: while loop

while do-while
Statement(s) is executed atleast once, thereafter condition is
Condition is checked first then statement(s) is executed.
checked.

It might occur statement(s) is executed zero times, If

At least once the statement(s) is executed.
condition is false.

No semicolon at the end of while. Semicolon at the end of while.

while(condition) while(condition);

If there is a single statement, brackets are not required. Brackets are always required.

Variable in condition is initialized before the execution of

variable may be initialized before or within the loop.
loop.

while loop is entry controlled loop. do-while loop is exit controlled loop.

while(condition) do { statement(s); }
{ statement(s); } while(condition);
 while and Do While
#include <stdio.h>
#include <stdio.h>
int main() {
int main()
// Write C code here
{
int a=11;
int a=11;
do
while(a==10)
{
{
printf("executed");
printf("Not executed");
printf("%d",a);
printf("%d",a);
}while(a==10);
}
return 0;
return 0;
}
}
OUTPUT:
OUTPUT:
executed
11
 Structured Programming

Structured programming is a programming paradigm that uses controlled structures

like sequences, selections, and iterations to enhance the clarity, efficiency, and
maintainability of a computer program.

It aims to reduce complexity and make code more understandable by avoiding the
use of "goto" statements and encouraging the use of subroutines or functions.
 Loop Invariants

A loop invariant is a condition [among program variables] that is necessarily true

immediately before and immediately after each iteration of a loop.

A loop invariant is some predicate (condition) that holds for every iteration of the
loop.

The loop invariant must be true:

• before the loop starts
• before each iteration of the loop
• after the loop terminates
 Loop Invariant Condition:

Loop invariant condition is a condition about the relationship between the variables of
our program which is definitely true immediately before and immediately after each
iteration of the loop.

For example: Consider an array A{7, 5, 3, 10, 2, 6} with 6 elements and we have to find
maximum element “max” in the array.

max = -INF (minus infinite)

for (i = 0 to n-1)
if (A[i] > max)
max = A[i]

In the above example after the 3rd iteration of the loop max value is 7, which holds
true for the first 3 elements of array A. Here, the loop invariant condition is that max is
always maximum among the first i elements of array A.
 Structured Programming

#include <stdio.h> Output:

Enter values for A and B: 5
int main() { 6
// Declaration and initialization of variables Sum: 11
int num1, num2, sum;

// Input
printf("Enter two numbers: "); 1. Declaration and Initialization: Variables are declared and
scanf("%d %d", &num1, &num2); initialized at the beginning of the program.

// Process 2. Input: User input is obtained using scanf.

sum = num1 + num2;
3. Process: The sum of the two numbers is calculated.
// Output
printf("Sum: %d\n", sum); 4. Output: The result is displayed using printf.

return 0; 5. Structured Control Flow: The flow of control is sequential,

} moving from one statement to the next.
 Modular Design in C

Modular design involves breaking down a program into smaller, independent modules or
functions.
Each function performs a specific task, making the code more modular and easier to
understand.

#include <stdio.h> int main() { The program is divided into three

void getInput(int *num1, int *num2) // Declaration and initialization of variables functions:
{ int num1, num2, sum; getInput,
printf("Enter two numbers: "); calculateSum, and
scanf("%d %d", num1, num2); // Input displayResult.
} getInput(&num1, &num2);
Each function has a specific
int calculateSum(int num1, int num2)
// Process responsibility: getting input,
{
return num1 + num2; sum = calculateSum(num1, num2); performing the calculation, and
} displaying the result.
void displayResult(int sum) // Output
{ displayResult(sum); The main function becomes more
printf("Sum: %d\n", sum); readable and focuses on the overall
} return 0; flow of the program.
}
 Scope

• A scope in any programming is a region of the program where a defined

variable can have its existence and beyond that variable it cannot be
accessed.

• There are three places where variables can be declared in C programming

language −

1. Inside a function or a block which is called local variables.

2. Outside of all functions which is called global variables.
3. In the definition of function parameters which are called formal
parameters.
 Local Variables

• A variable that is declared inside the function or block is called a local

variable.
• It must be declared at the start of the block.
• You must have to initialize the local variable before it is used.

// #include <stdio.h>

void function() Output:

{
int x = 10; // local variable
10
printf("%d", x);
}

int main() { function(); }

 Global Variables in C

• A variable that is declared outside the function or block is called a global

variable.

• Any function can change the value of the global variable. It is available to all
the functions.

• It must be declared at the start of the block.

 Global Variables in C

#include <stdio.h>

/* global variable declaration */

int g = 20;
int main () { OUTPUT:
/* local variable declaration */ value of g = 10
int g = 10;
printf ("value of g = %d\n", g);
return 0;
}
 Global Variables in C

When a local variable is defined, it is not initialized by the system, you

must initialize it yourself.

Global variables are initialized automatically by the system when you

define them as follows −

Data Type Initial Default Value

int 0
char '\0'
float 0
double 0
pointer NULL
 Formal Parameters

int main ()
{
int a = 10;
int b = 20;
int c = 0;
printf ("value of a in main() =
%d\n", a); OUTPUT:
c = sum( a, b);
printf ("value of c in main() = value of a in main() = 10
%d\n", c); value of a in sum() = 10
return 0; value of b in sum() = 20
} value of c in main() = 30
int sum(int a, int b)
{
printf ("value of a in sum() =
%d\n", a);
printf ("value of b in sum() =
%d\n", b);
return a + b;
 Passing Parameters: Call by Value
#include<stdio.h>
int main()
{
void change(int a)
int a=100;
{ printf("In main a= %d\n", a);
printf("In function change a=%d\n ", a); change(a);
printf("Value of a after function calling is %d", a);
a=a+100;
return 0;
printf("After adding a=%d\n",a); }
// return a;
}

24-02-2026 32
 Passing Parameters: Call by Reference
#include<stdio.h>
int main()
{
void change(int *num)
int a=100;
{ printf("In main a= %d\n", a);
printf("In function change a=%d\n ", *num); change(&a);
printf("Value of a after function calling is %d", a);
(*num) += 100;
return 0;
printf("After adding a=%d\n",*num); }
// return a;
}

24-02-2026 33
 Data
• Data is a collection of facts and figures or a set of values or values of a specific
format that refers to a single set of item values. It is also computer Information,
either transmitted or stored.

Data: TEERPSAJ SI EMAN YM Collection of characters

Information: MY NAME IS JASPREET

Systematic
representation

When Data is arranged in systematic way then it gets a structure and becomes
meaningful.
To provide an appropriate way to structure the data and produce meaningful
information we need to understand Data Structure

34
24-02-2026
• A data structure is a storage that is used to store and organize data.
• It is a way of arranging data on a computer so that it can be accessed and updated efficiently.

35
24-02-2026
 Primitive Data Structure Data

• Directly operated upon the machine-level instructions are known as primitive

data structures

• Integer, Floating-point number, Character constants, pointers etc.

• Common Operations
• Create
• Update
• Delete
 Non-Primitive Data Structure

• Derived from the primitive data structures

• Emphasize on structuring of a group of homogeneous (same type) or

heterogeneous (different type) data items

• Common Operations
• Traversal
• Insertion
• Selection
• Search
• Sort
• Merge
• Delete
 Linear Data Structures

Data structure in which data elements are arranged sequentially or linearly,

where each element is attached to its previous and next adjacent elements, is
called a linear data structure. Examples of linear data structures are array,
stack, queue, linked list, etc.

1. Static data structure: Static data structure has a fixed memory size
(allocated at compilation time). It is easier to access the elements in a
static data structure.
An example of this data structure is an array.

2. Dynamic data structure: In dynamic data structure, the size is not

fixed (memory is allocated at runtime). It can be randomly updated
during the runtime which may be considered efficient concerning the
memory (space) complexity of the code.
Examples of this data structure are linked list, queue, stack, etc.
38
24-02-2026
Linear Data Structures
Linear Data Structures
Linear Data Structures
Linear Data Structures
Linear Data Structures
 Non Linear Data Structures

• Data structures where data elements are not placed sequentially or linearly
are called non-linear data structures.
• In a non-linear data structure, we can’t traverse all the elements in a single
run only.
Examples of non-linear data structures are trees and graphs.

44
24-02-2026
Non
NonLinear
LinearData
DataStructures
Structures
Non Linear Data Structures
Non Linear Data Structures
Non Linear Data Structures
Comparison
 Arrays Linear Sequential Access Data Structure

• Array
• Collection of similar data elements
• Each data element is of the same data type

• Elements of the array

• Stored in consecutive memory locations
• Referenced by an index (also known as the subscript)

• Declared using the following syntax

• type arrayname[size];
• int marks[5];
 Contd..

• Memory representation of an Array

 Address of Array Elements

• Address of data element A[i]

A[i] = BA + (i – lower_bound) * size

• BA is the base address of the array A,

• i is the index of the element of which we have to calculate the address,
• size is the size of one element in memory, i.e. size of int is 4
 Address of Array Elements

Given an array
• int marks[8] = {99, 67, 78, 56, 88, 90, 34, 85}
• Calculate the address of marks[4] when the base address = 1000 when
integer size is 2 bytes.

Solution
• marks[4] = 1000 + 2(4 – 0) = 1000 + 2(4) = 1008
 Length of an Array

• The length of an array is given by the number of elements stored in it

• General formula
• Length = upper_bound – lower_bound + 1
where
• upper_bound is the index of the last element
• lower_bound is the index of the first element
 Contd..

• Let Age[5] be an array of integers

• Where Age[0] = 2, Age[1] = 5, Age[2] = 3, Age[3] = 1, Age[4] = 7.
• Calculate the length of the array.
 Operations on Arrays

• Traverse
• Insertion
• Deletion
• Merge
• Search
• Sort
 Traverse Operation

• Accessing each and every element of the array

• Traversing data elements of an array A can include

• printing every element
• counting the total number of elements
• performing any process on these elements

• Example
for (int i = 0; i < n; i++)
printf(“%d\n”, arr[i]);
 Insertion Operation

• Insertion at the End of an existing array

100 104 108 112 116 120 124 128 132 136
10 20 30 40 50
arr[0] arr[1] arr[2] arr[3] arr[4] arr[5] arr[6] arr[7] arr[8] arr[9]

n = 5;
pos = 6;
val = 60;
arr[pos - 1] = val;
n++;
 Insertion Operation

• Insertion at some Position of an existing array

100 104 108 112 116 120 124 128 132 136
10 20 30 40 50 60
arr[0] arr[1] arr[2] arr[3] arr[4] arr[5] arr[6] arr[7] arr[8] arr[9]
n = 6;
pos = 3;
val = 70;
for( i = n - 1; i >= pos - 1; i--)
arr[i+1] = arr[i];
arr[pos-1] = val;
n = n+1;
 Deletion Operation

• Deleting the last element

100 104 108 112 116 120 124 128 132 136
10 20 30 40 50 60
arr[0] arr[1] arr[2] arr[3] arr[4] arr[5] arr[6] arr[7] arr[8] arr[9]

n = 6;
n = n – 1;
 Deletion Operation

• Deletion at some position

100 104 108 112 116 120 124 128 132 136
10 20 30 40 50 60
arr[0] arr[1] arr[2] arr[3] arr[4] arr[5] arr[6] arr[7] arr[8] arr[9]

n = 6; pos = 3;
for (i = pos - 1 ; i < n - 1 ; i++)
arr[i] = arr[i+1];
n--;
 Merge Operation

• Example
int a[10] = {10, 20, 30, 40, 50};
int b[10] = {60, 70, 80};
 Merge two sorted arrays

Given two sorted arrays, the task is to merge them in a sorted

manner.
Example

Create an auxiliary array of size N + M.

Put two pointers i and j and initialise them to 0.
Pointer i points to the first array, whereas pointer j points to
the second array.
Traverse both the array simultaneously using the pointers, and
pick the smallest elements among both the array and insert in
into the auxiliary array.
Increment the pointers.
After traversal, return the merged array.
 Two-Dimensional Arrays

• Store data in the form of grids or tables

• Specified using two subscripts where

• the first subscript denotes the row
• the second denotes the column

• C compiler treats a two-dimensional array as an array of one-dimensional

array

• Declaration
• data_type array_name[row_size][column_size];
• Ex: int marks[2][3];
 Two-Dimensional Arrays

• Ex: Store the marks obtained by three students in five different subjects
int marks[3][5];
• Pictorial form of a two-dimensional array
 Address of 2-D Array Elements

• Row Major Order : the elements of an array are stored in a Row-Wise

fashion.

• Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))

I = Row Subset of an element whose address to be found,
J = Column Subset of an element whose address to be found,
B = Base address,
W = Storage size of one element store in an array(in byte),
LR = Lower Limit of row/start row index of the matrix(If not given assume it as
zero),
LC = Lower Limit of column/start column index of the matrix(If not given assume
it as zero),
N = Number of column given in the matrix.
 Address of 2-D Array Elements

Q. Given an array, arr[1………10][1………15] with base value 100 and the size of each element is 1
Byte in memory. Find the address of arr[8][6] with the help of row-major order.
Base address B = 100
Storage size of one element store in any array W = 1 Bytes
Row Subset of an element whose address to be found I = 8
Column Subset of an element whose address to be found J = 6
Lower Limit of row/start row index of matrix LR = 1
Lower Limit of column/start column index of matrix = 1
Number of column given in the matrix N = Upper Bound – Lower Bound + 1
= 15 – 1 + 1
= 15
• Formula:
Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))
• Solution:
Address of A[8][6] = 100 + 1 * ((8 – 1) * 15 + (6 – 1))
= 100 + 1 * ((7) * 15 + (5))
= 100 + 1 * (110)
Address of A[I][J] = 210
 Address of 2-D Array Elements

• Column Major Order : If elements of an array are stored in a column-

major fashion means moving across the column and then to the next column
then it’s in column-major order.

• Address of A[I][J] = B + W * ((J – LC) * M + (I – LR))

I = Row Subset of an element whose address to be found,
J = Column Subset of an element whose address to be found,
B = Base address,
W = Storage size of one element store in any array(in byte),
LR = Lower Limit of row/start row index of matrix(If not given assume it as
zero),
LC = Lower Limit of column/start column index of matrix(If not given assume it
as zero),
M = Number of rows given in the matrix.
 Address of 2-D Array Elements

Q. Given an array arr[1………10][1………15] with a base value of 100 and the size of each
element is 1 Byte in memory find the address of arr[8][6] with the help of column-major
order.

Base address B = 100

Storage size of one element store in any array W = 1 Bytes
Row Subset of an element whose address to be found I = 8
Column Subset of an element whose address to be found J = 6
Lower Limit of row/start row index of matrix LR = 1
Lower Limit of column/start column index of matrix = 1
Number of Rows given in the matrix M = Upper Bound – Lower Bound + 1
= 10 – 1 + 1
= 10
• Formula: used
Address of A[I][J] = B + W * ((J – LC) * M + (I – LR))
Address of A[8][6] = 100 + 1 * ((6 – 1) * 10 + (8 – 1))
= 100 + 1 * ((5) * 10 + (7))
= 100 + 1 * (57)
Address of A[I][J] = 157
 Initializing Two-Dimensional Arrays

• A two-dimensional array is initialized same a one-dimensional array is

initialized.

• For example,
int marks[2][3]={90, 87, 78, 68, 62, 71};
int marks[2][3]={{90,87,78},{68, 62, 71}};

• Initialization is done row by row

marks[0][0] = 90 marks[0][1] = 87 marks[0][2] = 78
marks[1][0] = 68 marks[1][1] = 62 marks[1][2] = 71
 Initializing Two-Dimensional Arrays

• Note:
• Only the size of the first dimension, can be omitted

int marks[][3]={{90, 87, 78}, {68, 62, 71}};

• Initialize the entire two-dimensional array to zeros

int marks[2][3] = {0};
 Initializing Two-Dimensional Arrays

• Initializing by taking input from user

for(i = 0; i < rows; i++)
{
for(j = 0; j < columns; j++)
{
scanf(“%d”, &arr[i][j]);
}
}
 Initializing Two-Dimensional Arrays
#include <stdio.h>
void main ()
{
int arr[3][3],i,j;
for (i=0;i<3;i++)
{
for (j=0;j<3;j++)
{
printf("Enter a[%d][%d]: ",i,j);
scanf("%d",&arr[i][j]);
}
}
printf("\n printing the elements ....\n");
for(i=0;i<3;i++)
{
printf("\n");
for (j=0;j<3;j++)
{
printf("%d\t",arr[i][j]);
}
}
 Storing a Two-Dimensional Array

• Row major order

• elements of the array are stored row by row where n elements of the
first row will occupy the first n locations
• Column major order
• elements of the array are stored column by column where m elements of
the first column will occupy the first m locations
Storing a Two-Dimensional Array
 Storing a Two-Dimensional Array

• Formula to calculate the address of some element A[I][J]

When Array indices start with 0.

• Array elements are stored in row major order,
Address(A[I][J]) = BA + w{N(I) + J}

• Array elements are stored in column major order

Address(A[I][J]) = BA + w{M(J) + I}
w is the number of bytes required to store one element,
N is the number of columns,
M is the number of rows,
I and J are the subscripts of the array element.
 Storing a Two-Dimensional Array

• Consider a 20 x 5 two-dimensional array marks which has its base address =

1000 and the size of an element = 2. Compute the address of the element,
marks[18][4] assuming that the elements are stored in row major order, and
array indices start with 1.

• Solution
Address(A[I][J]) = BA + w{N(I – 1) + (J – 1)}
Address(marks[18][4]) = 1000 + 2 {5(18 – 1) + (4 – 1)}
= 1000 + 2 {5(17) + 3}
= 1000 + 2 (88)
= 1000 + 176 = 1176
 Visualizing Array

2D Arrays 3D Arrays
Initialize 3D Array
Print Elements of 3D Array
Print Elements of 3D Array
Print Elements of 3D Array
 Recursion
• Recursion is a programming #include <stdio.h>
technique where a function calls
void rec(int n) {
itself repeatedly until a specific
base condition is met. // Base Case
• A function that performs such if (n == 6) return;
self-calling behavior is known as a
printf("Recursion Level %d\n", n);
recursive function, and each
rec(n + 1);
instance of the function calling }
itself is called a recursive call.
1) Direct Recursion int main() {
rec(1);
2) Indirect Recursion return 0;
}
24-02-2026 83
 Recursion

•Recursion is the process of calling a function itself repeatedly until a particular

condition is met.

•A function that calls itself directly or indirectly is called a recursive function and
such kind of function calls are called recursive calls.

•In C, recursion is used to solve a complex problem.

•Using recursion we can solve a complex problem in a small piece of code by

breaking down the problem.

•We can solve large numbers of problems using recursion for example factorial of a
number.
 Recursion
Recursion is the process which comes into existence when a function calls a
copy of itself to work on a smaller problem.
 Recursion

•The basic syntax structure of the recursive functions is:

type function_name (args)

{
// function statements
// base condition
// recursion case (recursive call)
}
 Recursion

If we use iteration, we must be careful not to create an infinite loop by

accident:

for(int incr=1; incr!=10;incr+=2)

...

Oops!
int result = 1;
while(result >0){
...
result++;
}
Oops!
 Recursion

Similarly, if we use recursion we must be careful not to create an

infinite chain of function calls:
int fac(int numb){
return numb * fac(numb-1);
}
Oops!
Or: No termination
condition
int fac(int numb){
if (numb<=1)
return 1;
else
return numb * fac(numb+1);
}

Oops!
 Recursion

We must always make sure that the recursion bottoms out:

• A recursive function must contain at least one non-recursive branch.
• The recursive calls must eventually lead to a non-recursive branch.
 Calculate the sum of the first N natural numbers and solve it
using recursion.
// C Program to calculate the sum of first N natural numbers using recursion
#include <stdio.h>
int nSum(int n)
{
// base condition to terminate the recursion when N = 0
if (n == 0) {
return 0;
}
int res = n + nSum(n - 1);

return res;
} Sum of First 5 Natural Numbers: 15
int main()
{
int n = 5;

// calling the function

int sum = nSum(n);

printf("Sum of First %d Natural Numbers: %d", n, sum);

return 0;
}
 Memory Allocation for Recursive Function

• A stack frame is created on top of the existing stack frames each time a
recursive call is encountered and the data of each recursive copy of the
function will be stored in their respective stack.

• Once, some value is returned by the function, its stack frame will be
destroyed.

• The compiler maintains an instruction pointer to store the address of the

point where the control should return in the function after its progressive
copy returns some value.

• This return point is the statement just after the recursive call.

• After all the recursive copy returned some value, we come back to the base
function and the finally return the control to the caller function.
 Calculate the sum of the first N natural numbers and solve it
using recursion.
// C Program to calculate the sum of first N natural numbers using recursion
#include <stdio.h>
int nSum(int n)
{
// base condition to terminate the recursion when N = 0
if (n == 0) {
return 0;
}
int res = n + nSum(n - 1);

return res;
}
int main()
{
int n = 5;

// calling the function

int sum = nSum(n);

printf("Sum of First %d Natural Numbers: %d", n, sum);

return 0;
}
Memory Allocation for Recursive Function

But when the control comes

to nSum(0), the condition (n
== 0) becomes true and the
statement return 0 is
executed.
 Recursion

• Recursion is one way to decompose a task into smaller subtasks. At least

one of the subtasks is a smaller example of the same task.
• The smallest example of the same task has a non-recursive solution.

Example: The factorial function

n! = n * (n-1)! and 1! = 1
Recursion
• Fibonacci numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
where each number is the sum of the preceding two.

• Recursive definition:
• F(0) = 0;
• F(1) = 1;
• F(number) = F(number-1)+ F(number-2);
Fibonacci numbers
int fibonacci (int n)
#include<stdio.h> {
int fibonacci(int); if (n==0)
{
void main ()
return 0;
{ }
int n,f; else if (n == 1)
{
printf("Enter the value of n?"); return 1;
scanf("%d",&n); }
f = fibonacci(n); else
{
printf("%d",f); return fibonacci(n-1)+fibonacci(n-2);
} }
}
int display (int n) Recursion
{
if(n == 0)
return 0; // terminating condition
else
{
printf("%d",n);
return display(n-1); // recursive call Let us examine this recursive function for n = 4.
}
}
 What is Searching Algorithm?

Searching Algorithms are designed to check for an element or retrieve an element from any
data structure where it is stored.

Based on the type of search operation, these algorithms are generally classified into two
categories:

Sequential Search: In this, the list or array is traversed sequentially and every element is
checked. For example: Linear Search.

Interval Search: These algorithms are specifically designed for searching in sorted data-
structures. These type of searching algorithms are much more efficient than Linear Search as
they repeatedly target the center of the search structure and divide the search space in half.
For Example: Binary Search.
 How Does Linear Search Algorithm Work?

In Linear Search Algorithm,

Every element is considered as a potential match for the key and checked for the same.
If any element is found equal to the key, the search is successful and the index of that element
is returned.

If no element is found equal to the key, the search yields “No match found”.

For example: Consider the array arr[] = {10, 50, 30, 70, 80, 20, 90, 40} and key = 30
 How Does Linear Search Algorithm Work?

// C code to linearly search x in arr[].

Output:
#include <stdio.h> Element is present at index 4
int search(int arr[], int N, int x)
{
for (int i = 0; i < N; i++)
if (arr[i] == x)
return i; Time Complexity:
return -1;
} Best Case: In the best case, the key might be
int main(void) present at the first index. So the best case
{ complexity is O(1)
int arr[] = { 2, 3, 4, 10, 40 }; Worst Case: In the worst case, the key might be
int x = 40; present at the last index i.e., opposite to the end
int N = sizeof(arr) / sizeof(arr[0]);
from which the search has started in the list. So
int result = search(arr, N, x);
if(result == -1) the worst-case complexity is O(N) where N is the
printf("Element is not present in array"); size of the list.
else Average Case: O(N)
printf("Element is present at index %d", result);
return 0;
}
 Linear Searching

Advantages of Linear Search:

• Linear search can be used irrespective of whether the array is sorted or not. It can be used
on arrays of any data type.
• Does not require any additional memory.
• It is a well-suited algorithm for small datasets.

Drawbacks of Linear Search:

• Linear search has a time complexity of O(N), which in turn makes it slow for large datasets.
• Not suitable for large arrays.

When to use Linear Search?

• When we are dealing with a small dataset.
• When you are searching for a dataset stored in contiguous memory.

Time Complexity
Best Case O(1)
Average Case O(n)
Worst Case O(n)

Space Complexity O(1)

 Binary Search

•Binary Search is defined as a searching algorithm used in a sorted array by

repeatedly dividing the search interval in half.
 Binary Search

•Divide the search space into two halves by finding the middle index “mid”.

•Compare the middle element of the search space with the key.

•If the key is found at middle element, the process is terminated.

•If the key is not found at middle element, choose which half will be used as the next search space.

•If the key is smaller than the middle element, then the left side is used for next search.

•If the key is larger than the middle element, then the right side is used for next search.

•This process is continued until the key is found or the total search space is exhausted.
 Binary Search: Iterative Approach

#include <stdio.h> int main(void)

int binarySearch(int arr[], int l, int r, int x) {
{ int arr[] = { 2, 3, 4, 10, 40 };
while (l <= r) { int n = sizeof(arr) / sizeof(arr[0]);
int m = l + (r - l) / 2; int x = 4;
if (arr[m] == x) int result = binarySearch(arr, 0, n - 1, x);
return m; if(result == -1)
if (arr[m] < x) printf("Element is not present in array");
l = m + 1; else
else printf("Element is present at index %d", result);
r = m - 1; return 0;
} }
return -1;
}
 Binary Search: Recursive Approach

#include <stdio.h> int main()

int binarySearch(int arr[], int l, int r, int x) {
{ int arr[] = { 2, 3, 4, 10, 40 };
if (r >= l) { int n = sizeof(arr) / sizeof(arr[0]);
int mid = l + (r - l) / 2; int x = 10;
if (arr[mid] == x) int result = binarySearch(arr, 0, n - 1, x);
return mid; if(result == -1)
if (arr[mid] > x) printf("Element is not present in array");
return binarySearch(arr, l, mid - 1, x); else
return binarySearch(arr, mid + 1, r, x); printf("Element is present at index %d", result);
} return 0;
return -1; }
}
 Binary Search

Advantages of Binary Search:

• Binary search is faster than linear search, especially for large arrays.
• More efficient than other searching algorithms
• Binary search is well-suited for searching large datasets that are stored in external
memory, such as on a hard drive or in the cloud. Time Complexity
Best Case O(1)
Drawbacks of Binary Search: Average Case O(log n)
• The array should be sorted. Worst Case O(log n)
• Binary search requires that the data structure being searched be stored in contiguous
memory locations. Space Complexity O(1)

Applications of Binary Search:

• Binary search can be used as a building block for more complex algorithms used in
machine learning, such as algorithms for training neural networks or finding the
optimal hyperparameters for a model.
• It can be used for searching in computer graphics such as algorithms for ray tracing or
texture mapping.
• It can be used for searching a database.
 Time Complexity
• A data structure is the organization of the data in a way so that it can be used
efficiently.

• In order to use data efficiently, we have to store it efficiently.

• Efficiency of data structures is always measured in terms of TIME and SPACE.

• An ideal data structure could be the one that takes least possible time for all of its
operations and consumes the least memory space.

• We can compare the Time complexity on the basis of operations performed on

them.

24-02-2026 109
 Time Complexity
Inserting data at the start of array

24-02-2026 110
 Time Complexity
Inserting data at the start of linked list

24-02-2026 111
 Time Complexity

• Measuring the actual running time is not practical at all(input/machine

dependent)
• The running time generally depends on the size of the input.

24-02-2026 112
 Time Complexity

24-02-2026 113
 Cont…
Finding F(N)
 Cont…
Example:
 Cont…
Example:
 Cont…
Example:
 Cont…
Example:
 Cont…
Example:
 Asymptotic Notations
• The commonly used asymptotic notations used for
calculating the running time complexity of an
algorithm is given below:
• Big Oh Notation (O)
• Omega Notation (Ω)
• Theta Notation (θ)
 Big Oh Notation (O)
• Big Oh notation provides an upper bound on a
function which ensures that the function never
grows faster than the upper bound.
• gives the least upper bound on a function
• i.e. the function never grows faster than this
upper bound
• It is the formal way to express the upper boundary of
an algorithm running time.
• It measures the worst case of time complexity or the
algorithm's longest amount of time to complete its
operation.
 Table relating size of data set to amount of computations

24-02-2026 124
 Cont…
Example: Program to Calculate Sum of First N Natural Numbers
 Cont…
Example: Program to Calculate Sum of First N Natural Numbers
 Sorting

• Sorting
• Refers to arranging data in a particular format
• Sorting algorithm
• Specifies the way to arrange data in a particular order
• Importance of sorting lies
• Data searching can be optimized to a very high level, if data is stored in a
sorted manner
• Used to represent data in more readable formats
• Real-life scenarios
• Telephone Directory
• Dictionary
 In-place and Not-in-place Sorting

• Sorting algorithms may require some extra space for comparison and
temporary storage of few data elements

• In-place sorting
• do not require any extra space and sorting is said to happen in-
place
• for example, within the array itself
• Bubble sort, insertion sort, selection sort, quick sort, heap sort is an
example of in-place sorting

• Not-in-place sorting (Out place)

• Some sorting algorithms requires space which is more than or equal
to the elements being sorted
• Merge-sort is an example of not-in-place sorting
 In-place and Not-in-place Sorting

• Stable Sorting
• Sorting does not change
the sequence of similar
content in which they
appear (eg. Bubble sort,
insertion sort, merge
sort, etc.)

• Not Stable Sorting

• Sorting changes the
sequence of similar
content in which they
appear (eg selection
sort, quic sort, etc.)
 Adaptive and Non-adaptive Sorting

• Adaptive Sorting Algorithm

• Takes advantage of already 'sorted' elements in the list that is to be
sorted
• That is, while sorting if the source list has some element already
sorted, adaptive algorithms will take this into account and will try not
to re-order them
(eg. Insertion sort)
• Non-adaptive Sorting Algorithm
• A non-adaptive algorithm is one which does not take into account the
elements which are already sorted
• They try to force every single element to be re-ordered to confirm
their sorted behavior.
(eg. Selection sort)
 Adaptive and Non-adaptive Sorting
• Important Terms
• Increasing Order
• If the successive element is greater than the previous one. For example, 1,
3, 4, 6, 8, 9
• Decreasing Order
• If the successive element is less than the current one. For example, 9, 8, 6,
4, 3, 1
• Non-Increasing Order
• If the successive element is less than or equal to its previous element in
the sequence
• This order occurs when the sequence contains duplicate values. For
example, 9, 8, 6, 3, 3, 1
• Non-Decreasing Order
• If the successive element is greater than or equal to its previous element
in the sequence
• This order occurs when the sequence contains duplicate values. For
example, 1, 3, 3, 6, 8, 9
Sorting: Bubble sort
 Sorting: Bubble sort
#include <stdio.h> // Function to print the elements of an array
// Function to perform Bubble Sort on an array void printArray(int array[], int size)
void bubbleSort(int array[], int size) {
{ for (int i = 0; i < size; ++i)
for (int i = 0; i < size - 1; i++) {
{ printf("%d ", array[i]);
for (int j = 0; j < (size - 1 - i); j++) }
{ printf("\n");
if (array[j] > array[j + 1]) } int main()
{ {
// Swap array elements if they are in the wrong order int data[] = {-2, 45, 0, 11, -9};
int temp = array[j]; // Find the array's length
array[j] = array[j + 1]; int size = sizeof(data) / sizeof(data[0]);
array[j + 1] = temp;
} // Perform Bubble Sort on the array
} bubbleSort(data, size);
} Output:
} Sorted Array in Ascending Order: // Print the sorted array
-9 -2 0 11 45 printf("Sorted Array in Ascending Order:\n");
printArray(data, size);

return 0;
}
 Sorting: Bubble sort

• Comparison-based algorithm
• Works on the repeatedly swapping of adjacent elements until they are not in
the intended order.
• Called bubble sort
• The movement of array elements is just like the movement of air
bubbles in the water
• Average and worst case complexity are of Ο(n2) where n is the number of
items
• Not suitable for large data sets
• Used
• Complexity does not matter
• Simple and short code is preferred
 Sorting: Bubble sort

• Time Complexity
1. Best Case Complexity
• 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)
2. Average Case Complexity
• Occurs when the array elements are in jumbled order that is not
properly ascending and not properly descending
• Average case time complexity of bubble sort is O(n2)
3. Worst Case Complexity
• Occurs when the array elements are required to be sorted in reverse
order
• The worst-case time complexity of bubble sort is O(n2)
 Sorting: Selection Sort

Selection sort is a simple and efficient sorting algorithm that works by repeatedly
selecting the smallest (or largest) element from the unsorted portion of the list and
moving it to the sorted portion of the list.
Sorting: Selection Sort
Sorting: Selection Sort
 Sorting: Selection sort
#include <stdio.h> void printArr(int a[], int n) /* function to print the array */
void selection(int arr[], int n) {
{ int i;
int i, j, small; for (i = 0; i < n; i++)
for (i = 0; i < n-1; i++) printf("%d ", a[i]);
{ }
small = i;
for (j = i+1; j < n; j++) int main()
{ {
if (arr[j] < arr[small]) int a[] = { 31,12,0 , 25, 8, 32, 17 };
{ int n = sizeof(a) / sizeof(a[0]);
small = j; printf("Before sorting array elements are - \n");
} printArr(a, n);
} selection(a, n);
int temp = arr[small]; printf("\nAfter sorting array elements are - \n");
arr[small] = arr[i]; printArr(a, n);
arr[i] = temp; return 0;
} Output: }
}
Before sorting array elements are -
31 12 0 25 8 32 17
After sorting array elements are -
0 8 12 17 25 31 32
 Sorting: Selection sort

• Time Complexity
1. Best Case Complexity
• Occurs when there is no sorting required, i.e. the array is already sorted
• The algorithm still performs the full number of comparisons to confirm the
array is sorted, resulting in O(n²) time complexity
2. Average Case Complexity
• Occurs when the array elements are in jumbled order that is not properly
ascending and not properly descending
• On average, the number of comparisons remains the same, leading
to O(n²).
3. Worst Case Complexity
• Occurs when the array elements are required to be sorted in reverse order
• The maximum number of both comparisons and swaps, but the number of
comparisons is still bound by O(n²).
 Insertion Sort

• In-place comparison-based sorting algorithm

• Works similar to the sorting of Playing cards
• It is assumed that the first card is already sorted in the card game, and
then we select an unsorted card
• If the selected unsorted card is greater than the first card, it will be
placed at the right side; otherwise, it will be placed at the left side
• Similarly, all unsorted cards are taken and put in their exact place
 Insertion Sort

Algorithm
• 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
Insertion Sort
Insertion Sort
void insertionsort()
{
for (int i=1; i<n;i++)
{
int j=i-1;
int key=arr[i];
while(j>=0 && key<=arr[j])
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
}
 Insertion Sort

• Time Complexity
• Best Case Complexity
• Occurs when there is no sorting required, i.e. the array is already
sorted
• The best-case time complexity - O(n)
• Average Case Complexity
• Occurs when the array elements are in jumbled order that is not
properly ascending and not properly descending
• Average case time complexity - O(n2)
• Worst Case Complexity
• Occurs when the array elements are required to be sorted in reverse
order
• The worst-case time complexity - O(n2)
 Divide-and-Conquer

• Divide the problem into a number of sub-problems

• Similar sub-problems of smaller size

• Conquer the sub-problems

• Solve the sub-problems recursively

• Sub-problem size small enough  solve the problems in straightforward

manner

• Combine the solutions of the sub-problems

• Obtain the solution for the original problem

172
 Merge Sort

Here is the recursive mergesort algorithm:

• If the list has only one element, return the list
and terminate. (Base case)
To sort an array A[p . . r]:
• Divide
• Divide the n-element sequence to be
sorted into two subsequences of n/2
elements each
• Conquer
• Sort the subsequences recursively using
merge sort
• When the size of the sequences is 1 there is
nothing more to do
• Combine
• Merge the two sorted subsequences
 Merge Sort

1 2 3 4 5 6 7 8

Divide 5 2 4 7 1 3 2 6 q=4

1 2 3 4 5 6 7 8

5 2 4 7 1 3 2 6

1 2 3 4 5 6 7 8

5 2 4 7 1 3 2 6

1 2 3 4 5 6 7 8

5 2 4 7 1 3 2 6

174
 Merge Sort

1 2 3 4 5 6 7 8

Conquer 1 2 2 3 4 5 6 7
and
Merge 1 2 3 4 5 6 7 8

2 4 5 7 1 2 3 6

1 2 3 4 5 6 7 8

2 5 4 7 1 3 2 6

1 2 3 4 5 6 7 8

5 2 4 7 1 3 2 6

175
 Merge Sort

p q r
1 2 3 4 5 6 7 8

Alg.: MERGE-SORT(A, p, r) 5 2 4 7 1 3 2 6

if p < r Check for base case

then q ← (p + r)/2 Divide

MERGE-SORT(A, p, q) Conquer

MERGE-SORT(A, q + 1, r) Conquer

MERGE(A, p, q, r) Combine

• Initial call: MERGE-SORT(A, 1, n)

176
 Merging

p q r
1 2 3 4 5 6 7 8

2 4 5 7 1 2 3 6

• Input: Array A and indices p, q, r such that p≤q<r

• Subarrays A[p . . q] and A[q + 1 . . r] are sorted
• Output: One single sorted subarray A[p . . r]

177
 Merging

p q r
• Idea for merging: 1 2 3 4 5 6 7 8

• Two piles of sorted cards 2 4 5 7 1 2 3 6

• Choose the smaller of the two top cards

• Remove it and place it in the output pile
• Repeat the process until one pile is empty
• Take the remaining input pile and place it face-down onto the
output pile

A1 A[p, q]
A[p, r]

A2 A[q+1, r]

178
Example: MERGE(A, 9, 12, 16)
p q r

179
Example: MERGE(A, 9, 12, 16)

180
Example (cont.)

181
Example (cont.)

182
Example (cont.)

Done!

183
 Merge - Pseudocode

Alg.: MERGE(A, p, q, r) p q r
1. Compute n1 and n2
1 2 3 4 5 6 7 8

2 4 5 7 1 2 3 6
2. Copy the first n1 elements into
L[1 . . n1 + 1] and the next n2 elements into R[1 . . n2 + 1] n1 n2
1. L[n1 + 1] ← ; R[n2 + 1] ← 
2. i ← 1; j←1 p q

3. for k ← p to r L 2 4 5 7 
4. do if L[ i ] ≤ R[ j ] q+1 r

5. then A[k] ← L[ i ] R 1 2 3 6 
6. i ←i + 1
7. else A[k] ← R[ j ]
8. j←j+1
184
 Merge Sort
void merge(int arr[], int l, int m, int r){ while (i < n1 && j < n2) {
int i, j, k; if (L[i] <= R[j]) { // Copy the remaining elements of
int n1 = m - l + 1; arr[k] = L[i]; R[], if there are any
int n2 = r - m; i++; while (j < n2) {
} arr[k] = R[j];
// Create left & right array else { j++;
int L[n1], R[n2]; arr[k] = R[j]; k++;
j++; }
// Copy data to L[] and R[] } }
for (i = 0; i < n1; i++) k++;
L[i] = arr[l + i]; }
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j]; // Copy the remaining elements
of L[], if there are any
// Merge array L and R back into while (i < n1) {
arr[l..r] arr[k] = L[i];
i = 0; i++;
j = 0; k++;
k = l; }
 Merge Sort

• Time Complexity
• Best Case Complexity
• Occurs when array is already sorted
• Best-case time complexity - O(n*log n)
• Average Case Complexity
• Occurs when the array elements are in jumbled
order
• Average case time complexity - O(n*log n)
• Worst Case Complexity
• Occurs when the array elements are required to be
sorted in reverse order.
• Worst-case time complexity - O(n*log n)
 Quicksort

• Quicksort is a faster and highly efficient sorting algorithm

• Follows the divide and conquer approach
• Quicksort picks an element as pivot, and then it partitions the given array
around the picked pivot element
• Divides a large array into two arrays
• one array holds values that are smaller than or equal to the
specified value (Pivot):left array
• another array holds the values that are greater than the pivot:
Right array
• Left & right sub-arrays are then partitioned using same approach
• It will continue until single element remains in the sub-array
• Combine the already sorted array
 Quicksort

• Choosing the pivot

• Pivot can be random, i.e. select the random pivot from
the given array
• Pivot can either be the rightmost element of the
leftmost element of the given array
• Select median as the pivot element
 Quick Sort

< 28 <

< 15 < < 47 <

1. Pick a “pivot”
2. Divide into less-than & greater-than pivot
3. Sort each side recursively
 The steps of QuickSort

S 81 31 57 select pivot value

43
13 75
92 0
65 26

S1 S2 partition S
0 31 75
43 65
13 81
92
26 57

QuickSort(S1) and
S1 S2 QuickSort(S2)
0 13 26 31 43 57 65 75 81 92

S 0 13 26 31 43 57 65 75 81 92 Presto! S is sorted
[Weiss]
 The steps of QuickSort
QuickSort Example
i j

5 1 3 9 7 0 4 2 6 8

i j

5 1 3 9 7 0 4 2 6 8

i j

5 1 3 9 7 0 4 2 6 8

i j

5 1 3 2 7 0 4 9 6 8

•Move i to the right to be larger than pivot.

•Move j to the left to be smaller than pivot.
•Swap
 i j

5 1 3 2 7 0 4 9 6 8

i j

5 1 3 2 7 0 4 9 6 8

i j

5 1 3 2 4 0 7 9 6 8

i j

5 1 3 2 4 0 7 9 6 8

j i

5 1 3 2 4 0 7 9 6 8

j i

0 1 4 2 4 5 6 9 7 8

S1 < pivot pivot S2 > pivot

 Quicksort

• Algorithm for Quick Sort

• Step 1: Choose the lowest index value as pivot.
• Step 2: Take two variables to point left and right of the
list excluding pivot.
• Step 3: Left points to the low index.
• Step 4: Right points to the high index.
• Step 5: While value at left < pivot move right.
• Step 6: While value at right > pivot move left.
• Step 7: If both Step 5 and Step 6 does not match, swap
left and right.
• Step 8: If left <= right, the point where they met is new
pivot.
 Quicksort function

void quickSort(int arr[], int low, int high)

{
if (low < high)
{
int p = partition(arr, low, high);
quickSort(arr, low, p - 1);
quickSort(arr, p + 1, high);
}
}
 Quicksort

// Lomuto Partition function (first element as

pivot) // Place pivot at correct position
int partition(int arr[], int low, int high) swap(&arr[low], &arr[j]);
{ return j;
int pivot = arr[low]; }
int i = low + 1;
int j = high;

while (i <= j)
{
while (i <= high && arr[i] <= pivot)
i++;

while (arr[j] > pivot)

j--;

if (i < j)
swap(&arr[i], &arr[j]);
}
 The steps of QuickSort

Quick sort:
• pick a pivot value from the array
• partition the list around the pivot value
• sort the left half
• sort the right half

Merge sort:
• divide a list into two identically sized halves
• sort the left half
• sort the right half
• recombine the sorted halves into a sorted whole
 Quick Sort

• Time Complexity
• Best & Average Case Complexity
• Occurs when the pivot consistently divides the array
into roughly equal halves.
• Best-case time complexity - O(n*log n)
• Worst Case Complexity
• Happens with already sorted/reverse-sorted data or
poor pivot selection (like always picking the
smallest/largest element), creating highly
unbalanced partitions .
• Worst-case time complexity - O(n2)
24-02-2026 201