StoneHaos

maxim12

Jun 18th, 2020
1,231
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <time.h>
  4. #include <stdlib.h>
  5.  
  6. using namespace std;
  7.  
  8. void print(int* arr, int n) {
  9.     for (int i = 0; i < n; ++ i)
  10.         printf("%d ", arr[i]);
  11.     printf("\n");
  12. }
  13.  
  14. /*
  15. a - Проходы
  16. b - Сравнения
  17. c - Перестановки
  18. */
  19. void quick(int* arr, int n, int* a, int* b, int* c) {
  20.     if (n <= 1)
  21.         return;
  22.     int left = 0;
  23.     int right = n - 1;
  24.     int pivot = (n - 1) >> 1;
  25.     while (left < right) {
  26.         while (left < pivot && arr[left] <= arr[pivot]) {
  27.             ++ left;
  28.             (*b) ++;
  29.         }
  30.         while (right > pivot && arr[right] >= arr[pivot]) {
  31.             -- right;
  32.             (*b) ++;
  33.         }
  34.         (*b) ++;
  35.         if (arr[left] > arr[right]) {
  36.             (*c) ++;
  37.             swap(arr[left], arr[right]);
  38.             if (left == pivot)
  39.                 pivot = right;
  40.             else if (right == pivot)
  41.                 pivot = left;
  42.         }
  43.     }
  44.     (*a) ++;
  45.     quick(arr, pivot + 1, a, b, c);
  46.     quick(arr + pivot + 1, n - pivot - 1, a, b, c);
  47. }
  48.  
  49. void radix(int* arr, int n, int* a, int* b, int* c) {
  50.     int d = 1;
  51.     int cnt[10];
  52.     int p[10];
  53.     int *tmp = new int[n];
  54.     int k = 0;
  55.  
  56.     int mx = 0;
  57.     for (int i = 0; i < n; ++ i)
  58.         if (arr[i] > mx)
  59.             mx = arr[i];
  60.     for (; mx != 0; mx /= 10, ++ k);
  61.  
  62.     for (int i = 0; i < k; ++ i, d *= 10) { // Проход по разрядам числа
  63.  
  64.         p[0] = 0;
  65.         fill(cnt, cnt + 10, 0);
  66.  
  67.         for (int j = 0; j < n; ++ j) { // Подсчёт количества каждой цифры в текущем разряде всех чисел массива
  68.             int x = (arr[j] / d) % 10;
  69.             cnt[x] ++;
  70.         }
  71.         (*a) ++;
  72.  
  73.         for (int j = 1; j < 10; ++ j) // Устанавливает начальные смещения для сортировки по разряду
  74.             p[j] = p[j - 1] + cnt[j - 1];
  75.  
  76.         for (int j = 0; j < n; ++ j) { // Сортировка по разряду
  77.             int x = (arr[j] / d) % 10;
  78.             tmp[p[x] ++] = arr[j];
  79.         }
  80.         (*a) ++;
  81.  
  82.         for (int j = 0; j < n; ++ j) // Запись tmp в arr
  83.             arr[j] = tmp[j];
  84.     }
  85.     delete [] tmp;
  86. }
  87.  
  88. int main() {
  89.     time_t t = time(NULL);
  90.     printf("t = %d\n", t);
  91.     srand(t);
  92.  
  93.     int n;
  94.     scanf("%d", &n);
  95.     int* arr = new int[n];
  96.     for (int i = 0; i < n; ++ i)
  97.         arr[i] = rand() % 100 - 50;
  98.     int a = 0, b = 0, c = 0;
  99.  
  100.     printf("Quick Sort:\n");
  101.     print(arr, n);
  102.     quick(arr, n, &a, &b, &c);
  103.     print(arr, n);
  104.     printf("a = %d, b = %d, c = %d\n", a, b, c);
  105.  
  106.     a = 0; b = 0; c = 0;
  107.     for (int i = 0; i < n; ++ i)
  108.         arr[i] = rand() % 100;
  109.     printf("\nRadix Sort:\n");
  110.     print(arr, n);
  111.     radix(arr, n, &a, &b, &c);
  112.     print(arr, n);
  113.     printf("a = %d, b = %d, c = %d\n", a, b, c);   
  114.  
  115.     delete [] arr;
  116.     return 0;
  117. }
RAW Paste Data