Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #define LEN 10
- void merge(int *V, size_t left, size_t mid, size_t right);
- void merge_sort(int *V, size_t i, size_t j);
- void print_arr(int *V, size_t length);
- int main(void) {
- int arr[LEN] = {
- 4, 6, 10, 10, 1, 9, 11, 15, -1, 1
- };
- printf("Unsorted:\n");
- print_arr(arr, LEN);
- merge_sort(arr, 0, LEN - 1);
- printf("\nSorted:\n");
- print_arr(arr, LEN);
- return 0;
- }
- void print_arr(int *V, size_t length) {
- printf("[ ");
- for (size_t i = 0; i < length; i++)
- printf("%d ", V[i]);
- printf("]");
- }
- void merge(int *V, size_t left, size_t mid, size_t right) {
- int *T = (int *)malloc(sizeof(int) * (right - left + 1));
- size_t i = left;
- size_t j = mid + 1;
- size_t t_index = 0;
- // Finchè non ho finito almeno una delle 2 fusioni
- // T(n) = O(n)
- while (i <= mid && j <= right) {
- if (V[i] < V[j]) {
- T[t_index++] = V[i++];
- } else {
- T[t_index++] = V[j++];
- }
- }
- // Ciò che rimane del left
- // T(n) = O(n)
- while (i <= mid) {
- T[t_index++] = V[i++];
- }
- // Ciò che rimane del right
- // T(n) = O(n)
- while (j <= right) {
- T[t_index++] = V[j++];
- }
- // Copiamo su V
- for (size_t copy_i = left; copy_i <= right; copy_i++) {
- V[copy_i] = T[copy_i - left];
- }
- }
- // T(N) = 2T(n/2) + O(n)
- // 2nd MT = n^logb(a)*log2n
- void merge_sort(int *V, size_t i, size_t j) {
- if (i >= j)
- return;
- size_t mid = i + (j - i) / 2;
- // O(T(n / 2))
- merge_sort(V, i, mid);
- // O(T(n / 2))
- merge_sort(V, mid + 1, j);
- // O(n)
- merge(V, i, mid, j);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement