Untitled
unknown
plain_text
a year ago
2.6 kB
7
Indexable
#include <stdio.h> #include <stdlib.h> #include <time.h> void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; 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++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } void mergeSortIterative(int arr[], int n) { int curr_size, left_start; for (curr_size = 1; curr_size <= n - 1; curr_size = 2 * curr_size) { for (left_start = 0; left_start < n - 1; left_start += 2 * curr_size) { int mid = left_start + curr_size - 1; int right_end = left_start + 2 * curr_size - 1 < n - 1 ? left_start + 2 * curr_size - 1 : n - 1; merge(arr, left_start, mid, right_end); } } } void mergeSortRecursive(int arr[], int l, int r) { if (l < r) { int m = l + (r - l) / 2; mergeSortRecursive(arr, l, m); mergeSortRecursive(arr, m + 1, r); merge(arr, l, m, r); } } void printArray(int A[], int size) { for (int i = 0; i < size; i++) printf("%d ", A[i]); printf("\n"); } int main() { int n; printf("Enter the number of elements: "); scanf("%d", &n); int arr[n]; printf("Enter %d elements:\n", n); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); printf("\nOriginal array: "); printArray(arr, n); // Time measurement for iterative merge sort clock_t start_iterative = clock(); mergeSortIterative(arr, n); clock_t end_iterative = clock(); double time_iterative = ((double)(end_iterative - start_iterative)) / CLOCKS_PER_SEC; printf("\nArray after iterative merge sort: "); printArray(arr, n); printf("Time taken for iterative merge sort: %f seconds\n", time_iterative); // Time measurement for recursive merge sort clock_t start_recursive = clock(); mergeSortRecursive(arr, 0, n - 1); clock_t end_recursive = clock(); double time_recursive = ((double)(end_recursive - start_recursive)) / CLOCKS_PER_SEC; printf("\nArray after recursive merge sort: "); printArray(arr, n); printf("Time taken for recursive merge sort: %f seconds\n", time_recursive); return 0; }
Editor is loading...
Leave a Comment