2323007

PRACTICAL
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 NAGMA
2323007

UNDER THE SUPERVISION OF:

Er. Anjali Thakur
Assistant Professor AIML Department, ACE

Department of Artificial Intelligence and Machine Learning

Ambala College of Engineering and Applied Research, Devsthali, Ambala
(Haryana)
2323007

PRACTICAL - 1
Aim: Write a program to find the factorial of a number.
Software used: CodeBlocks.
Description: This program calculates the factorial of a non-negative integer nnn by
multiplying all integers from 1 up to nnn. It uses a loop to perform this multiplication. If the user
enters a negative number, the program outputs a message that factorials are not defined for
negative numbers.

Source Code:
#include <stdio.h>
int factorial(int n)
{
if (n < 0)
return -1; // Return -1 to indicate an error for negative numbers
unsigned long long result = 1;
for (int i = 1; i <= n; ++i)
{
result *= i;
}
return result;
}
int main()
{
int number;
printf("Enter a number: ");
scanf("%d", &number);
if (number < 0)
printf("Factorial does not exist for negative numbers.\n");
else
printf("Factorial of %d is %llu\n", number, factorial(number));
return 0;
}
2323007

Output:
2323007

PRACTICAL - 2
Aim: Write a program to check the number is prime or not.
Description: A prime number is a natural number greater than 1 that has no divisors other
than 1 and itself. This program checks if a given number is prime by iterating from 2 to the
square root of the number and checking for any divisors.
Software Used: CodeBlocks.
Source Code:
#include<stdio.h>
int isPrime(int n)
{
if (n <= 1)
return 0; // Numbers less than or equal to 1 are not prime
for (int i = 2; i <= n / 2; i++)
{
if (n % i == 0)
return 0; // If divisible by any number other than 1 and itself, it's not prime
}
return 1; // No divisors found, so it's prime
}
int main()
{
int number;
printf("Enter a number: ");
scanf("%d", &number); if (isPrime(number))
printf("%d is a prime number.\n", number);
else
printf("%d is not a prime number.\n", number);
return 0;
}

Output:
2323007

PRACTICAL - 3
Aim: To find the given element in an array using LinearSearch.
Description: In linear search, each element of the array is sequentially checked until the
desired element is found or the end of the array is reached. This program takes an array and a
target number as input, then searches for the target in the array.
Software Used: CodeBlocks
Source Code:
#include <stdio.h>
int linearSearch(int arr[], int size, int target)
{
for (int i = 0; i < size; i++)
{
if (arr[i] == target)
return i; // Return the index if target is found
}
return -1; // Return -1 if target is not found
}
int main()
{
int n, target;
printf("Enter the number of elements in the array: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter the number to search for: ");
scanf("%d", &target);
int result = linearSearch(arr, n, target);
if (result != -1)
printf("Number %d found at index %d.\n", target, result);
else
printf("Number %d not found in the array.\n", target);
return 0;
}
2323007

Output:
2323007

PRACTICAL - 4
Aim: Write a program to find the element in the array using BinarySearch .
Description: Binary search is a fast search algorithm that works only on sorted arrays. The
array is divided in half repeatedly, comparing the target with the middle element each time. If the
middle element is not the target, the algorithm discards the half where the target cannot be
located, making the search more efficient.
Software Used: CodeBlocks
Source Code:
#include <stdio.h>
int binarySearch(int arr[], int size, int target)
{
int left = 0, right = size - 1;
while (left <= right)
{
int mid = left + (right - left) / 2; // Check if the target is at the middle
if (arr[mid] == target)
return mid;
// If the target is greater, ignore the left half
if (arr[mid] < target)
left = mid + 1;
else // If the target is smaller, ignore the right half
right = mid - 1;
}
return -1; // Target not found
}
int main()
{
int n, target;
printf("Enter the number of elements in the sorted array: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d sorted elements:\n", n);
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter the number to search for: ");
scanf("%d", &target);
int result = binarySearch(arr, n, target);
if (result != -1)
printf("Number %d found at index %d.\n", target, result);
else
2323007

{
printf("Number %d not found in the array.\n", target);
return 0;
}

Output:
2323007

PRACTICAL - 5
Aim: Write a program for insertion sort, selection sort and bubble sort .
Description:
• Insertion Sort:
In Insertion Sort, elements are picked from an unsorted part and placed in the
correct position in the sorted part.
• Selection Sort:
In Selection Sort, the array is divided into a sorted and an unsorted part. The
minimum element from the unsorted part is selected and swapped with the first
element of the unsorted part.
• Bubble Sort:
In Bubble Sort, adjacent elements are repeatedly swapped if they are in the wrong
order, and this process is repeated for every element.

Software Used: CodeBlocks.

Source Code:

Insertion Sort:-
#include <stdio.h>
void insertionSort(int arr[], int n)
{
for (int i = 1; i < n; i++)
{
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
2323007

int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("Sorted array using Insertion Sort: ");
printArray(arr, n);
return 0;
}

Output:

Selection Sort:-
#include <stdio.h>
void selectionSort(int arr[], int n)
{
for (int i = 0; i < n - 1; i++)
{
int minIdx = i;
for (int j = i + 1; j < n; j++)
{
if (arr[j] < arr[minIdx])
minIdx = j;
}
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
2323007

}
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array using Selection Sort: ");
printArray(arr, n);
return 0;
}

Output:
2323007

Bubble Sort:
#include <stdio.h>
void bubbleSort(int arr[], int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array using Bubble Sort: ");
printArray(arr, n);
return 0;
}
2323007

Output:
2323007

PRACTICAL - 6
Aim:- Write a program to implement Stack and its operation.
Description:- A stack is a linear data structure that follows the LIFO (Last In First Out)
principle. The program implements the stack using an array and supports the following
operations:
• Push: Add an element to the top of the stack.
• Pop: Remove an element from the top of the stack.
• Display: Show all the elements of the stack.
Software Used: CodeBlocks.
Source Code:
#include <stdio.h>
#define MAX 100
int stack[MAX];
int top = -1;
void Push(int a)
{
if (top == MAX)
{
printf("Stack is overflow\n");
}
else
{
top++;
stack[top] = a;
printf("Element added\n");
}
}
void display()
{
if (top == -1)
{
printf("Stack is empty\n");
}
else
{
printf("Stack elements:\n");
for (int i = top; i >= 0; i--)
{
printf("%d\n", stack[i]);
}
}
}
2323007

int pop()
{
if (top == -1)
{
printf("Stack underflow\n");
return -1;
}
else
{
int popped_element = stack[top];
top--;
return popped_element;
}
}
int main()
{
Push(10);
Push(20);
Push(30);
pop();
display();
return 0;
}

Output:
2323007

PRACTICAL - 7
Aim: -Write a program for quick sort.
Description: - Quick Sort is a divide-and-conquer sorting algorithm. It selects a pivot,
partitions the array into elements smaller and larger than the pivot, and recursively sorts the
subarrays. It is efficient, with an average time complexity of O(nlog n)
Software used: - CodeBlocks
Source code: -
#include <stdio.h>
// Function to partition the array
int partition(int arr[], int low, int high)
{
int pivot = arr[high]; // Choose the last element as pivot
int i = low - 1;
for (int j = low; j < high; j++)
{
if (arr[j] < pivot)
{
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Place pivot in its correct position
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}

// Quick Sort function

void quickSort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);

// Recursively sort elements before and after partition

quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

// Function to print the array

2323007

void printArray(int arr[], int size)

{
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Unsorted array: ");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}

Output: -
2323007

PRACTICAL - 8
Aim: Write a program for merge sort.
Description: - Merge Sort is a divide-and-conquer sorting algorithm. It splits the array into
halves, recursively sorts them, and merges the sorted halves into a single sorted array. It has a
time complexity of O(n log n)

Software used: - CodeBlocks

Source code: -
#include <stdio.h>
// Merge two subarrays
void merge(int arr[], int left, int mid, int right)
{
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays
int L[n1], R[n2];
// Copy data to temporary arrays
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// Merge the temporary arrays
int i = 0, j = 0, k = left;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

// Copy remaining elements of L[], if any

while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
2323007

// Copy remaining elements of R[], if any

while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Merge Sort function
void mergeSort(int arr[], int left, int right)
{
if (left < right)
{
int mid = left + (right - left) / 2;

// Recursively sort first and second halves

mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);

// Merge the sorted halves

merge(arr, left, mid, right);
}
}
// Function to print the array
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Unsorted array: ");
printArray(arr, n);
mergeSort(arr, 0, n - 1);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
2323007

Output: -