1.
Aim: write a C program to implement bubble sort technique
Program analysis:
This program defines a function bubble Sort to sort an array of integers using the bubble sort algorithm. It
then sorts an example array in the main function and prints the array before and after sorting.
Program:
#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;
}
}
}
}
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Array before sorting:\n");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
bubbleSort(arr, n);
printf("Array after sorting:\n");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Output:
Array before sorting:
64 34 25 12 22 11 90
Array after sorting:
11 12 22 25 34 64 90
2. Aim: write a C program to implement quick sort technique
Program analysis:
This program defines functions swap, partition, and quickSort to implement the quicksort algorithm. It then
sorts an example array in the main function and prints the array before and after sorting.
Program
#include <stdio.h>
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++)
{
if (arr[j] < pivot)
{
i++;
swap(&arr[i], &arr[j]);
}
}
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);
}
}
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Array before sorting:\n");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
quickSort(arr, 0, n - 1);
printf("Array after sorting:\n");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Output:
Array before sorting:
10 7 8 9 1 5
Array after sorting:
1 5 7 8 9 10
3. Aim: Write a C program to implement Merge sort technique
Program analysis:
This program defines functions merge and mergeSort to implement the merge sort algorithm. It then sorts
an example array in the main function and prints the array before and after sorting.
Program
#include <stdio.h>
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
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 l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Array before sorting:\n");
for (int i = 0; i < arr_size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
mergeSort(arr, 0, arr_size - 1);
printf("Array after sorting:\n");
for (int i = 0; i < arr_size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Output:
Array before sorting:
12 11 13 5 6 7
Array after sorting:
5 6 7 11 12 13
4. Aim: Write a C program to implement Linear Search
Program analysis:
This program defines a function linearSearch to search for a key in an array using linear search. It then
searches for a key in an example array in the main function and prints the result.
Program
#include <stdio.h>
int linearSearch(int arr[], int n, int key)
{
for (int i = 0; i < n; i++)
{
if (arr[i] == key)
{
return i; // return index if key found
}
}
return -1; // return -1 if key not found
}
int main()
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 10;
int result = linearSearch(arr, n, key);
if (result != -1)
{
printf("Element %d found at index %d\n", key, result);
}
else
{
printf("Element %d not found in array\n", key);
}
return 0;
}
Output:
Element 10 found at index 3
5. Aim: Write a C program to implement Binary Search
Program analysis:
This program defines a function binarySearch to search for a key in a sorted array using binary search. It then
searches for a key in an example sorted array in the main function and prints the result.
Program
#include <stdio.h>
int binarySearch(int arr[], int left, int right, int key)
{
while (left <= right)
{
int mid = left + (right - left) / 2;
// Check if key is present at mid
if (arr[mid] == key)
return mid;
// If key greater, ignore left half
if (arr[mid] < key)
left = mid + 1;
// If key is smaller, ignore right half
else
right = mid - 1;
}
// If key is not present in array
return -1;
}
int main()
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 10;
int result = binarySearch(arr, 0, n - 1, key);
if (result != -1)
{
printf("Element %d found at index %d\n", key, result);
}
else
{
printf("Element %d not found in array\n", key);
}
return 0;
}
Output:
Element 10 found at index 3
6. Aim: Write a C program to implement Single Linked List Operations:.
Program analysis:
This code now includes additional operations like insertion at the end of the list (insertAtEnd) and deletion of
a node with a given key (deleteNode). Let me provide the output.
Program
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node* next;
};
void insertAtBeginning(struct Node** head, int newData)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = *head;
*head = newNode;
}
void printList(struct Node* head)
{
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
void deleteNode(struct Node** head, int key)
{
struct Node* temp = *head;
struct Node* prev = NULL;
// If the head node itself holds the key to be deleted
if (temp != NULL && temp->data == key)
{
*head = temp->next;
free(temp);
return;
}
// Search for the key to be deleted, keep track of the previous node
while (temp != NULL && temp->data != key)
{
prev = temp;
temp = temp->next;
}
// If key was not present in linked list
if (temp == NULL)
{
printf("Key not found in the list\n");
return;
}
// Unlink the node from the linked list
prev->next = temp->next;
free(temp);
}
int main()
{
struct Node* head = NULL;
// Insert elements into the list
insertAtBeginning(&head, 3);
insertAtBeginning(&head, 6);
insertAtBeginning(&head, 9);
printf("Linked List after insertion at beginning: ");
printList(head);
// Delete a specific item from the list
deleteNode(&head, 6);
printf("Linked List after deletion of item 6: ");
printList(head);
return 0;
}
Output:
Linked List after insertion at beginning: 9 -> 6 -> 3 -> NULL
Linked List after deletion of item 6: 9 -> 3 -> NULL
7. Aim: Write a C program to implement stack using Arrays.
Program analysis:
This program demonstrates the stack operations, including initialization, pushing elements onto the stack,
popping elements from the stack, and peeking the top element. It also includes error handling for stack
overflow and underflow scenarios.
Program
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Structure to represent stack
struct Stack
{
int array[MAX_SIZE];
int top;
};
// Function to initialize the stack
void initializeStack(struct Stack *stack)
{
stack->top = -1; // Set top to -1 indicating empty stack
}
// Function to check if the stack is empty
int isEmpty(struct Stack *stack)
{
return stack->top == -1;
}
// Function to check if the stack is full
int isFull(struct Stack *stack)
{
return stack->top == MAX_SIZE - 1;
}
// Function to push element onto the stack
void push(struct Stack *stack, int data)
{
if (isFull(stack))
{
printf("Stack Overflow\n");
return;
}
stack->array[++stack->top] = data;
printf("%d pushed to stack\n", data);
}
// Function to pop element from the stack
int pop(struct Stack *stack)
{
if (isEmpty(stack))
{
printf("Stack Underflow\n");
return -1;
}
printf("%d popped from stack\n", stack->array[stack->top]);
return stack->array[stack->top--];
}
// Function to peek the top element of the stack
int peek(struct Stack *stack)
{
if (isEmpty(stack))
{
printf("Stack is empty\n");
return -1;
}
return stack->array[stack->top];
}
int main()
{
struct Stack stack;
initializeStack(&stack);
// Push elements onto the stack
push(&stack, 1);
push(&stack, 2);
push(&stack, 3);
push(&stack, 4);
push(&stack, 5);
// Pop elements from the stack
pop(&stack);
pop(&stack);
// Peek the top element of the stack
printf("Top element of the stack: %d\n", peek(&stack));
return 0;
}
Output:
1 pushed to stack
2 pushed to stack
3 pushed to stack
4 pushed to stack
5 pushed to stack
5 popped from stack
4 popped from stack
Top element of the stack: 3
8. Aim: Write a C program to implement queue using Arrays
Program analysis:
This program implements a queue using arrays. It includes functions to initialize the queue, check if the
queue is empty or full, enqueue elements into the queue, and dequeue elements from the queue. In the
main function, it demonstrates enqueuing and dequeuing elements from the queue.
Program
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Structure to represent queue
struct Queue
{
int array[MAX_SIZE];
int front, rear;
};
// Function to initialize the queue
void initializeQueue(struct Queue *queue)
{
queue->front = -1;
queue->rear = -1;
}
// Function to check if the queue is empty
int isEmpty(struct Queue *queue)
{
return queue->front == -1;
}
// Function to check if the queue is full
int isFull(struct Queue *queue)
{
return (queue->rear + 1) % MAX_SIZE == queue->front;
}
// Function to enqueue an element
void enqueue(struct Queue *queue, int data)
{
if (isFull(queue))
{
printf("Queue Overflow\n");
return;
}
if (isEmpty(queue))
{
queue->front = 0;
}
queue->rear = (queue->rear + 1) % MAX_SIZE;
queue->array[queue->rear] = data;
printf("%d enqueued to queue\n", data);
}
// Function to dequeue an element
int dequeue(struct Queue *queue)
{
if (isEmpty(queue))
{
printf("Queue Underflow\n");
return -1;
}
int data = queue->array[queue->front];
if (queue->front == queue->rear)
{
queue->front = -1;
queue->rear = -1;
}
Else
{
queue->front = (queue->front + 1) % MAX_SIZE;
}
printf("%d dequeued from queue\n", data);
return data;
}
int main()
{
struct Queue queue;
initializeQueue(&queue);
// Enqueue elements onto the queue
enqueue(&queue, 1);
enqueue(&queue, 2);
enqueue(&queue, 3);
// Dequeue elements from the queue
dequeue(&queue);
dequeue(&queue);
// Enqueue more elements
enqueue(&queue, 4);
enqueue(&queue, 5);
return 0;
}
Output:
1 enqueued to queue
2 enqueued to queue
3 enqueued to queue
1 dequeued from queue
2 dequeued from queue
4 enqueued to queue
5 enqueued to queue
9. Aim: Write a C program to implement Binary tree traversals using Recursion
Program analysis:
This program creates a binary tree and performs pre-order, in-order, and post-order traversals recursively.
Program
#include <stdio.h>
#include <stdlib.h>
// Structure for a binary tree node
struct Node
{
int data;
struct Node* left;
struct Node* right;
};
// Function to create a new node
struct Node* createNode(int data)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL)
{
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function for pre-order traversal
void preOrder(struct Node* root)
{
if (root != NULL) {
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
}
// Function for in-order traversal
void inOrder(struct Node* root)
{
if (root != NULL)
{
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
}
// Function for post-order traversal
void postOrder(struct Node* root)
{
if (root != NULL) {
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
}
int main()
{
// Creating a binary tree
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Pre-order traversal: ");
preOrder(root);
printf("\n");
printf("In-order traversal: ");
inOrder(root);
printf("\n");
printf("Post-order traversal: ");
postOrder(root);
printf("\n");
return 0;
}
Output:
Pre-order traversal: 1 2 4 5 3
In-order traversal: 4 2 5 1 3
Post-order traversal: 4 5 2 3 1