merge sort P2

#include <stdio.h>

#include <stdlib.h>

#include <time.h>


// Merge two subarrays of arr[].

// First subarray is arr[l..m]

// Second subarray is arr[m+1..r]

void merge(int arr[], int l, int m, int r) {

    int i, j, k;

    int n1 = m - l + 1;

    int n2 = r - m;


    // Create temporary arrays

    int* L = (int*)malloc(n1 * sizeof(int));

    int* R = (int*)malloc(n2 * sizeof(int));


    // Copy data to temporary arrays L[] and R[]

    for (i = 0; i < n1; i++)

        L[i] = arr[l + i];

    for (j = 0; j < n2; j++)

        R[j] = arr[m + 1 + j];


    // Merge the temporary arrays back into arr[l..r]

    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++;

    }


    // Copy the remaining elements of L[], if any

    while (i < n1) {

        arr[k] = L[i];

        i++;

        k++;

    }


    // Copy the remaining elements of R[], if any

    while (j < n2) {

        arr[k] = R[j];

        j++;

        k++;

    }


    free(L);

    free(R);

}


// Merge Sort function

void mergeSort(int arr[], int l, int r) {

    if (l < r) {

        // Same as (l+r)/2, but avoids overflow for large l and r

        int m = l + (r - l) / 2;


        // Sort first and second halves

        mergeSort(arr, l, m);

        mergeSort(arr, m + 1, r);


        // Merge the sorted halves

        merge(arr, l, m, r);

    }

}


int main() {

    int n, i;

    clock_t start, end;

    double cpu_time_used;


    printf("Enter the number of elements (n): ");

    scanf("%d", &n);


    if (n < 5000) {

        printf("Please enter a value of n greater than 5000.\n");

        return 1;

    }


    int* arr = (int*)malloc(n * sizeof(int));

    if (arr == NULL) {

        printf("Memory allocation failed.\n");

        return 1;

    }


    // Generate n random numbers

    srand(time(NULL));

    for (i = 0; i < n; i++) {

        arr[i] = rand() % 10000; // Generating random numbers between 0 to 9999

    }


    // Record the starting time

    start = clock();


    // Perform Merge Sort

    mergeSort(arr, 0, n - 1);


    // Record the ending time

    end = clock();


    // Calculate the time taken

    cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;


    printf("Time taken for sorting: %lf seconds\n", cpu_time_used);


    free(arr); // Free dynamically allocated memory

    return 0;

}


Comments

Post a Comment

Popular posts from this blog

kruskal algo P4

 #include <stdio.h> #include <stdlib.h> #define MAX_EDGES 1000 typedef struct Edge {     int src, dest, weight; } Edge; typedef struct Graph {     int V, E;     Edge edges[MAX_EDGES]; } Graph; typedef struct Subset {     int parent, rank; } Subset; Graph* createGraph(int V, int E) {     Graph* graph = (Graph*) malloc(sizeof(Graph));     graph->V = V;     graph->E = E;     return graph; } int find(Subset subsets[], int i) {     if (subsets[i].parent != i) {         subsets[i].parent = find(subsets, subsets[i].parent);     }     return subsets[i].parent; } void Union(Subset subsets[], int x, int y) {     int xroot = find(subsets, x);     int yroot = find(subsets, y);     if (subsets[xroot].rank < subsets[yroot].rank) {         subsets[xroot].parent = yroot;     } else if (subs...
Read more

topological sort P6

 #include <stdio.h> #include <stdlib.h> #define MAX_VERTICES 100 // Structure to represent a graph typedef struct {     int V;     int** adjMatrix; } Graph; // Function to create a new graph Graph* createGraph(int V) {     Graph* graph = (Graph*)malloc(sizeof(Graph));     graph->V = V;     graph->adjMatrix = (int**)calloc(V, sizeof(int*));     for (int i = 0; i < V; i++) {         graph->adjMatrix[i] = (int*)calloc(V, sizeof(int));     }     return graph; } // Function to add an edge to the graph void addEdge(Graph* graph, int src, int dest) {     graph->adjMatrix[src][dest] = 1; } // Function to perform topological sorting void topologicalSort(Graph* graph) {     int V = graph->V;     int inDegree[MAX_VERTICES] = {0};     int queue[MAX_VERTICES], front = 0, rear = -1;     // Calculate in-degree (number o...
Read more

prim's algo P5

 #include <stdio.h> #include <limits.h> #define V_MAX 100 // Maximum number of vertices // Function to find the vertex with the minimum key value, from the set of vertices not yet included in the MST int minKey(int key[], int mstSet[], int V) {     int min = INT_MAX, min_index;     for (int v = 0; v < V; v++)         if (mstSet[v] == 0 && key[v] < min)             min = key[v], min_index = v;     return min_index; } // Function to print the constructed MST stored in parent[] void printMST(int parent[], int V, int graph[V_MAX][V_MAX]) {     printf("Edge Weight\n");     for (int i = 1; i < V; i++)         printf("%d - %d %d \n", parent[i], i, graph[i][parent[i]]); } // Function to construct and print MST for a graph represented using adjacency matrix representation void primMST(int graph[][V_MAX], int V) {     int parent[V_MAX]...
Read more