Нужен пример сортировки слиянием - C (СИ) (76704)

Узнай цену своей работы

Формулировка задачи:

В общем пытался сам написать сортировку слиянием, в результате потерял литр крови из глаз. Моя программа вышла чересчур большой и неадекватной. Хотел поискать решения в интернете и нашел их великое множество, но все они на с++, а работающую программу на чистом си не встретил. Из-за плохого знания с++, не смог перевести на си. Пожалуйста, если знаете, где есть работающая версия, скиньте ссылку или код. Вот хороший сайт, но там решение на си++, времени разбираться с классами нет, помогите, будьте добры.

Решение задачи: «Нужен пример сортировки слиянием»

textual
Листинг программы 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <errno.h>
  4. #include <pthread.h>
  5. #include <time.h>
  6. #define MAXLEN 100000000
  7. #define NANO 1000000000
  8.  
  9.  
  10. struct timespec tp;
  11.  
  12.  
  13. int a[MAXLEN], len;
  14. int *for_8Cores; // like a buf
  15. typedef struct {
  16.     int a;
  17.     int b;
  18. } str_k;
  19.  
  20. void *mergesort (void *arg) {
  21.     str_k kk = * (str_k *) arg;
  22.     int step = 1;
  23.     int k;
  24.     int q;
  25.     int i, j;
  26.     while ((kk.b - kk.a) > step) {
  27.         
  28.         for (k = kk.a; k < kk.b; k = k + 2 * step) {
  29.             i = k;
  30.             j = k + step;
  31.             q = k;
  32.             while ((i < k + step) && (i < kk.b) && (j < k + 2 * step) && (j < kk.b)) {
  33.                 if (a[i] <= a[j]) {
  34.                     for_8Cores[q] = a[i];
  35.                     ++i;
  36.                     ++q;
  37.                 }
  38.                 else {
  39.                     for_8Cores[q] = a[j];
  40.                     ++j;
  41.                     ++q;
  42.                 }
  43.             }
  44.             while ((i < k + step) && (i < kk.b)) {
  45.                 for_8Cores[q] = a[i];
  46.                 ++q;
  47.                 ++i;
  48.             }
  49.             while ((j < k + 2 * step) && (j < kk.b)) {
  50.                 for_8Cores[q] = a[j];
  51.                 ++j;
  52.                 ++q;
  53.             }
  54.         }
  55.         step *= 2;
  56.                 for (k = kk.a; k < kk.b; ++k)
  57.                     a[k] = for_8Cores[k];
  58.     }
  59. }
  60.  
  61. void mergesort_1 (int step) {
  62.     int k;
  63.     int q;
  64.     int i, j;
  65.     int *buf;
  66.     while (len > step) {            
  67.         for (k = 0; k < len; k = k + 2 * step) {
  68.             i = k;
  69.             j = k + step;
  70.             q = k;
  71.             while ((i < k + step) && (i < len) && (j < k + 2 * step) && (j < len)) {
  72.                 if (a[i] <= a[j]) {
  73.                     for_8Cores[q] = a[i];
  74.                     ++i;
  75.                     ++q;
  76.                 }
  77.                 else {
  78.                     for_8Cores[q] = a[j];
  79.                     ++j;
  80.                     ++q;
  81.                 }
  82.             }
  83.             while ((i < k + step) && (i < len)) {
  84.                 for_8Cores[q] = a[i];
  85.                 ++q;
  86.                 ++i;
  87.             }
  88.             while ((j < k + 2 * step) && (j < len)) {
  89.                 for_8Cores[q] = a[j];
  90.                 ++j;
  91.                 ++q;
  92.             }
  93.         }
  94.         for (k = 0; k < len; ++k)
  95.             a[k] = for_8Cores[k];
  96.         step *=2;
  97.     }
  98. }
  99.  
  100. int main (int argc, char **argv) {
  101.     FILE *f;
  102.     f = fopen (argv[1], "r");
  103.     if (f == NULL) {
  104.         printf ("There is no such file.\n");
  105.         return 1;
  106.     }
  107.     int i;
  108.     i = 0;
  109.     while (fscanf (f, "%d", &a[i]) == 1) 
  110.         ++i;
  111.     len = i;
  112.     fclose (f);
  113.  
  114.     int cores = atoi(argv[2]);
  115.     if (cores < 1 || cores > 32) {
  116.         printf ("Can't do this. It's immoral!\n");
  117.         return 0;
  118.     }
  119.     printf ("working on %d thread(s)...\n", cores);
  120.     for_8Cores = (int *) malloc (len * sizeof(int));
  121.     pthread_t thread[16];
  122.     int cer = 1;
  123.     while (cer < len/cores) 
  124.         cer *= 2;
  125.     if ((len/cores - cer/2) <= (cer - len/cores))
  126.         cer = cer/2;    
  127. //  printf ("%d - cer\n", cer);
  128.     str_k k[16];
  129.     for (i = 0; i < cores - 1; ++i) {
  130.         k[i].a = i * cer;
  131.         k[i].b = (i + 1) * cer;
  132.     }
  133.     k[cores - 1].a = (cores - 1) * cer;
  134.     k[cores - 1].b = len;
  135.     clock_gettime (1, &tp);
  136.     double start = tp.tv_sec;
  137.     double Nstart = (double) tp.tv_nsec;
  138.     for (i = 0; i < cores; ++i)
  139.         pthread_create(&thread[i], NULL, mergesort, &k[i]);
  140.     for (i = 0; i < cores; ++i)
  141.         pthread_join(thread[i], NULL);
  142.  
  143.     mergesort_1 (cer);
  144.     free (for_8Cores); //убрал за собой!
  145.     f = fopen ("answer.txt", "w");
  146.     for (i = 0; i < len; ++i)
  147.         fprintf (f, "%d ", a[i]);
  148.     fclose (f);
  149.     clock_gettime (1, &tp);
  150.     printf("Время работы = %lf\n", (double) (tp.tv_sec - start + ((double)tp.tv_nsec - Nstart) / NANO));
  151.         
  152.     return 0;
  153. }

Объяснение кода листинга программы

Этот код реализует сортировку массива целых чисел слиянием. Он использует многопоточность для ускорения процесса сортировки.

  1. В функции mergesort происходит сортировка массива a с помощью алгоритма сортировки слиянием. Эта функция принимает аргумент arg, который является структурой str_k, содержащей два индекса, ограничивающие подмассив, который нужно отсортировать.
  2. В функции mergesort_1 происходит сортировка массива a с помощью алгоритма сортировки слиянием. Эта функция принимает аргумент step, который определяет размер подмассива, который нужно отсортировать на каждом шаге.
  3. В функции main происходит чтение чисел из файла в массив a. Затем определяется количество потоков, которые будут использоваться для сортировки. Создаются потоки и запускается сортировка слиянием в каждом потоке. Затем происходит объединение массива a из всех потоков. Результат сортировки записывается в файл answer.txt.
  4. Значения переменных:
    • MAXLEN - максимально возможный размер массива a.
    • NANO - используется для точного вычисления времени работы программы.
    • len - количество элементов в массиве a.
    • for_8Cores - временный массив, используемый для сортировки.
    • cer - размер подмассива, который сортируется в каждом потоке.
    • k - структура, используемая для передачи границ подмассивов в функцию сортировки.
    • thread - массив потоков.
    • tp - структура, используемая для измерения времени работы программы.
    • start - время начала выполнения программы.
    • Nstart - время начала выполнения программы в наносекундах.
    • f - файл, используемый для чтения чисел и записи результата сортировки.
    • i - счетчик, используемый для итерации по массиву a и файлу f.
    • cores - количество потоков, которые будут использоваться для сортировки.

ИИ поможет Вам:

  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 3.667 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут