fork download
copy 
  1. #include <assert.h>  // assert
  2. #include <stddef.h>  // size_t
  3. #include <stdlib.h>  // qsort, malloc, realloc, free, exit
  4. #include <stdio.h>   // printf, scanf
  5. #include <string.h>  // memcpy
  6.  
  7. struct vec{
  8.     void *data;
  9.     size_t size;
  10.     size_t capacity;
  11.     size_t elem_size;
  12. };
  13.  
  14. int vec_init(struct vec *v, size_t elem_size){
  15.     v->elem_size = elem_size;
  16.     v->size = 0;
  17.     v->capacity = 4;
  18.     v->data = malloc(v->capacity * elem_size);
  19.     if(v->data == NULL){
  20.         v->capacity = 0;
  21.         return 0;
  22.     }
  23.     return 1;
  24. }
  25.  
  26. void vec_free(struct vec *v){
  27.     free(v->data);
  28.     v->data = NULL;
  29.     v->size = 0;
  30.     v->capacity = 0;
  31. }
  32.  
  33. void *vec_get(struct vec *v, size_t i){
  34.     assert(i < v->size);
  35.     return (char *)v->data + i * v->elem_size;
  36. }
  37.  
  38. int vec_push(struct vec *v, void *elem){
  39.     if(v->size >= v->capacity){
  40.         size_t new_capacity = v->capacity * 2;
  41.         void *new_data = realloc(v->data, new_capacity * v->elem_size);
  42.         if(new_data == NULL){
  43.             return 0;
  44.         }
  45.         v->data = new_data;
  46.         v->capacity = new_capacity;
  47.     }
  48.     memcpy((char *)v->data + v->size * v->elem_size, elem, v->elem_size);
  49.     v->size++;
  50.     return 1;
  51. }
  52.  
  53. void dvq(void *ptr, size_t l, size_t r, size_t elem_size, int (*cmp)(const void *, const void *), struct vec *pom){
  54.     if(l >= r) return;
  55.  
  56.     size_t mid = (l + r) / 2;
  57.     dvq(ptr, l, mid, elem_size, cmp, pom); dvq(ptr, mid + 1, r, elem_size, cmp, pom);
  58.  
  59.     size_t i = l, j = mid + 1, akt = l;
  60.     while(i <= mid && j <= r){
  61.         void *ei = (char *)ptr + i * elem_size;
  62.         void *ej = (char *)ptr + j * elem_size;
  63.         if(cmp(ei, ej) <= 0){
  64.             memcpy((char *)pom->data + akt * elem_size, ei, elem_size);
  65.             akt++; i++;
  66.         }else{
  67.             memcpy((char *)pom->data + akt * elem_size, ej, elem_size);
  68.             akt++; j++;
  69.         }
  70.     }
  71.     while(i <= mid){
  72.         memcpy((char *)pom->data + akt * elem_size, (char *)ptr + i * elem_size, elem_size);
  73.         akt++; i++;
  74.     }
  75.     while(j <= r){
  76.         memcpy((char *)pom->data + akt * elem_size, (char *)ptr + j * elem_size, elem_size);
  77.         akt++; j++;
  78.     }
  79.  
  80.     for(size_t k = l; k <= r; k++) memcpy((char *)ptr + k * elem_size, (char *)pom->data + k * elem_size, elem_size);
  81. }
  82.  
  83. void msort(void *ptr, size_t ile, size_t size, int (*cmp)(const void *, const void *)){
  84.     if(ile <= 1) return;
  85.  
  86.     struct vec pom;
  87.     if(!vec_init(&pom, size)) exit(1);
  88.  
  89.     while(pom.capacity < ile){
  90.         size_t new_cap = pom.capacity * 2;
  91.         void *new_data = realloc(pom.data, new_cap * size);
  92.         if(new_data == NULL){
  93.             vec_free(&pom);
  94.             exit(1);
  95.         }
  96.         pom.data = new_data;
  97.         pom.capacity = new_cap;
  98.     }
  99.     pom.size = ile;
  100.  
  101.     dvq(ptr, 0, ile - 1, size, cmp, &pom);
  102.  
  103.     vec_free(&pom);
  104. }
  105.  
  106. struct pair{
  107.     int first;
  108.     int second;
  109. };
  110.  
  111. int cmp_int(const void *a, const void *b){
  112.     int ia = *(const int *)a;
  113.     int ib = *(const int *)b;
  114.     if(ia < ib) return -1;
  115.     if(ia > ib) return 1;
  116.  
  117.  
  118.     return 0;
  119. }
  120.  
  121.  
  122.  
  123.  
  124.  
  125. int cmp_char(const void *a, const void *b){
  126.     char ca = *(const char *)a;
  127.     char cb = *(const char *)b;
  128.  
  129.     if(ca < cb) return -1;
  130.     if(ca > cb) return 1;
  131.     return 0;
  132. }
  133.  
  134.  
  135.  
  136. int cmp_pair(const void *a, const void *b){
  137.     const struct pair *pa = a;
  138.     const struct pair *pb = b;
  139.  
  140.     if(pa->first < pb->first) return -1;
  141.     if(pa->first > pb->first) return 1;
  142.     return 0;
  143. }
  144.  
  145.  
  146.  
  147.  
  148. int main(void){
  149.     int inty[] = {5, 2, 9, 1, 5, 6};
  150.     size_t inty_ile = sizeof(inty) / sizeof(inty[0]);
  151.     msort(inty, inty_ile, sizeof(int), cmp_int);
  152.     printf("inty: ");
  153.     for(size_t i = 0; i < inty_ile; i++) printf("%d ", inty[i]);
  154.     printf("\n");
  155.  
  156.  
  157.     char chary[] = {'z', 'a', 'k', 'b', 'm'};
  158.     size_t chary_ile = sizeof(chary) / sizeof(chary[0]);
  159.     msort(chary, chary_ile, sizeof(char), cmp_char);
  160.     printf("chary: ");
  161.     for(size_t i = 0; i < chary_ile; i++) printf("%c ", chary[i]);
  162.     printf("\n");
  163.  
  164.  
  165.  
  166.     struct pair pary[] = {{2, 1}, {1, 2}, {2, 2}, {1, 1}};
  167.     size_t pary_ile = sizeof(pary) / sizeof(pary[0]);
  168.     msort(pary, pary_ile, sizeof(struct pair), cmp_pair);
  169.     printf("pary (stabilne): ");
  170.     for(int i = 0; i < 4; i++) printf("(%d,%d), ", pary[i].first, pary[i].second);
  171.     printf("\n");
  172.  
  173.     return 0;
  174. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
inty: 1 2 5 5 6 9 
chary: a b k m z 
pary (stabilne): (1,2), (1,1), (2,1), (2,2),
https://ideone.com/xJK7WW
language:
C (gcc 8.3)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!