#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void selectionSort(int arr[], int n, int* comparisons, int* swaps) {
int i, j, min_idx;
for (i = 0; i < n - 1; i++) {
min_idx = i;
for (j = i + 1; j < n; j++) {
(*comparisons)++;
if (arr[j] < arr[min_idx])
min_idx = j;
}
if (min_idx != i) {
(*swaps)++;
swap(&arr[min_idx], &arr[i]);
}
}
}
void insertionSort(int arr[], int n, int* comparisons, int* swaps) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
(*comparisons)++;
(*swaps)++;
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int n) {
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
void writeFile(int arr[], int n, const char* filename) {
FILE* file = fopen(filename, "w");
if (file == NULL) {
printf("Error opening file!\n");
exit(1);
}
int i;
for (i = 0; i < n; i++)
fprintf(file, "%d\n", arr[i]);
fclose(file);
}
int main() {
const char* inputFileName = "input.txt";
const char* outputFileName = "output.txt";
const int MAX_SAMPLES = 100000;
// Generate random input samples and write them to a file
FILE* inputFile = fopen(inputFileName, "w");
if (inputFile == NULL) {
printf("Error opening input file!\n");
return 1;
}
srand(time(NULL));
int i;
for (i = 0; i < MAX_SAMPLES; i++)
fprintf(inputFile, "%d\n", rand() % 20000 - 10000);
fclose(inputFile);
// Read input samples from the file
FILE* file = fopen(inputFileName, "r");
if (file == NULL) {
printf("Error opening input file!\n");
return 1;
}
int arr[MAX_SAMPLES];
for (i = 0; i < MAX_SAMPLES; i++)
fscanf(file, "%d", &arr[i]);
fclose(file);
// Perform selection sort
int comparisons = 0, swaps = 0;
clock_t start = clock();
selectionSort(arr, MAX_SAMPLES, &comparisons, &swaps);
clock_t end = clock();
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Selection Sort:\n");
printf("Comparisons: %d\n", comparisons);
printf("Swaps: %d\n", swaps);
printf("Time Complexity: %f seconds\n", time_taken);
// Write sorted data to output file
writeFile(arr, MAX_SAMPLES, outputFileName);
// Perform insertion sort
comparisons = 0;
swaps = 0;
start = clock();
insertionSort(arr, MAX_SAMPLES, &comparisons, &swaps);
end = clock();
time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("\nInsertion Sort:\n");
printf("Comparisons: %d\n", comparisons);
printf("Swaps: %d\n", swaps);
printf("Time Complexity: %f seconds\n", time_taken);
// Write sorted data to output file
writeFile(arr, MAX_SAMPLES, outputFileName);
return 0;
}