array LL insertion

arrayLL.c

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

#define MAX_N 10000

typedef struct Node {
    int data;
    struct Node *next;
} Node;

void insert_array_sorted(int *arr, int *size, int value, int max_n) {
    if (*size >= max_n) {
        return;
    }

    int i;
    for (i = *size - 1; i >= 0 && arr[i] > value; i--) {
        arr[i + 1] = arr[i];
    }
    arr[i + 1] = value;
    (*size)++;
}

void print_array(int *arr, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d%s", arr[i], (i == size - 1) ? "" : " ");
    }
}

void free_list(Node *head) {
    Node *current = head;
    Node *next;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
}

void print_list(Node *head) {
    Node *current = head;
    while (current != NULL) {
        printf("%d%s", current->data, (current->next == NULL) ? "" : " ");
        current = current->next;
    }
}

Node *insert_list_sorted(Node *head, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        return head;
    }
    newNode->data = value;
    newNode->next = NULL;

    if (head == NULL || head->data >= value) {
        newNode->next = head;
        return newNode;
    }

    Node *current = head;
    while (current->next != NULL && current->next->data < value) {
        current = current->next;
    }
    newNode->next = current->next;
    current->next = newNode;
    return head;
}

void generate_random_elements(int N, int *elements) {
    for (int i = 0; i < N; i++) {
        elements[i] = rand() % 10001;
    }
}

void run_single_test(int N, int *elements) {
    clock_t start_time, end_time;
    double time_taken_ms;

    int *array = (int *)malloc(N * sizeof(int));
    if (array == NULL) return;
    int array_size = 0;

    start_time = clock();
    for (int i = 0; i < N; i++) {
        insert_array_sorted(array, &array_size, elements[i], N);
    }
    end_time = clock();
    time_taken_ms = ((double)(end_time - start_time)) / CLOCKS_PER_SEC * 1000.0;
    print_array(array, array_size);
    printf("\t%.3f ms", time_taken_ms);
    printf("\n");
    free(array);

    Node *head = NULL;
    start_time = clock();
    for (int i = 0; i < N; i++) {
        head = insert_list_sorted(head, elements[i]);
    }
    end_time = clock();
    time_taken_ms = ((double)(end_time - start_time)) / CLOCKS_PER_SEC * 1000.0;
    print_list(head);
    printf("\t%.3f ms", time_taken_ms);
    printf("\n");
    free_list(head);
}

void run_timing_experiment(int N, double *avg_array, double *avg_list) {
    const int num_runs = 6;
    double total_array_time = 0.0;
    double total_list_time = 0.0;

    int *elements = (int *)malloc(N * sizeof(int));
    if (elements == NULL) return;

    for (int run = 0; run < num_runs; run++) {
        generate_random_elements(N, elements);
        clock_t start, end;
        double time_taken;

        int *array = (int *)malloc(N * sizeof(int));
        if (array == NULL) goto cleanup;
        int array_size = 0;
        start = clock();
        for (int i = 0; i < N; i++) {
            insert_array_sorted(array, &array_size, elements[i], N);
        }
        end = clock();
        time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
        total_array_time += time_taken;
        free(array);

        Node *head = NULL;
        start = clock();
        for (int i = 0; i < N; i++) {
            head = insert_list_sorted(head, elements[i]);
        }
        end = clock();
        time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
        total_list_time += time_taken;
        free_list(head);
    }

    *avg_array = (total_array_time / num_runs) * 1000.0;
    *avg_list = (total_list_time / num_runs) * 1000.0;

cleanup:
    free(elements);
}

int main(int argc, char *argv[]) {
    srand((unsigned int)time(NULL));

    if (argc == 2) {
        int N = atoi(argv[1]);
        if (N <= 0 || N > MAX_N) {
            fprintf(stderr, "Invalid N. Please use a positive integer up to %d.\n", MAX_N);
            return 1;
        }

        int *elements = (int *)malloc(N * sizeof(int));
        if (elements == NULL) return 1;
        generate_random_elements(N, elements);
        run_single_test(N, elements);
        free(elements);
        return 0;

    } else if (argc == 1) {
        int N_values[] = {100, 500, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000};
        int num_N_values = sizeof(N_values) / sizeof(N_values[0]);

        printf("--- Performance Comparison (Average of 6 Runs) ---\n");
        printf("N\t\tArray (ms)\t\tLinked List (ms)\n");
        printf("--------------------------------------------------\n");

        for (int i = 0; i < num_N_values; i++) {
            int N = N_values[i];
            double avg_array, avg_list;
            run_timing_experiment(N, &avg_array, &avg_list);
            printf("%d\t\t%.3f\t\t\t%.3f\n", N, avg_array, avg_list);
        }

        return 0;

    } else {
        fprintf(stderr, "Usage: %s [N]\n", argv[0]);
        fprintf(stderr, "  If N is provided, runs a single test for that N (Part I & II).\n");
        fprintf(stderr, "  If no argument is provided, runs the full timing suite (Part III).\n");
        return 1;
    }
}