cba - Posts - OneCompiler

BUBBLE SORT:

#include <stdio.h>

void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// Last i elements are already sorted
for (int j = 0; j < n - i - 1; j++) {
// Swap if the element found is greater than the next element
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

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

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Unsorted array: ");
printArray(arr, n);

bubbleSort(arr, n);

printf("Sorted array: ");
printArray(arr, n);

return 0;

}

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;

    // 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;
}

}

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

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Unsorted array: ");
printArray(arr, n);

insertionSort(arr, n);

printf("Sorted array: ");
printArray(arr, n);

return 0;

}

MERGE SORT:

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];

// Copy data to temp arrays L[] and R[]
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 temp arrays back into arr[]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
    if (L[i] <= R[j]) arr[k++] = L[i++];
    else arr[k++] = R[j++];
}

// Copy the remaining elements of L[], if any
while (i < n1) arr[k++] = L[i++];

// Copy the remaining elements of R[], if any
while (j < n2) arr[k++] = R[j++];

}

void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid); // Left half
mergeSort(arr, mid + 1, right); // Right half
merge(arr, left, mid, right); // Merge both halves
}
}

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

int main() {
int list1[] = {12, 11, 13, 5, 6};
int list2[] = {7, 2, 3, 9, 10};
int n1 = sizeof(list1) / sizeof(list1[0]);
int n2 = sizeof(list2) / sizeof(list2[0]);

// Merge the two lists into one array
int mergedList[n1 + n2];
for (int i = 0; i < n1; i++) mergedList[i] = list1[i];
for (int i = 0; i < n2; i++) mergedList[n1 + i] = list2[i];

printf("Unsorted merged array: ");
printArray(mergedList, n1 + n2);

// Sort the merged array
mergeSort(mergedList, 0, n1 + n2 - 1);

printf("Sorted merged array: ");
printArray(mergedList, n1 + n2);

return 0;

}

LARGEST AND SMALLEST ELEMENT IN ARRAY:

#include <stdio.h>

void findMinMax(int arr[], int low, int high, int *min, int *max) {
// Base case: if there's only one element
if (low == high) {
*min = arr[low];
*max = arr[low];
return;
}

// Base case: if there are two elements
if (high == low + 1) {
    if (arr[low] < arr[high]) {
        *min = arr[low];
        *max = arr[high];
    } else {
        *min = arr[high];
        *max = arr[low];
    }
    return;
}

// Divide the array into two halves
int mid = (low + high) / 2;
int leftMin, leftMax, rightMin, rightMax;

findMinMax(arr, low, mid, &leftMin, &leftMax);  // Left half
findMinMax(arr, mid + 1, high, &rightMin, &rightMax);  // Right half

// Conquer: Combine the results from both halves
*min = (leftMin < rightMin) ? leftMin : rightMin;
*max = (leftMax > rightMax) ? leftMax : rightMax;

}

int main() {
int n;

// Take input from the user
printf("Enter the number of elements in the array: ");
scanf("%d", &n);

int arr[n];
printf("Enter the elements of the array: ");
for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
}

int min, max;
findMinMax(arr, 0, n - 1, &min, &max);

// Output the results
printf("Smallest element: %d\n", min);
printf("Largest element: %d\n", max);

return 0;

}

ACTIVITY SELECTOR PROBLEM USING GREEDY APPROACH:

#include <stdio.h>

// Function to perform Activity Selection
void activitySelector(int start[], int finish[], int n) {
// The first activity always gets selected
int i = 0;
printf("Selected activities: %d ", i + 1);

// Consider the rest of the activities
for (int j = 1; j < n; j++) {
    // If the start time of activity j is greater than or equal to
    // the finish time of the last selected activity, select it
    if (start[j] >= finish[i]) {
        printf("%d ", j + 1);
        i = j;
    }
}

}

int main() {
int n;

// Take the number of activities as input
printf("Enter the number of activities: ");
scanf("%d", &n);

int start[n], finish[n];

// Take start and finish times of the activities as input
printf("Enter the start and finish times of the activities:\n");
for (int i = 0; i < n; i++) {
    printf("Activity %d - Start time: ", i + 1);
    scanf("%d", &start[i]);
    printf("Activity %d - Finish time: ", i + 1);
    scanf("%d", &finish[i]);
}

// Sort the activities based on finish time
for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
        if (finish[i] > finish[j]) {
            // Swap the start and finish times
            int temp = finish[i];
            finish[i] = finish[j];
            finish[j] = temp;

            temp = start[i];
            start[i] = start[j];
            start[j] = temp;
        }
    }
}

// Apply the Greedy approach to select activities
activitySelector(start, finish, n);

return 0;

}

SOLUTION TO FRACTIONAL KNAPSACK PROBLEM USING GREEDY METHOD:

#include <stdio.h>

// Structure to represent an item
typedef struct {
int weight;
int value;
float ratio;
} Item;

// Function to calculate the maximum value of the knapsack using greedy method
float knapsack(Item items[], int n, int capacity) {
// Sorting items based on value/weight ratio in descending order
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (items[i].ratio < items[j].ratio) {
// Swap items[i] and items[j]
Item temp = items[i];
items[i] = items[j];
items[j] = temp;
}
}
}

int currentWeight = 0;
float totalValue = 0;

// Greedily pick items
for (int i = 0; i < n; i++) {
    if (currentWeight + items[i].weight <= capacity) {
        // Take the full item
        currentWeight += items[i].weight;
        totalValue += items[i].value;
    } else {
        // Take the fraction of the last item
        int remainingWeight = capacity - currentWeight;
        totalValue += items[i].value * ((float)remainingWeight / items[i].weight);
        break; // Knapsack is full
    }
}
return totalValue;

}

int main() {
int n, capacity;

// Take input for number of items and the knapsack capacity
printf("Enter the number of items: ");
scanf("%d", &n);
printf("Enter the capacity of the knapsack: ");
scanf("%d", &capacity);

Item items[n];

// Input the weights and values of the items
for (int i = 0; i < n; i++) {
    printf("Enter the weight and value for item %d: ", i + 1);
    scanf("%d %d", &items[i].weight, &items[i].value);
    // Calculate value/weight ratio for the greedy approach
    items[i].ratio = (float)items[i].value / items[i].weight;
}

// Find the maximum value that can be obtained
float maxValue = knapsack(items, n, capacity);

// Output the result
printf("Maximum value that can be obtained: %.2f\n", maxValue);

return 0;

}

SOLUTION FOR HUFFMAN CODING PROBLEM USING GREEDY METHOD

#include <stdio.h>
#include <stdlib.h>

// A structure to represent a node in the Huffman tree
typedef struct {
char data; // Character
int freq; // Frequency of the character
struct Node* left; // Left child
struct Node* right; // Right child
} Node;

// A function to create a new node
Node* createNode(char data, int freq) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->freq = freq;
newNode->left = newNode->right = NULL;
return newNode;
}

// A function to compare two nodes (used for sorting)
int compare(const void* a, const void* b) {
return ((Node*)a)->freq - ((Node*)b)->freq;
}

// Function to build the Huffman tree and print codes
void buildHuffmanTree(char* data, int* freq, int n) {
// Create an array of nodes
Node* nodes[n];
for (int i = 0; i < n; i++) {
nodes[i] = createNode(data[i], freq[i]);
}

// Sort the nodes based on frequency
qsort(nodes, n, sizeof(Node*), compare);

// Build the Huffman tree
while (n > 1) {
    // Extract the two nodes with the smallest frequencies
    Node* left = nodes[0];
    Node* right = nodes[1];

    // Create a new internal node with combined frequency
    Node* newNode = createNode('$', left->freq + right->freq);

    // Make the two nodes children of the new internal node
    newNode->left = left;
    newNode->right = right;

    // Replace the two nodes with the new node in the array
    nodes[1] = newNode;
    nodes[0] = nodes[--n];  // Remove the last node

    // Re-sort the array
    qsort(nodes, n, sizeof(Node*), compare);
}

// The last remaining node is the root of the Huffman tree
Node* root = nodes[0];

// A helper function to print the codes using recursion
void printCodes(Node* root, int* arr, int top) {
    if (root->left) {
        arr[top] = 0;  // Assign 0 for left branch
        printCodes(root->left, arr, top + 1);
    }

    if (root->right) {
        arr[top] = 1;  // Assign 1 for right branch
        printCodes(root->right, arr, top + 1);
    }

    // If it's a leaf node, print the character and its code
    if (!root->left && !root->right) {
        printf("%c: ", root->data);
        for (int i = 0; i < top; i++) {
            printf("%d", arr[i]);
        }
        printf("\n");
    }
}

// Array to store the Huffman codes
int arr[100], top = 0;

// Print the codes starting from the root of the tree
printCodes(root, arr, top);

}

int main() {
// Input: characters and their frequencies
char data[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
int freq[] = { 5, 9, 12, 13, 16, 45 };
int n = sizeof(data) / sizeof(data[0]);

// Build Huffman Tree and print codes
buildHuffmanTree(data, freq, n);

return 0;

}

DJIKSTRA'S ALGORITHM:

#include <stdio.h>
#include <limits.h>

#define V 9 // Number of vertices in the graph

// Function to find the vertex with the minimum distance value that is not yet processed
int minDistance(int dist[], int sptSet[]) {
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++) {
    if (sptSet[v] == 0 && dist[v] <= min) {
        min = dist[v];
        min_index = v;
    }
}
return min_index;

}

// Function to implement Dijkstra's algorithm
void dijkstra(int graph[V][V], int src) {
int dist[V]; // Array to store the shortest distance from src to each vertex
int sptSet[V]; // Shortest path tree set, keeps track of vertices whose shortest distance is already found

// Initialize distances as INFINITE and sptSet as false
for (int i = 0; i < V; i++) {
    dist[i] = INT_MAX;
    sptSet[i] = 0;
}

// Distance to the source is always 0
dist[src] = 0;

// Find the shortest path for all vertices
for (int count = 0; count < V - 1; count++) {
    // Get the vertex with the minimum distance value from the set of vertices
    // not yet processed
    int u = minDistance(dist, sptSet);

    // Mark the vertex u as processed
    sptSet[u] = 1;

    // Update the distance value of the adjacent vertices of the selected vertex u
    for (int v = 0; v < V; v++) {
        // Update dist[v] if the current distance is smaller than the previous one
        if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
            dist[v] = dist[u] + graph[u][v];
        }
    }
}

// Print the shortest distances from the source
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++) {
    printf("%d \t %d\n", i, dist[i]);
}

}

int main() {
// Graph represented as an adjacency matrix
int graph[V][V] = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};

// Call the Dijkstra function to find the shortest path from source vertex 0
dijkstra(graph, 0);

return 0;

}

PRIM'S ALGORITHM:

#include <stdio.h>
#include <limits.h>

#define V 5 // Number of vertices in the graph

// Function to find the vertex with the minimum key value that has not been included in the MST yet
int minKey(int key[], int mstSet[]) {
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++) {
    if (mstSet[v] == 0 && key[v] < min) {
        min = key[v];
        min_index = v;
    }
}
return min_index;

}

// Function to implement Prim's algorithm
void primMST(int graph[V][V]) {
int parent[V]; // Array to store the constructed MST
int key[V]; // Key values used to pick the minimum weight edge
int mstSet[V]; // To represent the vertices included in the MST

// Initialize all key values as INFINITE and mstSet[] as false
for (int i = 0; i < V; i++) {
    key[i] = INT_MAX;
    mstSet[i] = 0;
}

// Start with the first vertex (arbitrary choice)
key[0] = 0; // Make key of the first vertex 0 to start the MST from it
parent[0] = -1; // First node has no parent

// Find the minimum spanning tree for all vertices
for (int count = 0; count < V - 1; count++) {
    // Pick the minimum key vertex from the set of vertices not yet included in MST
    int u = minKey(key, mstSet);

    // Add the picked vertex to the MST set
    mstSet[u] = 1;

    // Update the key and parent values of the adjacent vertices of the selected vertex
    for (int v = 0; v < V; v++) {
        // graph[u][v] is non-zero only if there is an edge from u to v
        if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {
            key[v] = graph[u][v];
            parent[v] = u;
        }
    }
}

// Print the constructed MST
printf("Edge \t Weight\n");
for (int i = 1; i < V; i++) {
    printf("%d - %d \t %d\n", parent[i], i, graph[i][parent[i]]);
}

}

int main() {
// Graph represented as an adjacency matrix
int graph[V][V] = {
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}
};

// Call the function to find the MST
primMST(graph);

return 0;

}

DEPTH FIRST SEARCH (DFS):

#include <stdio.h>

#define V 5 // Number of vertices in the graph

// Function to perform DFS
void DFS(int graph[V][V], int visited[], int vertex) {
// Mark the current node as visited and print it
visited[vertex] = 1;
printf("%d ", vertex);

// Visit all the adjacent vertices of the current vertex
for (int i = 0; i < V; i++) {
    // If there is an edge and the vertex hasn't been visited yet
    if (graph[vertex][i] == 1 && !visited[i]) {
        DFS(graph, visited, i);  // Recursive call to visit the adjacent vertex
    }
}

}

int main() {
// Graph represented as an adjacency matrix
int graph[V][V] = {
{0, 1, 0, 1, 0},
{1, 0, 1, 0, 1},
{0, 1, 0, 1, 0},
{1, 0, 1, 0, 1},
{0, 1, 0, 1, 0}
};

int visited[V] = {0};  // Array to keep track of visited vertices

// Start DFS traversal from vertex 0
printf("DFS starting from vertex 0: ");
DFS(graph, visited, 0);

return 0;

}

BREADTH FIRST SEARCH:

#include <stdio.h>
#include <stdlib.h>

#define V 5 // Number of vertices in the graph

// Queue structure
struct Queue {
int items[V];
int front;
int rear;
};

// Function to initialize the queue
void initQueue(struct Queue* q) {
q->front = -1;
q->rear = -1;
}

// Function to check if the queue is empty
int isEmpty(struct Queue* q) {
return q->front == -1;
}

// Function to add an element to the queue
void enqueue(struct Queue* q, int value) {
if (q->rear == V - 1) {
printf("Queue is full!\n");
} else {
if (q->front == -1) {
q->front = 0;
}
q->rear++;
q->items[q->rear] = value;
}
}

// Function to remove an element from the queue
int dequeue(struct Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty!\n");
return -1;
} else {
int item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
q->front = q->rear = -1; // Reset the queue
}
return item;
}
}

// Function to perform BFS
void BFS(int graph[V][V], int start) {
int visited[V] = {0}; // Array to keep track of visited vertices
struct Queue q; // Queue to hold vertices to be visited
initQueue(&q); // Initialize the queue

// Start BFS from the 'start' vertex
visited[start] = 1;
enqueue(&q, start);  // Enqueue the starting vertex

while (!isEmpty(&q)) {
    // Dequeue a vertex from the queue
    int current = dequeue(&q);
    printf("%d ", current);

    // Visit all the adjacent vertices of the dequeued vertex
    for (int i = 0; i < V; i++) {
        // If there's an edge and the vertex hasn't been visited yet
        if (graph[current][i] == 1 && !visited[i]) {
            visited[i] = 1;  // Mark it as visited
            enqueue(&q, i);  // Enqueue the vertex
        }
    }
}

}

int main() {
// Graph represented as an adjacency matrix
int graph[V][V] = {
{0, 1, 0, 1, 0},
{1, 0, 1, 0, 1},
{0, 1, 0, 1, 0},
{1, 0, 1, 0, 1},
{0, 1, 0, 1, 0}
};

// Start BFS traversal from vertex 0
printf("BFS starting from vertex 0: ");
BFS(graph, 0);

return 0;

}

TOPOLOGICAL SORT:

#include <stdio.h>
#include <stdlib.h>

#define V 6 // Number of vertices in the graph

// Stack to store the topological sort result
int stack[V];
int top = -1; // Stack pointer

// Function to push elements to the stack
void push(int vertex) {
stack[++top] = vertex;
}

// Function to perform DFS and store the result in stack
void DFS(int graph[V][V], int visited[], int vertex) {
visited[vertex] = 1; // Mark the vertex as visited

// Visit all the adjacent vertices
for (int i = 0; i < V; i++) {
    if (graph[vertex][i] == 1 && !visited[i]) {
        DFS(graph, visited, i);  // Recursive DFS call for unvisited vertices
    }
}

// Push the vertex to stack after all its adjacent vertices are processed
push(vertex);

}

// Function to perform Topological Sort
void topologicalSort(int graph[V][V]) {
int visited[V] = {0}; // Array to track visited vertices

// Call DFS for each unvisited vertex
for (int i = 0; i < V; i++) {
    if (!visited[i]) {
        DFS(graph, visited, i);
    }
}

// Print the topological sort (stack will give the reverse order)
printf("Topological Sort: ");
while (top != -1) {
    printf("%d ", stack[top--]);
}
printf("\n");

}

int main() {
// Graph represented as an adjacency matrix
int graph[V][V] = {
{0, 1, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0},
{0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0}
};

// Perform Topological Sort
topologicalSort(graph);

return 0;

}

FORD FULKERSON ALGORITHM:

#include <stdio.h>
#include <limits.h>

#define V 6 // Number of vertices in the graph

// Function to perform DFS and find an augmenting path
int dfs(int graph[V][V], int source, int sink, int visited[], int path[]) {
visited[source] = 1;
if (source == sink)
return 1; // Found a path

// Explore all the adjacent vertices
for (int i = 0; i < V; i++) {
    if (!visited[i] && graph[source][i] > 0) {
        path[i] = source;  // Record the parent of the current node
        if (dfs(graph, i, sink, visited, path)) {
            return 1;  // Found a path
        }
    }
}
return 0;  // No augmenting path found

}

// Function to implement Ford-Fulkerson algorithm
int fordFulkerson(int graph[V][V], int source, int sink) {
int graphCopy[V][V];
int path[V]; // Array to store the augmenting path
int maxFlow = 0;

// Create a copy of the original graph to keep track of the remaining capacities
for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
        graphCopy[i][j] = graph[i][j];
    }
}

// Augment the flow while there is a path from source to sink
while (1) {
    int visited[V] = {0};  // Reset visited array
    if (!dfs(graphCopy, source, sink, visited, path)) {
        break;  // No more augmenting path
    }

    // Find the maximum flow through the path found by DFS
    int pathFlow = INT_MAX;
    for (int v = sink; v != source; v = path[v]) {
        int u = path[v];
        pathFlow = (pathFlow < graphCopy[u][v]) ? pathFlow : graphCopy[u][v];
    }

    // Update the residual graph
    for (int v = sink; v != source; v = path[v]) {
        int u = path[v];
        graphCopy[u][v] -= pathFlow;
        graphCopy[v][u] += pathFlow;
    }

    maxFlow += pathFlow;  // Add the path flow to the total max flow
}

return maxFlow;  // Return the maximum flow

}

int main() {
// Graph represented as an adjacency matrix where graph[i][j] is the capacity of the edge from vertex i to vertex j
int graph[V][V] = {
{0, 16, 13, 0, 0, 0},
{0, 0, 10, 12, 0, 0},
{0, 4, 0, 0, 14, 0},
{0, 0, 9, 0, 0, 20},
{0, 0, 0, 7, 0, 4},
{0, 0, 0, 0, 0, 0}
};

// Source and sink
int source = 0;
int sink = 5;

// Perform Ford-Fulkerson algorithm to find the maximum flow
int maxFlow = fordFulkerson(graph, source, sink);

printf("The maximum flow from source %d to sink %d is %d\n", source, sink, maxFlow);

return 0;

}

HEAP SORT:

#include <stdio.h>

void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

// Function to "heapify" a subtree rooted at index i
void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // Left child index
int right = 2 * i + 2; // Right child index

// If left child is larger than root
if (left < n && arr[left] > arr[largest]) {
    largest = left;
}

// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest]) {
    largest = right;
}

// If largest is not root
if (largest != i) {
    swap(&arr[i], &arr[largest]);
    
    // Recursively heapify the affected subtree
    heapify(arr, n, largest);
}

}

// Function to perform heap sort
void heapSort(int arr[], int n) {
// Build a max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}

// One by one extract elements from the heap
for (int i = n - 1; i > 0; i--) {
    // Move current root to end
    swap(&arr[0], &arr[i]);

    // Call max heapify on the reduced heap
    heapify(arr, i, 0);
}

}

// Function to print the array
void printArray(int arr[], int n) {
for (int i = 0; i < n; 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);

// Perform heap sort
heapSort(arr, n);

printf("Sorted array: ");
printArray(arr, n);

return 0;

}

SELECTION SORT:

#include <stdio.h>

// Function to perform selection sort
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i; // Index of the minimum element

    // Find the minimum element in the unsorted part
    for (int j = i + 1; j < n; j++) {
        if (arr[j] < arr[minIndex]) {
            minIndex = j;
        }
    }

    // Swap the found minimum element with the first element
    int temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
}

}

// Function to print the array
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("Unsorted array: ");
printArray(arr, n);

// Perform selection sort
selectionSort(arr, n);

printf("Sorted array: ");
printArray(arr, n);

return 0;

}

QUICK SORT:

#include <stdio.h>

// Function to swap two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

// Partition function to rearrange the array
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; j++) {
    if (arr[j] < pivot) {
        i++;
        swap(&arr[i], &arr[j]);
    }
}
swap(&arr[i + 1], &arr[high]); // Place pivot in the correct position
return (i + 1);  // Return the pivot index

}

// Quick sort function
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // Partition index

    quickSort(arr, low, pi - 1);  // Sort elements before the pivot
    quickSort(arr, pi + 1, high); // Sort elements after the pivot
}

}

// 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[] = {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;

}