2323007

PRACTICAL FILE
of
“DATA STRUCTURE LAB”
SUBJECT CODE: PC-CS-AIML-213LA

SUBMITTED IN PARTIAL FULFILLMENT OF THE

REQUIREMENTS FOR THE AWARD OF
BACHELORS OF TECHNOLOGY (B.TECH.)
IN
Artificial Intelligence and Machine Learning

(SESSION: 2023-27)

SUBMITTED BY:
Ayesha
2323007

BRANCH - Artificial Intelligence and Machine Learning

UNDER THE SUPERVISION OF:

Er. Anjali Thakur
Assistant Professor
AIML Department, ACE

Department of Computer Science and Engineering

 2323007

Ambala College of Engineering and Applied Research, Devsthali, Ambala

(Haryana)Affiliated to Kurukshetra University, Kurukshetra

INDEX

S.NO PRACTICAL AIM DATE SIGNATURE

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.
 2323007

PRACTICAL-1
AIM: Search an element in an array using binary search methods.
SOFTWARE USED: vs code.
PROCEDURE:
LINEAR SEARCH:
1. [Enter the size of the array]
2. [Enter the elements of the array using for loop]
3. [Enter element you want of search] n =?.
4. Repeat for loop while arr[i] != n.
5. [End of the loop]
6. When arr[i] == n. Print Index of that Element.
BINARY SEARCH:

: Beg = LB, End = UB, mid = Int({Beg + End} / 2).

1. Repeat step 3 and step 4 while Beg <= End and arr[mid] != Item.
2. If Item < arr[mid]
set End = mid – 1
else
set Beg = mid + 1.
[End of the Structure]

SOURCE CODE:
Binary search:
#include<stdio.h>
int main ()
{
int i,value,n,mid;
int lower=0,upper=n;
int flag=0;
printf("enter elements of array:");
scanf("%d",&n);
int A[n];
for(i=1;i<=n;i++)
{
scanf("%d",&A[i]);
}
 2323007

printf("enter the value to research:");

scanf("%d",&value);
while(lower<=upper)
{
mid=(lower+upper)/2;
if(A[mid]==value)
{
flag=1;
break;
}
if(A[mid]>value)
{
upper=mid+1;
}
else
{
lower=mid-1;
}
}
if(flag==1)
{
printf("element is located at %d",mid);
}
else
{
printf("element is not found");
}
}
 2323007

Linear search:

OUTPUT:
Linear search:

Binary search:
 2323007

PRACTICAL-2
AIM: Sorting an array using Switch case (insertion sort, selection sort, bubble sort).
THEORY: Bubble Sort, Selection Sort, and Insertion Sort are simple sorting algorithms
that are commonly used to sort small datasets or as building blocks for more complex
sorting algorithms.
Bubble Sort:
1. Time complexity: O(n^2) in the worst and average cases, O(n) in the best case
(when the input array is already sorted)
Space complexity: O(1)
2. Basic idea: Iterate through the array repeatedly, comparing adjacent pairs of
elements and swapping them if they are in the wrong order. Repeat until the
array is fully sorted.
Selection Sort:
1. Time complexity: O(n^2) in all cases (worst, average, and best)
Space complexity: O(1)
2. Basic idea: Find the minimum element in the unsorted portion of the array and
swap it with the first unsorted element. Repeat until the array is fully sorted.
Insertion Sort:
1. Time complexity: O(n^2) in the worst and average cases, O(n) in the best case
(when the input array is already sorted)
Space complexity: O(1)
2. Basic idea: Build up a sorted subarray from left to right by inserting each new
element into its correct position in the subarray. Repeat until the array is fully
sorted.

SOURCE CODE:
#include <stdio.h>

// Function to perform Insertion Sort

void insertionSort(int arr[], int n) {
int i, j, key;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

// Function to perform Bubble Sort

void bubbleSort(int arr[], int n) {
int temp, swapped;
 2323007

do {
swapped = 0;
for (int i = 1; i < n; i++) {
if (arr[i - 1] > arr[i]) {
temp = arr[i - 1];
arr[i - 1] = arr[i];
arr[i] = temp;
swapped = 1;
}
}
} while (swapped);
}

// Function to perform Selection Sort

void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}

int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter the elements: ");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
int choice;
printf("Choose a sorting algorithm (1-Insertion, 2-Bubble, 3-Selection): ");
scanf("%d", &choice);
switch (choice) {
case 1:
insertionSort(arr, n);
printf("Sorted array using Insertion Sort: ");
break;
case 2:
bubbleSort(arr, n);
 2323007

printf("Sorted array using Bubble Sort: ");

break;
case 3:
selectionSort(arr, n);
printf("Sorted array using Selection Sort: ");
break;
default:
printf("Invalid choice. Exiting.\n");
return 1;
}

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

printf("%d ", arr[i]);
}

return 0;
}

OUTPUT:
 2323007

PRACTICAL-3
AIM: Write a program to check if a number is prime or not.
SOFTWARE USED: vs code.
PROCEDURE:
1. Start.
2. Input the number nnn.
3. If n<2n < 2n<2, return "Not Prime" and End.
4. For each number iii from 2 to n\sqrt{n}n (inclusive):
5. If n%i==0n \% i == 0n%i==0, return "Not Prime" and End.
6. If no divisors were found, return "Prime".
7. End.

SOURCE CODE:
#include <stdio.h>
#include <math.h>
int is_prime(int number) {
if (number < 2) {
return 0;
}
for (int i = 2; i <= sqrt(number); i++) {
if (number % i == 0) {
return 0;
}
}
return 1;
}
int main() {
int num;
printf("Enter a number: ");
scanf("%d", &num);
if (is_prime(num)) {
printf("%d is a prime number.\n", num);
} else {
 2323007

printf("%d is not a prime number.\n", num);

}
return 0;
}

OUTPUT:
 2323007

PRACTICAL-4
AIM: Write a program to check the factorial of a program.
SOFTWARE USED: vs code.
PROCEDURE:
1. Start.
2. Input the number n.
3. If n is less than 0, print "Factorial is not defined for negative numbers" and End.
4. Initialize fact = 1.
5. For each i from 1 to n (inclusive):
6. Multiply fact = fact * i.
7. After the loop, print fact as the factorial of n.
8. End.

SOURCE CODE:
#include <stdio.h>
int main() {
int num, i;
unsigned long long factorial = 1;
printf("Enter a number: ");
scanf("%d", &num);
if (num < 0) {
printf("Factorial is not defined for negative numbers.\n");
}
else {
for (i = 1; i <= num; ++i) {
factorial *= i;
}
printf("Factorial of %d = %llu\n", num, factorial);
}
return 0;
}

OUTPUT:
2323007
 2323007

PRACTICAL-5
AIM: Write a program to implement Stack and its operations.
SOFTWARE USED: Code Blocks.
THEORY: A Stack is a linear data structure that follows the LIFO (Last-In-First-Out)
principle. Stack has one end, whereas the Queue has two ends (front and rear). It contains
only one pointer top pointer pointing to the topmost element of the stack. Whenever an
element is added in the stack, it is added on the top of the stack, and the element can be
deleted only from the stack. In other words, a stack can be defined as a container in which
insertion and deletion can be done from the one end known as the top of the stack.
• Push: When we insert an element in a stack then the operation is known as a push. If the
stack is full then the overflow condition occurs.
• Pop: When we delete an element from the stack, the operation is known as a pop. If the
stack is empty means that no element exists in the stack, this state is known as an underflow
state.

SOURCE CODE:
//Pushing and popping an element into Stack
#include<stdio.h>
void push
{
int a[6]={10,20,30,40,50}; int len=6, item-60; int MAXSTK=len-1,Top=4;
if(T op=MAXSTK)
{
printf("Stack overflow');
}
else
{
Top-Top+1; a[Top]-item;
printi"Stack after pushing: ");
for(int i-O;i<=Top;i++)
{
printf"%dIn", ai]);
｝
｝
 2323007

void pop()
{
int a[6]={10,20,30,40,50,60};
int len =6,item; int
MAXSTK=len-1, Top=5;
і(Тор =0)
{
printf("Stack underflow');
}
else
{
item=a[Top];
Top-Top-1;
printf("Stack after popping: "); for(int i=0;i<-Top;i++)
{
printf("%dn", a[il);
}
}
}
int main
{
int choice;
printf("Enter 1 for pushing and 2 for popping: ");
scanf("%d", &choice);
switch(choice)
{
case 1:push;
break;
case, 2:pop;
break;
}
 2323007

OUTPUT:
 2323007

PRACTICAL-6
AIM: Write a program for Quick Sort.
SOFTWARE USED: CodeBlocks.

THEORY: Quick sort is a highly efficient sorting algorithm and is based on partitioning of
array of data into smaller arrays. A large array is partitioned into two arrays one of which
holds values smaller than the specified value, say pivot, based on which the partition is made
and another array holds values greater than the pivot value.

Quicksort partitions an array and then calls itself recursively twice to sort the two resulting
subarrays. This algorithm is quite efficient for large-sized data sets as its average and worst-
case complexity are O(n2), respectively.

SOURCE CODE:

#include<stdio.h>

void swap(int* a,int* b)

int t = *a;

*a = *b;

*b = t;

int partition(int arr[],int low,int high)

int x=arr[high];

int i=(low-1);

for(int j=low;j<=high-1;j++)

if(arr[j]<x)

i++;

swap(&arr[i],&arr[j]);
 2323007

swap(&arr[i+1],&arr[high]);

return (i+1);

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

if(low<high)

int pi=partition(arr,low,high);

quickSort(arr,low,pi-1);

quickSort(arr,pi+1,high);

void printArray(int arr[],int size)

int i;

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

printf("%d",arr[i]);

printf("\n");

int main()

{
 2323007

int arr[]={11,19,6,65,1,25};

int n = sizeof(arr) / sizeof(arr[0]);

quickSort(arr,0,n-1);

printf("Sorted array:\n");

printArray(arr,n);

return 0;

OUTPUT:
 2323007

PRACTICAL-7
AIM: Write a program for Merge Sort.
SOFTWARE USED: CodeBlocks.
THEORY: Merge Sort is one of the most efficient sorting algorithms. It is based on the
divide and conquer strategy. Merge sort continuously cuts down a list into multiple sublists
until each has only one item, then merges those sublists into a sorted list.

SOURCE CODE:
#include<stdio.h>
void merge(int arr[],int p,int q,int r)
{
int i,j,k;
int n1=q-p+1;
int n2=r-q;
int L[n1], R[n2];
for(i=0;i<n1;i++)
L[i]=arr[p+i];
for(j=0;j<n2;j++)
R[j]=arr[q+1+j];
i=0;
j=0;
k=p;
while(i<n1 && j<n2)
{
if(L[i]<=R[j])
{
arr[k]=L[i];
i++;
}
else
{
arr[k]=R[j];
 2323007

j++;
}
k++;
}
while(i<n1)
{
arr[k]=L[i];
i++;
k++;
}
while(j<n2)
{
arr[k]=R[j];
j++;
k++;
}
}
void mergeSort(int arr[],int p,int r)
{
if(p<r)
{
int q=p+(r-p)/2;
mergeSort(arr,p,q);
mergeSort(arr,q+1,r);
merge(arr,p,q,r);
}
}
void printArray(int A[],int size)
{
int i;
for(i=0;i<size;i++)
 2323007

printf("%d ",A[i]);
printf("\n");
}
int main()
{
int arr[]={12, 11, 13, 5, 6, 7 };
int arr_size=sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}

Output:
2323007