BCA – 205 Data structure 1323572

1.)Write a program for using Dynamic Functions (malloc(), calloc(), realloc() and free()) functions.
#include <stdio.h>
#include <stdlib.h>
int main() {
int *arr;
int size, choice, i;
printf("Enter the size of the array: ");
scanf("%d", &size);
// Dynamically allocating memory for the array using malloc()
arr = (int *)malloc(size * sizeof(int));
if (arr == NULL) {
printf("Memory allocation failed. Exiting...\n");
return 1;
}
// Inputting elements into the array
printf("Enter %d elements:\n", size);
for (i = 0; i < size; i++) {
scanf("%d", &arr[i]);
}
// Performing operations on the array
printf("\nOperations Menu:\n");
printf("1. Print the array\n");
printf("2. Double each element of the array\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
// Printing the array
printf("The array is: ");
for (i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
break;
case 2:
// Doubling each element of the array
for (i = 0; i < size; i++) {
arr[i] *= 2;
}
printf("Array elements doubled successfully.\n");
break;
default:
printf("Invalid choice!\n");
}
// Freeing dynamically allocated memory using free()
free(arr);
return 0;
}
BCA – 205 Data structure 1323572
BCA – 205 Data structure 1323572

2.) Write a program to insert, delete and traverse an element in an array.

#include <stdio.h>
#define MAX_SIZE 100
// Function to insert an element into the array at a given position
int insertElement(int arr[], int *size, int element, int position) {
if (*size >= MAX_SIZE || position < 0 || position > *size) {
return 0; // Insertion failed
}
// Shift elements to the right to make space for the new element
for (int i = *size; i > position; i--) {
arr[i] = arr[i - 1];
}
// Insert the new element
arr[position] = element;
(*size)++; // Increase the size of the array
return 1; // Insertion successful
}
// Function to delete an element from the array at a given position
int deleteElement(int arr[], int *size, int position) {
if (position < 0 || position >= *size) {
return 0; // Deletion failed
}
// Shift elements to the left to fill the gap
for (int i = position; i < *size - 1; i++) {
arr[i] = arr[i + 1];
}
(*size)--; // Decrease the size of the array
return 1; // Deletion successful
}
// Function to traverse and print all elements of the array
void traverseArray(int arr[], int size) {
printf("Array elements: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[MAX_SIZE];
int size = 0;
int choice, element, position;
while (1) {
BCA – 205 Data structure 1323572

printf("\nArray Operations Menu:\n");

printf("1. Insert an element\n");
printf("2. Delete an element\n");
printf("3. Traverse the array\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter the element to insert: ");
scanf("%d", &element);
printf("Enter the position to insert: ");
scanf("%d", &position);
if (insertElement(arr, &size, element, position)) {
printf("Element inserted successfully.\n");
} else {
printf("Failed to insert element. Invalid position or array full.\n");
}
break;
case 2:
printf("Enter the position to delete: ");
scanf("%d", &position);
if (deleteElement(arr, &size, position)) {
printf("Element deleted successfully.\n");
} else {
printf("Failed to delete element. Invalid position.\n");
}
break;
case 3:
traverseArray(arr, size);
break;
case 4:
printf("Exiting program.\n");
return 0;
default:
printf("Invalid choice! Please enter a number between 1 and 4.\n");
}
}
return 0;
}
BCA – 205 Data structure 1323572
BCA – 205 Data structure 1323572

3) Write a program to implement linear search.

#include <stdio.h>
// Function to perform linear search
int linearSearch(int arr[], int size, int key) {
for (int i = 0; i < size; i++) {
if (arr[i] == key) {
return i; // Return the index of the key if found
}
}
return -1; // Return -1 if key is not found
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70};
int size = sizeof(arr) / sizeof(arr[0]);
int key, index;
printf("Enter the element to search: ");
scanf("%d", &key);
index = linearSearch(arr, size, key);

if (index != -1) {
printf("Element found at index: %d\n", index);
} else {
printf("Element not found in the array.\n");
}
return 0;
}
BCA – 205 Data structure 1323572

4) Write a program to implement Binary search.

#include <stdio.h>
// Function to perform binary search
int binarySearch(int arr[], int size, int key) {
int left = 0;
int right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// If the key is present at the middle
if (arr[mid] == key) {
return mid;
}
// If the key is smaller, ignore the right half
else if (arr[mid] > key) {
right = mid - 1;
}
// If the key is larger, ignore the left half
else {
left = mid + 1;
}
}
// Key not found
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70};
int size = sizeof(arr) / sizeof(arr[0]);
int key, index;
printf("Enter the element to search: ");
scanf("%d", &key);
index = binarySearch(arr, size, key);
if (index != -1) {
printf("Element found at index: %d\n", index);
} else {
printf("Element not found in the array.\n");
}
return 0;
}
BCA – 205 Data structure 1323572
BCA – 205 Data structure 1323572

5) Write a program to implement selection sort.

#include <stdio.h>
// Function to perform selection sort
void selectionSort(int arr[], int size) {
int i, j, min_index;
// Traverse through the array
for (i = 0; i < size - 1; i++) {
// Find the minimum element in the unsorted part of the array
min_index = i;
for (j = i + 1; j < size; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}
// Function to print the array
void printArray(int arr[], int size) {
printf("Sorted array: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
selectionSort(arr, size);
printArray(arr, size);
return 0;
}
BCA – 205 Data structure 1323572
BCA – 205 Data structure 1323572

6) Write a program to implement insertion sort.

#include <stdio.h>
// Function to perform insertion sort
void insertionSort(int arr[], int size) {
int i, j, key;
for (i = 1; i < size; i++) {
key = arr[i];
j = i - 1;
// Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current
position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// Function to print the array
void printArray(int arr[], int size) {
printf("Sorted array: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
insertionSort(arr, size);
printArray(arr, size);
return 0;
}
BCA – 205 Data structure 1323572
BCA – 205 Data structure 1323572

7) Write a program to implement quick sort.

#include <stdio.h>

// Function to partition the array and return the pivot index

int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choosing the last element as the pivot
int i = (low - 1); // Index of smaller element

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

// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++; // Increment index of smaller element
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap arr[i + 1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;

return (i + 1);
}

// Function to implement Quick Sort

void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi is partitioning index, arr[pi] is now at right place
int pi = partition(arr, low, high);

// Separately sort elements before partition and after partition

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

// Function to print the array

void printArray(int arr[], int size) {
printf("Sorted array: ");
for (int i = 0; i < size; i++) {
BCA – 205 Data structure 1323572

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

}
printf("\n");
}

int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int size = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");

quickSort(arr, 0, size - 1);

printArray(arr, size);

return 0;
}
BCA – 205 Data structure 1323572

8) Write a program to implement merge sort.

#include <stdio.h>

// Merge two subarrays of arr[]

// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

// Create temporary arrays

int L[n1], R[n2];

// Copy data to temporary arrays L[] and R[]

for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

// Merge the temporary arrays back into arr[l..r]

i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}

// Copy the remaining elements of L[], if there are any

while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
BCA – 205 Data structure 1323572

// Copy the remaining elements of R[], if there are any

while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

// l is for left index and r is right index of the sub-array of arr to be sorted
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// Same as (l+r)/2, but avoids overflow for large l and r
int m = l + (r - l) / 2;

// Sort first and second halves

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

// Merge the sorted halves

merge(arr, l, m, r);
}
}

// Function to print the array

void printArray(int arr[], int size) {
printf("Sorted array: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int size = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
BCA – 205 Data structure 1323572

mergeSort(arr, 0, size - 1);

printArray(arr, size);

return 0;
}