SHARE
TWEET

Untitled

a guest Nov 8th, 2019 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int print_arr(const int* arr, const int size)
  5. {
  6.     printf("array: ");
  7.     for (int i = 0; i < size; i++)
  8.     {
  9.         printf ("%d ", arr[i]);
  10.     }
  11.     printf("\n");
  12. }
  13.  
  14. int q_sort(int* arr, const int first, const int last)
  15. {  
  16.     int size = last - first + 1;
  17.    
  18.     printf("start sort. ");
  19.     print_arr(arr, size);
  20.    
  21.     if (size == 2)
  22.     {
  23.         printf("hi!");
  24.         if (arr[0] > arr[1])
  25.         {
  26.             int x = arr[1];
  27.             arr[1] = arr[0];
  28.             arr[0] = x;
  29.         }
  30.         return 0;
  31.     }
  32.    
  33.     if (size <= 1)
  34.     {
  35.         return 0;
  36.     }
  37.  
  38.     int middle_index = (int)(size / 2);
  39.     printf("middle_index = %d\n", middle_index);
  40.  
  41.     int begin_index = first;
  42.     int end_index = last;
  43.  
  44.     int current_left_index = 0;
  45.     int left_size = 0;
  46.     int* left_arr  = (int*)malloc(size*sizeof(int));
  47.  
  48.     int current_right_index = 0;
  49.     int right_size = 0;
  50.     int* right_arr = (int*)malloc(size*sizeof(int));
  51.    
  52.     int current_middle_index = 0;
  53.     int middle_size = 0;
  54.     int* middle_arr  = (int*)malloc(size*sizeof(int));
  55.  
  56.     int middle_element = arr[middle_index];
  57.  
  58.     for (int i = begin_index; i <= end_index; i++)
  59.     {
  60.         printf("if. current element: %d, middle: %d\n", arr[i], middle_element);
  61.         if (arr[i] >= middle_element)
  62.         {
  63.             right_arr[current_right_index] = arr[i];
  64.             current_right_index++;
  65.             right_size++;
  66.         }
  67.        
  68.         if (arr[i] < middle_element)
  69.         {
  70.             left_arr[current_left_index] = arr[i];
  71.             current_left_index++;
  72.             left_size++;
  73.         }
  74.        
  75.         if (arr[i] == middle_element)
  76.         {
  77.             middle_arr[current_middle_index] = arr[i];
  78.             current_middle_index++;
  79.             middle_size++;
  80.         }
  81.     }
  82.  
  83.     printf("left_size: %d\n", left_size);
  84.     printf("result left array: ");
  85.     print_arr(left_arr, left_size);
  86.     q_sort(left_arr,  0, left_size - 1);
  87.    
  88.     for (int i = 0; i < left_size; i++)
  89.     {
  90.         arr[i] = left_arr[i];
  91.     }
  92.    
  93.     printf("middle_size: %d\n", middle_size);
  94.     printf("result middle array:");
  95.     print_arr(middle_arr, middle_size);
  96.    
  97.     for (int i = 0; i < middle_size; i++)
  98.     {
  99.         arr[i + left_size + 1] = middle_arr[i];
  100.     }
  101.    
  102.     printf("right_size: %d\n", right_size);
  103.     printf("result right array:");
  104.     print_arr(right_arr, right_size);
  105.     q_sort(right_arr, 0, right_size - 1);
  106.    
  107.     for (int i = 0; i < right_size; i++)
  108.     {
  109.         arr[i + middle_size + left_size + 1] = right_arr[i];
  110.     }
  111.  
  112.     free(right_arr);
  113.     free(left_arr);
  114. }
  115.  
  116. int main()
  117. {
  118.     int size = 0;
  119.     int array[1000];
  120.     printf ("Enter the length of the array\n");
  121.     scanf ("%d", &size);
  122.     printf ("Enter the elements of the array\n");
  123.  
  124.     for (int i = 0; i < size; i++)
  125.     {
  126.         scanf ("%d", &array[i]);
  127.     }
  128.  
  129.     int last = size - 1;
  130.     int first = 0;
  131.  
  132.     q_sort(array, first, last);
  133.  
  134.     printf ("\nSorted array:\n");
  135.     print_arr(array, size);
  136.    
  137.     return 0;
  138. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top