LINEAR SEARCH

PROGRAM:

#include <stdio.h>
#include<time.h>
void linear(int n, int arr[] ,int a){
int i;
for( i=0;i<n;i++){
if(arr[i] == a){
printf("ELement found at %d ", i);
return;
}
}
printf("element not found");
}
void main(){
int i,n, arr[50] ,a;
clock_t t;
printf("enter size:");
scanf("%d", &n);
printf("Enter elements:");
for (i=0;i<n;i++){
scanf("%d",&arr[i]);
}
printf("Enter the value to be found:");
scanf("%d",&a);
t= clock();
linear(n,arr,a);
t=clock()-t;
double time= t;
printf("\n Time taken for execution is %f seconds", time);
}

OUTPUT:

enter size:3
Enter elements:16 75 23
Enter the value to be found:78
element not found
Time taken for execution is 2.000000 seconds
enter size:4
Enter elements:3 4 5 6
Enter the value to be found:4
ELement found at 1
Time taken for execution is 10.000000 seconds

enter size:5
Enter elements:112 234 567 764 123
Enter the value to be found:567
ELement found at 2
Time taken for execution is 5.000000 seconds

enter size:6
Enter elements:34 6 7 89 90 4
Enter the value to be found:4
ELement found at 5
Time taken for execution is 8.000000 seconds

enter size:10
Enter elements:1 2 3 4 43 32 21 123 234 432
Enter the value to be found:432
ELement found at 9
Time taken for execution is 5.000000 seconds
BINARY SEARCH

PROGRAM:

#include <stdio.h>
#include<time.h>
void binary(int n, int arr[] ,int a){
int i;
int l =0,h =n-1;
for( i=0;i<n;i++){
int mid = (l+h)/2;
if(arr[i] == a){
printf("ELement found at %d ", i);
return;
}
else if (a<mid){
h = mid-1;
}
else if(a>mid){
l= mid + 1;
}
}
printf("element not found");
}
void main(){
int i,n, arr[50] ,a;
clock_t t;
printf("enter size:");
scanf("%d", &n);
printf("Enter elements in ascending order:");
for (i=0;i<n;i++){
scanf("%d", &arr[i]);
}
printf("Enter the value to be found:");
scanf("%d",&a);
t= clock();
binary(n,arr,a);
t=clock()-t;
double time= t;
printf("\n Time taken for execution is %f seconds", time);
}
OUTPUT:

enter size:3
Enter elements in ascending order:34 88 90
Enter the value to be found:88
ELement found at 1
Time taken for execution is 5.000000 seconds

enter size:4
Enter elements in ascending order:23 45 67 89
Enter the value to be found:45
ELement found at 1
Time taken for execution is 7.000000 seconds

enter size:5
Enter elements in ascending order:5 6 7 8 9
Enter the value to be found:7
ELement found at 2
Time taken for execution is 8.000000 seconds

enter size:6
Enter elements in ascending order:12 13 14 15 177 899
Enter the value to be found:14
ELement found at 2
Time taken for execution is 9.000000 seconds

enter size:7
Enter elements in ascending order:22 33 44 55 66 77 88
Enter the value to be found:55
ELement found at 3
Time taken for execution is 7.000000 seconds
PATTERN MATCHING

PROGRAM:

#include <stdio.h>
#include <string.h>

void search(char* pat, char* txt)

{
int M = strlen(pat);
int N = strlen(txt);
for (int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;

if (j== M)
printf("Pattern found at index %d \n", i);
}
}
int main()
{
char txt[100];
char pat[100];
printf("\n Enter text:");
scanf("%s",txt);
printf("\n Enter pattern:");
scanf("%s", pat);
search(pat, txt);
return 0;
}

OUTPUT:

Enter text: rtyuiopasduiohjkuio

Enter pattern: uio
Pattern found at index 3
Pattern found at index 10
Pattern found at index 16
INSERTION SORT

PROGRAM:

#include <stdio.h>
#include <time.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 = j - 1;
}
arr[j + 1] = key;
}
}

int main() {
int n;
clock_t t;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements: ", n);
for (int i = 0; i < n; ++i) {
scanf("%d", &arr[i]);
}
t=clock();
insertionSort(arr, n);
t = clock()-t;
double time = t;
printf("Sorted array: ");
for (int i = 0; i < n; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
printf("Execution time %2f seconds",time);
return 0;
}

OUTPUT:
Enter the number of elements: 2
Enter 2 elements: 99 45
Sorted array: 45 99
Execution time 1.000000 seconds

Enter the number of elements: 3

Enter 3 elements: 54 3 12
Sorted array: 3 12 54
Execution time 2.000000 seconds

Enter the number of elements: 4

Enter 4 elements: 45 76 33 21
Sorted array: 21 33 45 76
Execution time 5.000000 seconds

Enter the number of elements: 5

Enter 5 elements: 8 5 3 9 74
Sorted array: 3 5 8 9 74
Execution time 2.000000 seconds
HEAP SORT

PROGRAM:

#include <stdio.h>
#include <time.h>
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
int main() {
int n;
clock_t t;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements: ", n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("Original array: ");
t=clock();
for (int i = 0; i < n; i++)
 printf("%d ", arr[i]);
printf("\n");
heapSort(arr, n);
t = clock()-t;
double time = t;
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
printf("Execution time %2f seconds",time);
}

OUTPUT:

Enter the number of elements: 5

Enter 5 elements: 34 78 6 23 1
Original array: 34 78 6 23 1
Sorted array: 1 6 23 34 78
Execution time 14.000000 seconds

Enter the number of elements: 4

Enter 4 elements: 6 8 3 5
Original array: 6 8 3 5
Sorted array: 3 5 6 8
Execution time 18.000000 seconds

Enter the number of elements: 3

Enter 3 elements: 3 7 4
Original array: 3 7 4
Sorted array: 3 4 7
Execution time 17.000000 seconds
BFS

PROGRAM:

#include <stdio.h>
int n, i, j, visited[10], queue[10], front = -1, rear = -1;
int adj[10][10];

void bfs(int v)
{
for (i = 1; i <= n; i++)
if (adj[v][i] && !visited[i])
queue[++rear] = i;
if (front <= rear)
{
visited[queue[front]] = 1;
bfs(queue[front++]);
}
}
void main()
{
int v;
printf("Enter the number of vertices: ");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
queue[i] = 0;
visited[i] = 0;
}
printf("Enter graph data in matrix form: \n");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
scanf("%d", &adj[i][j]);
printf("Enter the starting vertex: ");
scanf("%d", &v);
bfs(v);
printf("The node which are reachable are: \n");
for (i = 1; i <= n; i++)
if (visited[i])
printf("%d\t", i);
Else
printf("BFS is not possible. Not all nodes are reachable");
return 0;
}

OUTPUT:

Enter the number of vertices: 5

Enter graph data in matrix form:
01010
10111
00011
11100
10110
Enter the starting vertex: 3
The node which are reachable are:
1 2 3 4 5
DFS

PROGRAM:

#include <stdio.h>
int n, i, j, visited[10], stack[10], top = -1;
int adj[10][10];

void dfs(int v)
{
printf("%d ", v);
visited[v] = 1;
for (i = 1; i <= n; i++)
if (adj[v][i] && !visited[i])
dfs(i);
}

int main()
{
int v;
printf("Enter the number of vertices: ");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
stack[i] = 0;
visited[i] = 0;
}
printf("Enter graph data in matrix form: \n");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
scanf("%d", &adj[i][j]);
printf("Enter the starting vertex: ");
scanf("%d", &v);
printf("DFS traversal: ");
dfs(v);
printf("\n");
return 0;
}
OUTPUT:

Enter the number of vertices: 5

Enter graph data in matrix form:
01010
10111
00011
11100
10110
Enter the starting vertex: 2
DFS traversal: 2 1 4 3 5
DIJKSTRA’S ALGORITHM

PROGRAM:

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#define V 4
int minDistance(int dist[], bool sptSet[]) {
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
void dijkstra(int graph[V][V], int src) {
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}
int main() {
int graph[V][V];
printf("Enter the adjacency matrix for the graph (%d x %d):\n", V, V);
for(int i = 0; i < V; i++) {
for(int j = 0; j < V; j++) {
scanf("%d", &graph[i][j]);
}
}
int src;
printf("Enter the source vertex: ");
 scanf("%d", &src);
dijkstra(graph, src);
return 0;
}

OUTPUT:

Enter the adjacency matrix for the graph (4 x 4):

1011
0010
1111
0011
Enter the source vertex: 3
Vertex Distance from Source
0 2
1 2
2 1
3 0
PRIM’S ALGORITHM

PROGRAM:

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#define V 4
int minKey(int key[], bool mstSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
void printMST(int parent[], int graph[V][V]) {
printf("Edge \tWeight\n");
for (int i = 1; i < V; i++)
printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}
void primMST(int graph[V][V]) {
int parent[V];
int key[V];
bool mstSet[V];
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
printMST(parent, graph);
}
int main() {
int graph[V][V];
printf("Enter the adjacency matrix for the graph (%d x %d):\n", V, V);
for(int i = 0; i < V; i++) {
for(int j = 0; j < V; j++) {
scanf("%d", &graph[i][j]);
 }
}
primMST(graph);
return 0;
}

OUTPUT:

Enter the adjacency matrix for the graph (4 x 4):

1111
1110
0111
1111
Edge Weight
0-1 1
0-2 0
0-3 1
FLOYD ALGORITHM

PROGRAM:

#include <stdio.h>
#define V 4
void floydWarshall(int graph[V][V]) {
int dist[V][V];
int i, j, k;
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
for (k = 0; k < V; k++) {
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printf("shortest distances:\n");
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (dist[i][j] == 99999)
printf("%7s", "INF");
else
printf("%7d", dist[i][j]);
}
printf("\n");
}
}
int main() {
int graph[V][V] = {{0, 5, 99999, 10},
{99999, 0, 3, 99999},
{99999, 99999, 0, 1},
{99999, 99999, 99999, 0}};
floydWarshall(graph);
return 0;
}
OUTPUT:

shortest distances:
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0
WARSHALL’S ALGORITHM

PROGRAM:
#include <stdio.h>
#define V 4
void transitiveClosure(int graph[V][V]) {
int reach[V][V];
int i, j, k;
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
reach[i][j] = graph[i][j];
for (k = 0; k < V; k++) {
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
}
}
}
printf("Transitive closure of the given graph is :\n");
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
printf("%d ", reach[i][j]);
}
printf("\n");
}
}
int main() {
int graph[V][V] = { {1, 1, 0, 1},
{0, 1, 1, 0},
{0, 0, 1, 1},
{0, 0, 0, 1} };
transitiveClosure(graph);
return 0;
}

OUTPUT:
Transitive closure of the given graph is :
1111
0111
0011
0001
MINMAX

PROGRAM:

#include <stdio.h>
#include <stdlib.h>
void findMaxMin(int arr[], int low, int high, int *max, int *min);
int main() {
int n, i;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements:\n", n);
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
int max = arr[0], min = arr[0];
findMaxMin(arr, 0, n-1, &max, &min);
printf("Maximum element: %d\n", max);
printf("Minimum element: %d\n", min);
return 0;
}
void findMaxMin(int arr[], int low, int high, int *max, int *min) {
if (low == high) {
if (arr[low] > *max)
*max = arr[low];
if (arr[low] < *min)
*min = arr[low];
return;
}
if (high - low == 1) {
if (arr[low] < arr[high]) {
if (arr[low] < *min)
*min = arr[low];
if (arr[high] > *max)
*max = arr[high];
} else {
if (arr[high] < *min)
*min = arr[high];
if (arr[low] > *max)
*max = arr[low];
}
return;
 }
int mid = (low + high) / 2;
findMaxMin(arr, low, mid, max, min);
findMaxMin(arr, mid + 1, high, max, min);
}

OUTPUT:

Enter the number of elements: 5

Enter 5 elements:
12 56 78 999 23
Maximum element: 999
Minimum element: 12
QUICK SORT

PROGRAM:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);
int main() {
int n, i;
clock_t start, end;
double time_taken;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements:\n", n);
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
start = clock();
quickSort(arr, 0, n-1);
end = clock();
printf("Sorted array:\n");
for(i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
time_taken = ((double)(end - start))/CLOCKS_PER_SEC;
printf("\nTime taken for Quick Sort: %f seconds\n", time_taken);
return 0;
}
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 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++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i + 1;
}

OUTPUT:

Enter the number of elements: 5

Enter 5 elements:
34 55 23 15 6
Sorted array:
6 15 23 34 55
Time taken for Quick Sort: 0.000002 seconds

Enter the number of elements: 4

Enter 4 elements:
23 7 6 5
Sorted array:
5 6 7 23
Time taken for Quick Sort: 0.000001 seconds

Enter the number of elements: 3

Enter 3 elements:
78 6 5
Sorted array:
5 6 78
Time taken for Quick Sort: 0.000002 seconds
MERGE SORT

PROGRAM:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void mergeSort(int arr[], int l, int r);
void merge(int arr[], int l, int m, int r);
int main() {
int n, i;
clock_t start, end;
double time_taken;
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements:\n", n);
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
start = clock();
mergeSort(arr, 0, n-1);
end = clock();
printf("Sorted array:\n");
for(i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
time_taken = ((double)(end - start))/CLOCKS_PER_SEC;
printf("\nTime taken for Merge Sort: %f seconds\n", time_taken);
return 0;
}
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);
}
}

OUTPUT:

Enter the number of elements: 5

Enter 5 elements:
35621
Sorted array:
12356
Time taken for Merge Sort: 0.000010 seconds

Enter the number of elements: 4

Enter 4 elements:
4367
Sorted array:
3467
Time taken for Merge Sort: 0.000002 seconds

Enter the number of elements: 3

Enter 3 elements:
274
Sorted array:
247
Time taken for Merge Sort: 0.000003 seconds
N QUEENS PROBLEM

PROGRAM:

#include <stdio.h>
#include <stdbool.h>
#define MAX_N 10
int N;
bool isSafe(int board[MAX_N][MAX_N], int row, int col) {
int i, j;
for (i = 0; i < col; i++)
if (board[row][i])
return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;
return true;
}
bool solveNQueensUtil(int board[MAX_N][MAX_N], int col) {
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQueensUtil(board, col + 1))
return true;
board[i][col] = 0; // Backtrack
}
}
return false;
}
void printSolution(int board[MAX_N][MAX_N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf("%d ", board[i][j]);
printf("\n");
}
}
void solveNQueens() {
printf("Enter the value of N: ");
 scanf("%d", &N);
int board[MAX_N][MAX_N] = { {0} };
if (solveNQueensUtil(board, 0) == false) {
printf("Solution does not exist");
return;
}
printSolution(board);
}
int main() {
solveNQueens();
return 0;
}

OUTPUT:

Enter the value of N: 6

000100
100000
000010
010000
000001
001000
TSP

PROGRAM:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
#define N 4
int graph[N][N] = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
int min(int a, int b) {
return (a < b) ? a : b;
}
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void permute(int* arr, int l, int r, int* min_cost, int* optimal_path) {
if (l == r) {
int cost = 0;
for (int i = 0; i < N - 1; i++)
cost += graph[arr[i]][arr[i + 1]];
cost += graph[arr[N - 1]][arr[0]];
if (cost < *min_cost) {
*min_cost = cost;
for (int i = 0; i < N; i++)
optimal_path[i] = arr[i];
}
} else {
for (int i = l; i <= r; i++) {
swap(&arr[l], &arr[i]);
permute(arr, l + 1, r, min_cost, optimal_path);
swap(&arr[l], &arr[i]);
}
}
}
void printPath(int* path, int cost) {
 printf("Path: ");
for (int i = 0; i < N; i++)
printf("%d -> ", path[i]);
printf("%d\n", path[0]);
printf("Cost: %d\n", cost);
}
void bruteForceTSP() {
int path[N];
for (int i = 0; i < N; i++)
path[i] = i;
int min_cost = INT_MAX;
int optimal_path[N];
permute(path, 0, N - 1, &min_cost, optimal_path);
printf("Solution:\n");
printPath(optimal_path, min_cost);
}
void nearestNeighborTSP() {
int path[N];
bool visited[N];
for (int i = 0; i < N; i++)
visited[i] = false;
int start = 0;
path[0] = start;
visited[start] = true;
int total_cost = 0;
for (int i = 1; i < N; i++) {
int min_cost = INT_MAX;
int nearest_city;
for (int j = 0; j < N; j++) {
if (!visited[j] && graph[start][j] < min_cost) {
min_cost = graph[start][j];
nearest_city = j;
}
}
path[i] = nearest_city;
visited[nearest_city] = true;
total_cost += min_cost;
start = nearest_city;
}
total_cost += graph[path[N - 1]][path[0]];
printf("Nearest Neighbor Solution:\n");
printPath(path, total_cost);
}
int main() {
 bruteForceTSP();
nearestNeighborTSP();
return 0;
}

OUTPUT:

Solution:
Path: 0 -> 1 -> 3 -> 2 -> 0
Cost: 80
Nearest Neighbor Solution:
Path: 0 -> 1 -> 3 -> 2 -> 0
Cost: 80
K’TH SMALLEST NUMBER

PROGRAM:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 100
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;

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

if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
int randomPartition(int arr[], int low, int high) {
srand(time(NULL));
int random = low + rand() % (high - low);
int temp = arr[random];
arr[random] = arr[high];
arr[high] = temp;
return partition(arr, low, high);
}
int kthSmallest(int arr[], int low, int high, int k) {
if (k > 0 && k <= high - low + 1) {
int pos = randomPartition(arr, low, high);
if (pos - low == k - 1)
return arr[pos];
if (pos - low > k - 1)
return kthSmallest(arr, low, pos - 1, k);
return kthSmallest(arr, pos + 1, high, k - pos + low - 1);
}
return -1;
}
int main() {
int arr[MAX_SIZE], n, k;
printf("Enter the number of elements in the array: ");
scanf("%d", &n);
printf("Enter the elements of the array: ");
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("Enter the value of k: ");
scanf("%d", &k);
if (k > n) {
printf("Invalid value of k\n");
return 0;
}
printf("K'th smallest element is %d\n", kthSmallest(arr, 0, n - 1, k));
return 0;
}

OUTPUT:

Enter the number of elements in the array: 5

Enter the elements of the array: 45 78 67 23 4
Enter the value of k: 3
K'th smallest element is 45