Analysis of Sorting Algorithms: Quick Sort, Merge Sort, and Selection Sort
10)
#include <stdio.H>
#include <stdlib.H>
#include <time.H>
// Function to swap two elements
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
// Partition function for Quick Sort
int partition(int arr[], int low, int high)
{
int pivot = arr[high]; // Pivot element
int i = (low – 1); // Index of smaller element
for (int j = low; j <= high – 1; j++)
{
if (arr[j] < pivot)
{
i++; // Increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// Quick Sort function
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
// Recursively sort elements before and after partition
quickSort(arr, low, pi – 1);
quickSort(arr, pi + 1, high);
}
}
// Function to generate random numbers
void generateRandomNumbers(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
arr[i] = rand() % 100000; // Generate random numbers between 0 and 99999
}
}
int main()
{
int n;
printf(“Enter number of elements: “);
scanf(“%d”, &n); // Read the number of elements from the user
if (n <= 5000)
{
printf(“Please enter a value greater than 5000\n”);
return 1; // Exit if the number of elements is not greater than 5000
}
// Allocate memory for the array
int *arr = (int *)malloc(n * sizeof(int));
if (arr == NULL)
{
printf(“Memory allocation failed\n”);
return 1; // Exit if memory allocation fails
}
// Generate random numbers and store them in the array
generateRandomNumbers(arr, n);
// Measure the time taken to sort the array
clock_t start = clock();
quickSort(arr, 0, n – 1);
clock_t end = clock();
// Calculate and print the time taken to sort the array
double time_taken = ((double)(end – start)) / CLOCKS_PER_SEC;
printf(“Time taken to sort %d elements: %f seconds\n”, n, time_taken);
// Free the allocated memory
free(arr);
return 0;
}
import matplotlib.Pyplot as plt
# Example data collected
n_values = [10000, 20000, 30000, 35000, 50000]
time_taken = [0.0000, 0.015000, 0.011000, 0.003000, 0.015000] # replace with actual times recorded
plt.Plot(n_values, time_taken, marker=’o’)
plt.Title(‘Quick Sort Time Complexity’)
plt.Xlabel(‘Number of Elements (n)’)
plt.Ylabel(‘Time taken (seconds)’)
plt.Grid(True)
plt.Show()
11)
#include <stdio.H>
#include <stdlib.H>
#include <time.H>
// Function to merge two sorted arrays
void merge(int arr[], int left, int mid, int right)
{
int i, j, k;
int n1 = mid – left + 1;
int n2 = right – mid;
int *L = (int *)malloc(n1 * sizeof(int));
int *R = (int *)malloc(n2 * sizeof(int));
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
i = 0;
j = 0;
k = left;
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++;
}
free(L);
free(R);
}
// Function to implement Merge Sort
void mergeSort(int arr[], int left, int right)
{
if (left < right)
{
int mid = left + (right – left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void generateRandomArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
arr[i] = rand() % 100000; // Generate random integers between 0 and 99999
}
int main()
{
int n;
printf(“Enter the number of elements: “);
scanf(“%d”, &n);
if (n <= 5000)
{
printf(“Please enter a value greater than 5000\n”);
return 1;
}
int *arr = (int *)malloc(n * sizeof(int));
if (arr == NULL)
{
printf(“Memory allocation failed\n”);
return 1; // Exit if memory allocation fails
}
generateRandomArray(arr, n);
clock_t start = clock();
for (int i = 0; i < 1000; i++)
{
mergeSort(arr, 0, n – 1);
}
clock_t end = clock();
double time_taken = ((double)(end – start)) / CLOCKS_PER_SEC / 1000.0;
printf(“Time taken to sort %d elements: %f seconds\n”, n, time_taken);
free(arr);
return 0;
}
12)
#include <stdio.H>
#include <stdlib.H>
#include <stdbool.H>
// Function to print the solution
void printSolution(int **board, int N)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
printf(“%s “, board[i][j] ? “Q” : “#”);
}
printf(“\n”);
}
}
bool isSafe(int **board, int 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 solveNQUtil(int **board, int N, int col)
{
if (col >= N)
{
return true;
}
for (int i = 0; i < N; i++)
{
if (isSafe(board, N, i, col))
{
board[i][col] = 1;
if (solveNQUtil(board, N, col + 1))
{
return true;
}
board[i][col] = 0; // BACKTRACK
}
}
return false;
}
bool solveNQ(int N)
{
int **board = (int **)malloc(N * sizeof(int *));
for (int i = 0; i < N; i++)
{
board[i] = (int *)malloc(N * sizeof(int));
for (int j = 0; j < N; j++)
{
board[i][j] = 0;
}
}
if (!SolveNQUtil(board, N, 0))
{
printf(“Solution does not exist\n”);
for (int i = 0; i < N; i++)
{
free(board[i]);
}
free(board);
return false;
}
printSolution(board, N);
for (int i = 0; i < N; i++)
{
free(board[i]);
}
free(board);
return true;
}
int main()
{
int N;
printf(“Enter the number of queens: “);
scanf(“%d”, &N);
solveNQ(N);
return 0;
}
7)#include <stdio.H>
#define MAX 50
int p[MAX], w[MAX], x[MAX];
double maxprofit;
int n, m, i;
void greedyKnapsack(int n, int w[], int p[], int m)
{
double ratio[MAX];
for (i = 0; i < n; i++)
{
ratio[i] = (double)p[i] / w[i];
}
for (i = 0; i < n – 1; i++)
{
for (int j = i + 1; j < n; j++)
{
if (ratio[i] < ratio[j])
{
double temp = ratio[i];
ratio[i] = ratio[j];
ratio[j] = temp;
int temp2 = w[i];
w[i] = w[j];
w[j] = temp2;
temp2 = p[i];
p[i] = p[j];
p[j] = temp2;
}
}
}
int currentWeight = 0;
maxprofit = 0.0;
for (i = 0; i < n; i++)
{
if (currentWeight + w[i] <= m)
{
x[i] = 1; // Item i is selected
currentWeight += w[i];
maxprofit += p[i];
}
else
{
x[i] = (m – currentWeight) / (double)w[i];
maxprofit += x[i] * p[i];
break;
}
}
printf(“Optimal solution for greedy method: %.1f\n”, maxprofit);
printf(“Solution vector for greedy method: “);
for (i = 0; i < n; i++)
printf(“%d\t”, x[i]);
}
int main()
{
printf(“Enter the number of objects: “);
scanf(“%d”, &n);
printf(“Enter the objects’ weights: “);
for (i = 0; i < n; i++)
scanf(“%d”, &w[i]);
printf(“Enter the objects’ profits: “);
for (i = 0; i < n; i++)
scanf(“%d”, &p[i]);
printf(“Enter the maximum capacity: “);
scanf(“%d”, &m);
greedyKnapsack(n, w, p, m);
return 0;
}
8)#include<stdio.H>
#define MAX 10
int s[MAX],x[MAX],d;
void sumofsub(int p,int k,int r)
{
int i;
x[k]=1;
if((p+s[k])==d)
{
for(i=1; i<=k; i++)
if(x[i]==1)
printf(“%d “,s[i]);
printf(“\n”);
}
else if(p+s[k]+s[k+1]<=d)
sumofsub(p+s[k],k+1,r
-s[k]);
if((p+r
-s[k]>=d) && (p+s[k+1]<=d))
{
x[k]=0;
sumofsub(p,k+1,r
-s[k]);
}
}
int main()
{
int i,n,sum=0;
printf(“\nEnter the n value:”);
scanf(“%d”,&n);
printf(“\nEnter the set in increasing order:”);
for(i=1; i<=n; i++)
scanf(“%d”,&s[i]);
printf(“\nEnter the max subset value:”);
scanf(“%d”,&d);
for(i=1; i<=n; i++)
sum=sum+s[i];
if(sum<d || s[1]>d)
printf(“\nNo subset possible”);
else
sumofsub(0,1,sum);
return 0;
}
9)#include #include #include
// Function to perform selection sort on an array
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
for (i = 0; i < n-1; i++)
{
min_idx = i;
for (j = i+1; j < n; j++)
{
if (arr[j] < arr[min_idx])
{
min_idx = j;
}
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
void generateRandomNumbers(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
arr[i] = rand() % 10000;
}
}
int main()
{
int n;
printf(“Enter number of elements: “);
scanf(“%d”, &n);
if (n <= 5000)
{
printf(“Please enter a value greater than 5000\n”);
return 1;
}
int *arr = (int *)malloc(n * sizeof(int));
if (arr == NULL)
{
printf(“Memory allocation failed\n”);
return 1; // Exit if memory allocation fails
}
generateRandomNumbers(arr, n);
clock_t start = clock();
selectionSort(arr, n);
clock_t end = clock();
// Calculate and print the time taken to sort the array
double time_taken = ((double)(end – start)) / CLOCKS_PER_SEC;
printf(“Time taken to sort %d elements: %f seconds\n”, n, time_taken);
// Free the allocated memory
free(arr);
return 0;
}
import matplotlib.Pyplot as plt
# data collected
n_values = [6000, 7000, 8000, 9000, 10000]
time_taken = [0.031000, 0.034000, 0.047000, 0.052000, 0.077000] # replace with actual times recorded
plt.Plot(n_values, time_taken, marker=’o’)
plt.Title(‘Selection Sort Time Complexity’)
plt.Xlabel(‘Number of Elements (n)’)
plt.Ylabel(‘Time taken (seconds)’)
plt.Grid(True)
plt.Show()