fork download 
  1. #include <limits.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <time.h>
  6. #ifndef MYALGORITHMS_H
  7. #define MYALGORITHMS_H
  8.  
  9. #include <stdlib.h>
  10.  
  11. #define STRINGIZE(x) #x
  12.  
  13. /* Bitwise operations */
  14. #define setbit(number, bit) ((number) |= 1 << (bit))
  15. #define clearbit(number, bit) ((number) &= ~(1 << (bit)))
  16. #define switchbit(number, bit) ((number) ^= 1 << (bit))
  17. #define checkbit(number, bit) ((number) & (1 << bit))
  18.  
  19. typedef struct NODE* link;
  20. typedef struct NODE {
  21.     int data;
  22.     link next;
  23. } NODE;
  24.  
  25. char* repr_array(const int* A, const size_t N);
  26. void print_array(const int* A, const size_t N);
  27. void insertion_sort(int* A, const size_t N);
  28. void insertion_sort_2(int* A, const size_t N);
  29. int randrange(unsigned int n);
  30. int random_in_range(unsigned int min, unsigned int max);
  31. int rand_range(unsigned int n);
  32. inline void swap(void* A, void* B, size_t bytes);
  33. void shuffle(void* A, size_t membercount, size_t membersize);
  34. void my_bubble_sort(int* A, const size_t N);
  35. void bubble_sort(int* A, const size_t N);
  36. void selection_sort(int* A, const size_t N);
  37. void merge(int* left, int n_left, int* right, int n_right, int* out);
  38. void recurse(int* A, int* temp, int N);
  39. void merge_sort(int* A, int N);
  40. int* range(size_t N);
  41. inline void reverse(void* sequence, const size_t membercount, const size_t membersize);
  42. void test_reverse(void);
  43. char* getstring(void);
  44. int getinteger(void);
  45. void sort_trial(void);
  46. link insert_node(link A, link newnode);
  47. int delete_node(link A, link unwanted_node);
  48. int pop_node(link list);
  49. link append_node(link list, link newnode);
  50. void print_node(link node);
  51. void traverse_list(link node);
  52. link reverse_list(link head);
  53. link create_empty_node(void);
  54. link append_new_node(link tail, int data);
  55. link create_list_from_array(const int* A, const size_t N);
  56. size_t list_length(NODE const *list);
  57. void delete_list(link head);
  58. inline void swap_node(link A, link B);
  59. link getnode(const link head, size_t N);
  60. void* list_to_array(NODE const *list, const size_t list_length, const size_t data_size);
  61. link* create_link_array(link head, size_t length);
  62. inline int cmp_int_asc(const void* A, const void* B);
  63. inline int cmp_int_desc(const void* A, const void* B);
  64.  
  65. /* Generic insertion sort algorithm. */
  66. #define isort(base, num, size, comparator) \
  67. { \
  68.     void *left, *right, *key; \
  69.     if ((key = malloc(size))) \
  70.     { \
  71.         for (right = (base + size); ((size_t) right - (size_t) base)/size < num; right += size) \
  72.         { \
  73.             memcpy(key, right, size); \
  74.             for (left = right; (size_t) left > (size_t) base && comparator((left - size), key) > 0; left -= size) \
  75.             { \
  76.                 memcpy(left, left - size, size); \
  77.             } \
  78.             memcpy(left, key, size); \
  79.         } \
  80.         free(key); \
  81.     } \
  82. }
  83.  
  84. #endif // MYALGORITHMS_H
  85.  
  86.  
  87.  
  88.  
  89. #define PLACES_MAX (strlen(STRINGIZE(INT_MAX)) + 1)
  90. #define ARRLEN(A) (sizeof(A) / sizeof(0[A]))
  91.  
  92. char* repr_array(const int* A, const size_t N)
  93. {
  94.     char* result;
  95.     size_t len_result, p;
  96. #define ARRAY_BEGIN '['
  97. #define DELIMITERS ", "
  98. #define ARRAY_END "]"
  99.     result = NULL;
  100.     len_result = ((N - 1) * (PLACES_MAX + strlen(DELIMITERS))) + PLACES_MAX;
  101.     len_result += 3;
  102.     if ((result = realloc(result, sizeof(*result) * len_result)))
  103.     {
  104.         char* s;
  105.         s = result + 1;
  106.         result[0] = ARRAY_BEGIN;
  107.         for (p = 0; p < (N-1); ++p)
  108.         {
  109.             s += sprintf(s, "%d"DELIMITERS, A[p]);
  110.         }
  111.         sprintf(s, "%d"ARRAY_END, A[p]);
  112.     }
  113.     else
  114.     {
  115.         fprintf(stderr, "\n%s\n", "repr_array malloc failed: out of memory.");
  116.     }
  117.     return result;
  118. #undef ARRAY_END
  119. #undef DELIMITERS
  120. #undef ARRAY_BEGIN
  121. }
  122.  
  123. void print_array(const int* A, const size_t N)
  124. {
  125.     char* a = repr_array(A, N);
  126.     printf("%s\n", a);
  127.     free(a);
  128. }
  129.  
  130. void insertion_sort(int* A, const size_t N)
  131. {
  132.     size_t i, j;
  133.     int key;
  134.     for (i = 1; i < N; ++i)
  135.     {
  136.         key = A[i];
  137.         for (j = i; j > 0 && A[j - 1] > key; --j)
  138.         {
  139.             A[j] = A[j - 1];
  140.         }
  141.         A[j] = key;
  142.     }
  143. }
  144.  
  145. void insertion_sort_2(int* A, const size_t N)
  146. {
  147.     size_t i, j;
  148.     int key;
  149.     for (i = 1; i < N; ++i)
  150.     {
  151.         //key = A[i];
  152.         memcpy(&key, A+i, sizeof(*A));
  153.         for (j = i; j > 0 && A[j - 1] > key; --j)
  154.         {
  155.             //A[j] = A[j - 1];
  156.             memcpy(A+j, A+j-1, sizeof(*A));
  157.         }
  158.         //A[j] = key;
  159.         memcpy(A+j, &key, sizeof(*A));
  160.     }
  161. }
  162.  
  163. int randrange(unsigned int n)
  164. {
  165.     int randint, rand_max;
  166.     rand_max = RAND_MAX - (RAND_MAX % n);
  167.     while ((randint = rand()) >= rand_max);
  168.     return randint / (rand_max / n);
  169. }
  170.  
  171. int random_in_range(unsigned int min, unsigned int max)
  172. {
  173.     int base_random, range, remainder, bucket;
  174.     base_random = rand();
  175.     if (RAND_MAX == base_random)
  176.     {
  177.         return random_in_range(min, max);
  178.     }
  179.     range = max - min;
  180.     remainder = RAND_MAX % range;
  181.     bucket = RAND_MAX / range;
  182.  
  183.     if (base_random < (RAND_MAX - remainder))
  184.     {
  185.         return min + (base_random / bucket);
  186.     }
  187.     else
  188.     {
  189.         return random_in_range(min, max);
  190.     }
  191. }
  192.  
  193. int rand_range(unsigned int n)
  194. {
  195.     return random_in_range(0, n);
  196. }
  197.  
  198. inline void swap(void* A, void* B, size_t bytes)
  199. {
  200.     void* temp;
  201.     temp = malloc(bytes);
  202.     if (temp)
  203.     {
  204.         memcpy(temp, A, bytes);
  205.         memcpy(A, B, bytes);
  206.         memcpy(B, temp, bytes);
  207.         free(temp);
  208.     }
  209. }
  210.  
  211. void shuffle(void* A, size_t membercount, size_t membersize)
  212. {
  213.     size_t k;
  214.     while (membercount > 1)
  215.     {
  216.         k = rand_range(membercount);
  217.         --membercount;
  218.         swap(A + (membercount * membersize), A + (k * membersize), membersize);
  219.     }
  220. }
  221.  
  222. void my_bubble_sort(int* A, const size_t N)
  223. {
  224.     size_t i, j;
  225.     int *keydex, *next;
  226.     for (i = 0; i < N; ++i)
  227.     {
  228.         for (j = 0; j < (N - i - 1); ++j)
  229.         {
  230.             keydex = A + j;
  231.             next = keydex + 1;
  232.             if (*keydex > *next)
  233.             {
  234.                 swap(keydex, next, sizeof(*A));
  235.             }
  236.         }
  237.     }
  238. }
  239.  
  240. void bubble_sort(int* A, const size_t N)
  241. {
  242.     int n, i, newn;
  243.     n = N;
  244.     do
  245.     {
  246.         newn = 0;
  247.         for (i = 1; i < n; ++i)
  248.         {
  249.             if (A[i-1] > A[i])
  250.             {
  251.                 swap(A + i - 1, A + i, sizeof(*A));
  252.                 newn = i;
  253.             }
  254.         }
  255.         n = newn;
  256.     } while (n > 0);
  257. }
  258.  
  259. void selection_sort(int* A, const size_t N)
  260. {
  261.     int *keydex, *mindex, *index;
  262.     for (keydex = A; keydex - N < A; ++keydex)
  263.     {
  264.         mindex = keydex;
  265.         for (index = (keydex + 1); index < (A + N); ++index)
  266.         {
  267.             if (*index < *mindex)
  268.             {
  269.                 mindex = index;
  270.             }
  271.         }
  272.         if (keydex != mindex)
  273.         {
  274.             swap(keydex, mindex, sizeof(*A));
  275.         }
  276.     }
  277. }
  278.  
  279. void merge(int* left, int n_left, int* right, int n_right, int* out)
  280. {
  281.     int i, j, k;
  282.     for (i = j = k = 0; i < n_left && j < n_right; ++k)
  283.     {
  284.         if (left[i] < right[j])
  285.         {
  286.             out[k] = left[i];
  287.             ++i;
  288.         }
  289.         else
  290.         {
  291.             out[k] = right[j];
  292.             ++j;
  293.         }
  294.     }
  295.     while (i < n_left)
  296.     {
  297.         out[k] = left[i];
  298.         ++i;
  299.         ++k;
  300.     }
  301.     while (j < n_right)
  302.     {
  303.         out[k] = right[j];
  304.         ++j;
  305.         ++k;
  306.     }
  307. }
  308.  
  309. void recurse(int* A, int* temp, int N)
  310. {
  311.     int mid;
  312.     mid = N / 2;
  313.     if (N <= 1)
  314.     {
  315.         return;
  316.     }
  317.     recurse(temp, A, mid);
  318.     recurse(temp + mid, A + mid, N - mid);
  319.     merge(temp, mid, temp + mid, N - mid, A);
  320. }
  321.  
  322. void merge_sort(int* A, int N)
  323. {
  324.     int* temp;
  325.     temp = malloc(sizeof(*A) * N);
  326.     if (temp)
  327.     {
  328.         memcpy(temp, A, sizeof(*A) * N);
  329.         recurse(A, temp, N);
  330.         free(temp);
  331.     }
  332. }
  333.  
  334. /*typedef void(*sorting_algorithm)(int*, size_t);
  335. void test_sorting_algorithm(int* A, const size_t N, sorting_algorithm sort, const char* sort_name)
  336. {
  337.     printf("Before %s: ", sort_name);
  338.     print_array(A, N);
  339.     sort(A, N);
  340.     printf("After %s: ", sort_name);
  341.     print_array(A, N);
  342. }*/
  343.  
  344. #define test_sorting_algorithm(A, N, sort, sort_name) \
  345. { \
  346.     printf("Before %s: ", sort_name); \
  347.     print_array(A, N); \
  348.     sort(A, N); \
  349.     printf("After %s: ", sort_name); \
  350.     print_array(A, N); \
  351. }
  352. #define test_sort(A, N, name) test_sorting_algorithm(A, N, name, STRINGIZE(name))
  353.  
  354. int* range(size_t N)
  355. {
  356.     int* result;
  357.     if ((result = malloc(sizeof(*result) * N)))
  358.     {
  359.         int* i, num;
  360.         num = 0;
  361.         for (i = result; i < (result + N); ++i)
  362.         {
  363.             *i = num;
  364.             ++num;
  365.         }
  366.     }
  367.     return result;
  368. }
  369.  
  370. inline void reverse(void* sequence, const size_t membercount, const size_t membersize)
  371. {
  372.     void *left, *right;
  373.     right = sequence + ((membercount - 1) * membersize);
  374.     left = sequence;
  375.     while (left < right)
  376.     {
  377.         swap(left, right, membersize);
  378.         left += membersize;
  379.         right -= membersize;
  380.     }
  381. }
  382.  
  383. void test_reverse(void)
  384. {
  385.     int* A = range(10);
  386.     reverse(A, 10, sizeof(*A));
  387.     print_array(A, 10);
  388.     free(A);
  389. }
  390.  
  391. char* getstring(void)
  392. {
  393.     char* strbuffer = NULL;
  394.     size_t strbuffercapacity = 0;
  395.     size_t strbuffercharcount = 0;
  396.     int character;
  397.     while ((character = fgetc(stdin)) != '\n' && character != EOF)
  398.     {
  399.         if (strbuffercharcount + 1 > strbuffercapacity)
  400.         {
  401.             if (strbuffercapacity == 0)
  402.             {
  403.                 strbuffercapacity = sizeof(char) * 4;
  404.             }
  405.             else if (strbuffercapacity < (UINT_MAX / 2))
  406.             {
  407.                 strbuffercapacity *= 2;
  408.             }
  409.             else
  410.             {
  411.                 free(strbuffer);
  412.                 return NULL;
  413.             }
  414.             char* tempbuffer = realloc(strbuffer, sizeof(char) * strbuffercapacity);
  415.             if (tempbuffer == NULL)
  416.             {
  417.                 return NULL;
  418.             }
  419.             else
  420.             {
  421.                 strbuffer = tempbuffer;
  422.             }
  423.         }
  424.         strbuffer[strbuffercharcount] = character;
  425.         ++strbuffercharcount;
  426.     }
  427.     if (strbuffercharcount == 0 && character == EOF)
  428.     {
  429.         return NULL;
  430.     }
  431.     char* minstrbuffer = malloc(sizeof(char) * (strbuffercharcount + 1));
  432.     strncpy(minstrbuffer, strbuffer, strbuffercharcount);
  433.     free(strbuffer);
  434.     minstrbuffer[strbuffercharcount] = '\0';
  435.     return minstrbuffer;
  436. }
  437.  
  438. int getinteger(void)
  439. {
  440.     for(;;)
  441.     {
  442.         char* integers = getstring();
  443.         if (integers == NULL)
  444.         {
  445.             return INT_MAX;
  446.         }
  447.         int integer;
  448.         char character;
  449.         if (sscanf(integers, " %d %c", &integer, &character) == 1)
  450.         {
  451.             free(integers);
  452.             return integer;
  453.         }
  454.         else
  455.         {
  456.             free(integers);
  457.             printf("Retry: ");
  458.         }
  459.     }
  460. }
  461.  
  462. void sort_trial(void)
  463. {
  464.     int LEN, choice;
  465.     srand(time(NULL));
  466.     printf("Enter the size of the integer array you want: ");
  467.     LEN = getinteger();
  468.     int* A = range(LEN);
  469.     printf("\n1. Random array\n2. Reversed array\n3. Sorted array\n");
  470.     choice = getinteger();
  471.     switch (choice)
  472.     {
  473.         case 1:
  474.             shuffle(A, LEN, sizeof(*A));
  475.             break;
  476.         case 2:
  477.             reverse(A, LEN, sizeof(*A));
  478.             break;
  479.         case 3:
  480.             break;
  481.         default:
  482.             break;
  483.     }
  484.     printf("\n1. Insertion sort\n2. Bubble sort 1\n3. Bubble sort 2\n4. Selection sort\n");
  485.     choice = getinteger();
  486.     switch (choice)
  487.     {
  488.         case 1:
  489.             test_sort(A, LEN, insertion_sort);
  490.             break;
  491.         case 2:
  492.             test_sort(A, LEN, my_bubble_sort);
  493.             break;
  494.         case 3:
  495.             test_sort(A, LEN, bubble_sort);
  496.             break;
  497.         case 4:
  498.             test_sort(A, LEN, selection_sort);
  499.             break;
  500.         default:
  501.             break;
  502.     }
  503.     free(A);
  504. }
  505.  
  506. link insert_node(link A, link newnode)
  507. {
  508.     newnode->next = A->next;
  509.     A->next = newnode;
  510.     return newnode;
  511. }
  512.  
  513. int delete_node(link A, link unwanted_node)
  514. {
  515.     int data;
  516.     A->next = unwanted_node->next;
  517.     data = unwanted_node->data;
  518.     free(unwanted_node);
  519.     return data;
  520. }
  521.  
  522. int pop_node(link list)
  523. {
  524.     int data;
  525.     while (list->next)
  526.     {
  527.         list = list->next;
  528.     }
  529.     data = list->data;
  530.     free(list);
  531.     return data;
  532. }
  533.  
  534. link append_node(link list, link newnode)
  535. {
  536.     while (list->next)
  537.     {
  538.         list = list->next;
  539.     }
  540.     insert_node(list, newnode);
  541.     return newnode;
  542. }
  543.  
  544. void print_node(link node)
  545. {
  546.     printf("%p [%d] -> %p\n", node, node->data, node->next);
  547. }
  548.  
  549. void traverse_list(link node)
  550. {
  551.     for (; node->next; node = node->next)
  552.     {
  553.         print_node(node);
  554.     }
  555.     print_node(node);
  556. }
  557.  
  558. link reverse_list(link head)
  559. {
  560.     link new_head, next;
  561.     new_head = NULL;
  562.     while (head)
  563.     {
  564.         next = head->next;
  565.         head->next = new_head;
  566.         new_head = head;
  567.         head = next;
  568.     }
  569.     return new_head;
  570. }
  571.  
  572. link create_empty_node(void)
  573. {
  574.     return malloc(sizeof(NODE));
  575. }
  576.  
  577. link append_new_node(link tail, int data)
  578. {
  579.     link newnode;
  580.     newnode = create_empty_node();
  581.     newnode->data = data;
  582.     append_node(tail, newnode);
  583.     return tail->next;
  584. }
  585.  
  586. link create_list_from_array(const int* A, const size_t N)
  587. {
  588.     link head, tail;
  589.     size_t end;
  590.     head = create_empty_node();
  591.     if (head)
  592.     {
  593.         head->data = *A;
  594.         ++A;
  595.         tail = head;
  596.         tail->next = NULL;
  597.         for (end = (size_t) (A + N - 1); (size_t) A < end; ++A)
  598.         {
  599.             tail = append_new_node(tail, *A);
  600.         }
  601.     }
  602.     return head;
  603. }
  604.  
  605. size_t list_length(NODE const *list)
  606. {
  607.     size_t length;
  608.     length = 0;
  609.     while (list)
  610.     {
  611.         list = list->next;
  612.         ++length;
  613.     }
  614.     return length;
  615. }
  616.  
  617. void delete_list(link head)
  618. {
  619.     while (head->next)
  620.     {
  621.         delete_node(head, head->next);
  622.     }
  623.     free(head);
  624. }
  625.  
  626. inline void swap_node(link A, link B)
  627. {
  628.     swap(A, B, sizeof(link));
  629. }
  630.  
  631. link getnode(const link head, size_t N)
  632. {
  633.     link node;
  634.     node = head;
  635.     size_t index;
  636.     index = 0;
  637.     while (index < N)
  638.     {
  639.         node = node->next;
  640.         ++index;
  641.     }
  642.     return node;
  643. }
  644.  
  645. void* list_to_array(NODE const *list, const size_t list_length, const size_t data_size)
  646. {
  647.     void* array;
  648.     array = malloc(data_size * list_length);
  649.     if (array)
  650.     {
  651.         void* block;
  652.         size_t index;
  653.         index = 0;
  654.         block = array;
  655.         while (index < list_length)
  656.         {
  657.             memcpy(block, &(list->data), data_size);
  658.             block += data_size;
  659.             list = list->next;
  660.             ++index;
  661.         }
  662.     }
  663.     return array;
  664. }
  665.  
  666. link* create_link_array(link head, size_t length)
  667. {
  668.     link *array, *ptr;
  669.     array = malloc(sizeof(*array) * length);
  670.     ptr = array;
  671.     while (head->next)
  672.     {
  673.         *ptr = head;
  674.         ++ptr;
  675.         head = head->next;
  676.     }
  677.     return array;
  678. }
  679.  
  680. /*void isort(void* base, size_t num, size_t size, int (*comparator) (const void*, const void*))
  681. {
  682.     void *left, *right, *key;
  683.     if ((key = malloc(size)))
  684.     {
  685.         for (right = (base + size); ((size_t) right - (size_t) base)/size < num; right += size)
  686.         {
  687.             memcpy(key, right, size);
  688.             for (left = right; (size_t) left > (size_t) base && comparator((left - size), key) > 0; left -= size)
  689.             {
  690.                 memcpy(left, left - size, size);
  691.             }
  692.             memcpy(left, key, size);
  693.         }
  694.         free(key);
  695.     }
  696. }*/
  697.  
  698. inline int cmp_int_asc(const void* A, const void* B)
  699. {
  700.     int I = *((int*) A);
  701.     int J = *((int*) B);
  702.     return I < J ? -1 : I > J;
  703. }
  704.  
  705. inline int cmp_int_desc(const void* A, const void* B)
  706. {
  707.     int I = *((int*) A);
  708.     int J = *((int*) B);
  709.     return I > J ? -1 : I < J;
  710. }
  711.  
  712. int main(void)
  713. {
  714.     int A[] = {9,8,7,6,5,4,3,2,1,0};
  715.     print_array(A, 10);
  716.     insertion_sort(A, 10);
  717.     print_array(A, 10);
  718.     return 0;
  719. }
Success #stdin #stdout 0.01s 1856KB
comments (?)
stdin 
Standard input is empty
stdout 
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
https://ideone.com/Hfsgg
language:
C (gcc 8.3)
created:
14 years 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!