Sorting Algorithms: Quick Sort, Merge Sort, Selection Sort & N-Queens Problem
Sorting Algorithms in C: Quick Sort, Merge Sort, and Selection Sort
Quick Sort
Here’s a C implementation of the Quick Sort algorithm along with code to measure its execution time:
#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;
}
Visualizing Quick Sort Time Complexity with Matplotlib
You can visualize the time complexity of Quick Sort using Python’s Matplotlib library. Here’s an example:
import matplotlib.pyplot as plt
# Example data collected (replace with your actual measurements)
n_values = [10000, 20000, 30000, 35000, 50000]
time_taken = [0.0000, 0.015000, 0.011000, 0.003000, 0.015000]
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()
Merge Sort
void mergeSort(int arr[], int left, int right)
{
if (left {
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 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 {
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 {
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
#include
#include
// Function to print the solution
void printSolution(int **board, int N)
{
for (int i = 0; i {
for (int j = 0; 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 {
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 {
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 {
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 {
board[i] = (int *)malloc(N * sizeof(int));
for (int j = 0; j {
board[i][j] = 0;
}
}
if (!solveNQUtil(board, N, 0))
{
printf(“Solution does not exist\n”);
for (int i = 0; i {
free(board[i]);
}
free(board);
return false;
}
printSolution(board, N);
for (int i = 0; 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
#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 {
ratio[i] = (double)p[i] / w[i];
}
for (i = 0; i {
for (int j = i + 1; j {
if (ratio[i] {
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 {
if (currentWeight + w[i] {
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 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 scanf(“%d”, &w[i]);
printf(“Enter the objects’ profits: “);
for (i = 0; i scanf(“%d”, &p[i]);
printf(“Enter the maximum capacity: “);
scanf(“%d”, &m);
greedyKnapsack(n, w, p, m);
return 0;
}
8)#include
#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 if(x[i]==1)
printf(“%d “,s[i]);
printf(“\n”);
}
else if(p+s[k]+s[k+1] sumofsub(p+s[k],k+1,r
-s[k]);
if((p+r
-s[k]>=d) && (p+s[k+1] {
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 scanf(“%d”,&s[i]);
printf(“\nEnter the max subset value:”);
scanf(“%d”,&d);
for(i=1; i sum=sum+s[i];
if(sumd)
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 {
min_idx = i;
for (j = i+1; j {
if (arr[j] {
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 {
arr[i] = rand() % 10000;
}
}
int main()
{
int n;
printf(“Enter number of elements: “);
scanf(“%d”, &n);
if (n {
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()