Advertisement
AliAbdulKareem

Merge Sort + dynamic array of integers impl

Jan 29th, 2022
1,515
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef enum vec_state
  5. {
  6.     vec_error = 0,
  7.     vec_init  = 1,
  8.     vec_free  = 2,  
  9.  
  10. }vec_state;
  11.  
  12. typedef struct vec_int
  13. {
  14.     int* mem_pool;
  15.     size_t capacity;
  16.     size_t size;    
  17.     vec_state state;
  18. }vec_int;
  19.  
  20. vec_int vec_int_create(size_t capacity)
  21. {
  22.     vec_int vec;
  23.     if(capacity < 2) capacity = 2;
  24.     int* mem_pool = (int*) malloc(sizeof(int) * capacity);
  25.     if(mem_pool == NULL)
  26.     {
  27.         printf("init vector malloc failed...\n");
  28.         vec.mem_pool = NULL;
  29.         vec.size = 0;
  30.         vec.capacity = 0;
  31.         vec.state = vec_error;
  32.         return vec;
  33.     }
  34.     vec.mem_pool = mem_pool;
  35.     vec.size = 0;
  36.     vec.capacity = capacity;
  37.     vec.state = vec_init;
  38.     return vec;
  39. }
  40.  
  41. static void vec_int_grow(vec_int* vec)
  42. {
  43.     size_t new_capacity = (vec->capacity * 3) / 2;
  44.     int* new_pool = (int*) malloc(sizeof(int) * new_capacity);
  45.     if(new_pool == NULL)
  46.     {
  47.         printf("Growing int vec failed\n ");
  48.         return;
  49.     }
  50.     for(size_t i = 0, n = vec->size; i < n; ++i)
  51.     {
  52.         new_pool[i] = vec->mem_pool[i];
  53.     }
  54.     free(vec->mem_pool);
  55.     vec->mem_pool = new_pool;
  56.     vec->capacity = new_capacity;
  57. }
  58.  
  59. void vec_int_add(vec_int* vec, int elem)
  60. {
  61.     if(vec->size >= vec->capacity)
  62.     {
  63.         vec_int_grow(vec);
  64.     }
  65.     vec->mem_pool[vec->size] = elem;
  66.     vec->size++;
  67. }
  68.  
  69. void vec_int_print(vec_int* vec)
  70. {
  71.     for(size_t i = 0, n = vec->size; i < n; ++i)
  72.     {
  73.         printf("%d ", vec->mem_pool[i]);
  74.     }
  75.     printf("\n");
  76. }
  77.  
  78. void vec_int_free(vec_int* vec)
  79. {
  80.     if(vec->state != vec_init)
  81.     {
  82.         printf("vec int not initialized... \n");
  83.         return;
  84.     }
  85.     free(vec->mem_pool);
  86.     vec->size = vec->capacity = 0;
  87.     vec->state = vec_free;
  88. }
  89.  
  90. static void move_bytes(void* d,  void* s, size_t byte_count)
  91. {
  92.     unsigned char* dest = (unsigned char*) d;
  93.     unsigned char* source = (unsigned char*) s;
  94.     while(byte_count--) *dest++ = *source++ ;
  95. }
  96.  
  97. void move_right(void* mem_begin, size_t index, size_t elem_size, void* mem_end)
  98. {
  99.     unsigned char* start = (unsigned char*)mem_begin + (index * elem_size);
  100.  
  101.     unsigned char* end =  mem_end;
  102.    
  103.     while(end != start )
  104.     {
  105.       move_bytes(end, end - elem_size, elem_size);
  106.       end -= elem_size;
  107.     }
  108. }
  109.  
  110. void move_left(void* mem_begin, size_t index, size_t elem_size, void* mem_end)
  111. {
  112.     unsigned char* start = (unsigned char*)mem_begin + (index * elem_size);
  113.  
  114.     unsigned char* end =  mem_end;
  115.     while(end != start)
  116.     {
  117.         move_bytes(start ,start + elem_size, elem_size);
  118.         start += elem_size;
  119.     }
  120.    
  121. }
  122.  
  123. void vec_int_insert(vec_int * vec, size_t index, int elem)
  124. {
  125.     if(vec->size >= vec->capacity)
  126.     {
  127.         vec_int_grow(vec);
  128.     }
  129.     move_right(vec->mem_pool, index, sizeof(int), & (vec->mem_pool[vec->size]) );
  130.     vec->size++;
  131.     vec->mem_pool[index] = elem;
  132.    
  133. }
  134.  
  135. void vec_int_delete(vec_int* vec, size_t index)
  136. {
  137.     if(vec->size == 0)
  138.     {
  139.         printf("empty vec... returning\n");
  140.         return;
  141.     }
  142.     move_left(vec->mem_pool, index, sizeof(int), &(vec->mem_pool[vec->size -1 ]));
  143.     vec->size--;
  144. }
  145.  
  146. void vec_int_set(vec_int* vec, int index, int elem)
  147. {
  148.     if(index >= (int)vec->size)
  149.     {
  150.         if(index >= (int)vec->capacity)
  151.         {
  152.             printf("this index is not reserved yet\n");
  153.         }
  154.         else
  155.         {
  156.             printf("this index is reserved but not yet added\n");
  157.         }
  158.         return;
  159.        
  160.     }
  161.  
  162.     else if(index < 0)
  163.     {
  164.         printf("passed a negative index\n");
  165.         return;
  166.     }
  167.     else
  168.     {
  169.         vec->mem_pool[index] = elem;
  170.     }
  171.  
  172. }
  173.  
  174. int vec_int_get(vec_int* vec, int index)
  175. {
  176.     if(index < 0)
  177.     {
  178.         printf("passed a negative index\n");
  179.         return -1;
  180.     }
  181.     else if(index >= (int)vec->size)
  182.     {
  183.         printf("this element is outside the boundary of access\n");
  184.         return -1;
  185.     }
  186.     else
  187.     {
  188.         return vec->mem_pool[index];
  189.     }
  190.  
  191. }
  192.  
  193. vec_int vec_int_view(vec_int vec, size_t start_view_index, size_t size)
  194. {
  195.     vec.mem_pool = vec.mem_pool + start_view_index;
  196.     vec.size = size;
  197.     return vec;
  198. }
  199.  
  200. vec_int merge(vec_int left, vec_int right)
  201. {
  202.     size_t n = left.size + right.size ;
  203.  
  204.     vec_int v = vec_int_create(n);
  205.  
  206.     size_t i,j,k;
  207.  
  208.     for(i = 0, j = 0; i < left.size && j < right.size; )
  209.     {
  210.         if( left.mem_pool[i] > right.mem_pool[j])
  211.         {
  212.             vec_int_add(&v,right.mem_pool[j++]);
  213.         }
  214.         else
  215.         {
  216.             vec_int_add(&v,left.mem_pool[i++]);
  217.         }
  218.     }
  219.  
  220.     if(i == left.size)
  221.     {
  222.         while(j < right.size)
  223.         {
  224.             vec_int_add(&v,right.mem_pool[j++]);
  225.         }
  226.     }
  227.  
  228.     else
  229.     {
  230.         while(i < left.size)
  231.         {
  232.             vec_int_add(&v,left.mem_pool[i++]);
  233.         }
  234.  
  235.     }
  236.    
  237.     i = j = k = 0;
  238.     while(i < left.size)
  239.     {
  240.         left.mem_pool[i++] = v.mem_pool[k++];
  241.     }
  242.     while(j < right.size)
  243.     {
  244.         right.mem_pool[j++] = v.mem_pool[k++];
  245.     }
  246.     vec_int_free(&v);
  247.  
  248.     return vec_int_view(left, 0, left.size + right.size);
  249. }
  250.  
  251. vec_int merge_sort(vec_int vec)
  252. {
  253.     if(vec.size < 2) return vec;
  254.     vec_int left = merge_sort(vec_int_view(vec, 0, vec.size/2));
  255.     vec_int right = merge_sort(vec_int_view(vec, vec.size/2, vec.size - (vec.size/2)));
  256.  
  257.     return merge(left,right);
  258.  
  259. }
  260.  
  261. int main()
  262. {
  263.     vec_int vec = vec_int_create(4);
  264.  
  265.     vec_int_add(&vec,10);
  266.     vec_int_add(&vec,15);
  267.     vec_int_add(&vec,25);
  268.     vec_int_add(&vec,-10);
  269.     vec_int_add(&vec,-17);
  270.     vec_int_add(&vec,-22);
  271.     vec_int_add(&vec,-0);
  272.     vec_int_add(&vec,11);
  273.    
  274.    
  275.     vec_int_insert(&vec,vec.size,17);
  276.     vec_int_insert(&vec,1,0);
  277.    
  278.     vec_int view = vec_int_view(vec,0,vec.size - 0);
  279.     vec_int_print(&vec);
  280.     vec_int_print(&view);
  281.     vec = merge_sort(vec);
  282.     vec_int_print(&vec);
  283.     vec_int_free(&vec);
  284.  
  285. }
  286.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement