PROGRAM 1
AIM: To implement Selection Sort in C
ALGORITHM:
PROGRAM CODE:
#include<stdio.h>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
// Update min_idx if a smaller element is found
min_idx = j;
}
}
// Move minimum element to its
// correct position
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = 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]);
printf("Original array: ");
printArray(arr, n);
selectionSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
Output
Original vector: 64 25 12 22 11
Sorted vector: 11 12 22 25 64
PROGRAM 2:
AIM: To implement bubble sort in C
ALGORITHM:
PROGRAM CODE:
#include <stdbool.h>
#include <stdio.h>
void swap(int* xp, int* yp){
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// An optimized version of Bubble Sort
void bubbleSort(int arr[], int n){
int i, j;
bool swapped;
for (i = 0; i < n - 1; i++) {
swapped = false;
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
swapped = true;
}
}
// If no two elements were swapped by inner loop,
// then break
if (swapped == false)
break;
}
}
// Function to print an array
void printArray(int arr[], int size){
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
}
int main(){
int arr[] = { 64, 34, 25, 12, 22, 11, 90 };
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Output
Sorted array:
11 12 22 25 34 64 90
PROGRAM 3:
AIM: To implement insertion sort in C
ALGORITHM:
PROGRAM CODE:
// C program to implement insertion sort
#include <math.h>
#include <stdio.h>
void insertionSort(int arr[], int N) {
// Starting from the second element
for (int i = 1; i < N; i++) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1], that are
// greater than key, to one position to
// the right of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// Move the key to its correct position
arr[j + 1] = key;
}
}
int main() {
int arr[] = { 12, 11, 13, 5, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
printf("Unsorted array: ");
for (int i = 0; i < N; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// Calling insertion sort on array arr
insertionSort(arr, N);
printf("Sorted array: ");
for (int i = 0; i < N; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Output
Unsorted array: 12 11 13 5 6
Sorted array: 5 6
PROGRAM 4:
AIM: To implement Linked list in C
ALGORITHM:
PROGRAM CODE:
// C Program to create a Linked List
#include <stdio.h>
#include <stdlib.h>
// Define the structure of Node
typedef struct Node {
// Data field. Can add more data according to our need
int data;
// Pointer to the next node
struct Node *next;
} Node;
int main() {
// Create the First Node of the Linked List
// This will serve as the head of the list
Node *first = (Node *)malloc(sizeof(Node));
// Assigning data
first->data = 10;
// Creating the second node in the list
Node *second = (Node *)malloc(sizeof(Node));
// Assigning data
second->data = 20;
// Creating the third node
Node *third = (Node *)malloc(sizeof(Node));
// Assigning data
third->data = 30;
// Linking the nodes
first->next = second; // This will create: 10 -> 20
second->next = third; // This will create: 10 -> 20 -> 30
third->next = NULL; // This will create: 10 -> 20 -> 30 -> NULL
printf("Linked List: ");
Node* temp = first;
while(temp) {
printf("%d ", temp->data);
temp = temp->next;
}
return 0;
}
Output
Linked List: 10 20 30
PROGRAM 7:
AIM:Program to implement Push operation in Stack.
Algorithm:
Abhishek yadav 2300910100012 CS1 (A1) Semester III
Program Code :
#include <stdio.h>
#include <stdlib.h>
// Define the structure of a node
struct node {
int data;
struct node* link;
} *top = NULL;
// Function to push an element into the stack
void push(int data) {
struct node* newnode = (struct node*)malloc(sizeof(struct node));
if (newnode == NULL) {
printf("Stack overflow\n");
return;
}
newnode->data = data;
newnode->link = top;
top = newnode;
}
// Function to print the stack elements
void print() {
struct node* temp = top;
printf("The stack elements are:\n");
while (temp) {
printf("%d\n", temp->data);
temp = temp->link;
}
}
int main() {
push(10); // Push 10 onto the stack
push(20); // Push 20 onto the stack
push(40); // Push 40 onto the stack
push(50); // Push 50 onto the stack
print(); // Print all elements in the stack
return 0;
}
Abhishek yadav 2300910100012 CS1 (A1) Semester III
OUTPUT :
The stack elements are:
50
40
20
10
Abhishek yadav 2300910100012 CS1 (A1) Semester III
PROGRAM 8:
AIM:Program to implement Pop operation in Stack.
Algorithm:
Abhishek yadav 2300910100012 CS1 (A1) Semester III
Program Code :
#include <stdio.h>
#include <stdlib.h>
// Define the structure of a node
struct node {
int data;
struct node* link;
} *top = NULL;
// Function to push an element into the stack
void push(int data) {
struct node* newnode = (struct node*)malloc(sizeof(struct node));
if (newnode == NULL) {
printf("Stack overflow\n");
return;
}
newnode->data = data;
newnode->link = top; // Link the new node to the current top
top = newnode; // Update the top pointer
}
// Function to pop an element from the stack
int pop() {
if (top == NULL) { // Check for stack underflow
printf("Stack underflow\n");
return -1; // Return -1 as an error value
}
struct node* temp = top; // Temporarily store the top node
int val = temp->data; // Store the data to return later
top = top->link; // Update the top pointer to the next node
free(temp); // Free the memory of the popped node
temp = NULL; // Avoid dangling pointers
return val; // Return the popped value
}
// Function to print the stack elements
void print() {
struct node* temp = top;
printf("The stack elements are:\n");
while (temp) {
printf("%d\n", temp->data);
temp = temp->link;
}
}
int main() {
push(10);
push(20);
push(40);
push(50);
printf("Popped element: %d\n", pop()); // Pop an element and print it
print(); // Print the remaining stack elements
return 0;
}
Abhishek yadav 2300910100012 CS1 (A1) Semester III
OUTPUT :
Popped element: 50
The stack elements are:
40
20
10
Abhishek yadav 2300910100012 CS1 (A1) Semester III
PROGRAM 9:
AIM:Program to implement merge sorting algorithm.
Algorithm:
Abhishek yadav 2300910100012 CS1 (A1) Semester III
Program Code :
#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
int temp[100]; // Temporary array to store sorted elements
int i = left; // Start of left part
int j = mid + 1; // Start of right part
int k = 0; // Index for temp array
// Merge the two parts into temp[]
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// Copy remaining elements from left part
while (i <= mid) {
temp[k++] = arr[i++];
}
// Copy remaining elements from right part
while (j <= right) {
temp[k++] = arr[j++];
}
// Copy sorted elements back into the original array
for (i = left, k = 0; i <= right; i++, k++) {
arr[i] = temp[k];
}
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2; // Find the middle
mergeSort(arr, left, mid); // Sort the left part
mergeSort(arr, mid + 1, right); // Sort the right part
merge(arr, left, mid, right); // Merge the two sorted parts
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {20, 10, 50, 30, 40};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original Array: ");
printArray(arr, size);
mergeSort(arr, 0, size - 1);
printf("Sorted Array: ");
printArray(arr, size);
return 0;
}
Abhishek yadav 2300910100012 CS1 (A1) Semester III
OUTPUT :
Original Array: 20 10 50 30 40
Sorted Array: 10 20 30 40 50
Abhishek yadav 2300910100012 CS1 (A1) Semester III
PROGRAM 10:
AIM:Program to implement Quick sorting algorithm.
Algorithm:
Abhishek yadav 2300910100012 CS1 (A1) Semester III
Program Code :
#include <stdio.h>
// Function to swap two numbers
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Partition function: Rearranges elements around the pivot
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Pick the last element as the pivot
int i = low; // Start index for smaller numbers
for (int j = low; j < high; j++) {
if (arr[j] < pivot) { // If the current number is smaller than pivot
swap(&arr[i], &arr[j]); // Swap it to the correct position
i++;
}
}
swap(&arr[i], &arr[high]); // Place pivot in the correct position
return i; // Return the pivot index
}
// Quick Sort function
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // Get pivot index
quickSort(arr, low, pi - 1); // Sort the left part
quickSort(arr, pi + 1, high); // Sort the right part
}
}
// Function to print an 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, 4, 7, 9, 1, 15}; // Example array
int size = sizeof(arr) / sizeof(arr[0]); // Size of the array
printf("Original Array: ");
printArray(arr, size); // Print the array before sorting
quickSort(arr, 0, size - 1); // Sort the array using Quick Sort
printf("Sorted Array: ");
printArray(arr, size); // Print the sorted array
return 0;
}
Abhishek yadav 2300910100012 CS1 (A1) Semester III
OUTPUT :
Original Array: 12 4 7 9 1 15
Sorted Array: 1 4 7 9 12 15
Abhishek yadav 2300910100012 CS1 (A1) Semester III
PROGRAM 5:
AIM:Program to insert a node in a linked list
Algorithm:
Abhishek yadav 2300910100012 CS1 (A1) Semester III
Program Code :
#include <stdio.h>
#include <stdlib.h>
// Define the structure of a node
struct Node {
int data;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the beginning
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head; // Point new node to the current head
*head = newNode; // Update head to the new node
}
// Function to insert a node at the end
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) { // If the list is empty
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) { // Traverse to the last node
temp = temp->next;
}
temp->next = newNode; // Link the new node at the end
}
// Function to display the linked list
void printList(struct Node* head) {
struct Node* temp = head;
printf("Linked List: ");
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL; // Initialize an empty linked list
// Insert nodes
insertAtBeginning(&head, 10); // Insert 10 at the beginning
insertAtEnd(&head, 20); // Insert 20 at the end
insertAtBeginning(&head, 5); // Insert 5 at the beginning
insertAtEnd(&head, 30); // Insert 30 at the end
// Display the linked list
printList(head);
return 0;
}
Abhishek yadav 2300910100012 CS1 (A1) Semester III
OUTPUT :
Linked List: 5 -> 10 -> 20 -> 30
Abhishek yadav 2300910100012 CS1 (A1) Semester III
PROGRAM 6:
AIM:Program to delete a node in a linked list
Algorithm:
Abhishek yadav 2300910100012 CS1 (A1) Semester III
Program Code :
#include <stdio.h>
#include <stdlib.h>
// Define the structure of a node
struct Node {
int data;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the end
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) { // If the list is empty
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) { // Traverse to the last node
temp = temp->next;
}
temp->next = newNode; // Link the new node at the end
}
// Function to delete a node from the beginning
void deleteFromBeginning(struct Node** head) {
if (*head == NULL) { // If the list is empty
printf("The list is empty. Nothing to delete.\n");
return;
}
struct Node* temp = *head;
*head = (*head)->next; // Move the head pointer to the next node
free(temp); // Free the memory of the deleted node
}
// Function to display the linked list
void printList(struct Node* head) {
struct Node* temp = head;
if (head == NULL) {
printf("The list is empty.\n");
return;
}
printf("Linked List: ");
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL; // Initialize an empty linked list
// Insert some nodes into the linked list
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
insertAtEnd(&head, 40);
printf("Original List:\n");
printList(head);
// Delete node from the beginning
deleteFromBeginning(&head);
printf("List after deleting from the beginning:\n");
printList(head);
return 0;
}
OUTPUT :
Original List:
Linked List: 10 -> 20 -> 30 -> 40
List after deleting from the beginning:
Linked List: 20 -> 30 -> 40
Abhishek yadav 2300910100012 CS1 (A1) Semester III
