mergesort_gen.c 1.17 KB
Newer Older
Paffenholz, Andreas's avatar
Paffenholz, Andreas committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
/*************************************
* Beispielprogramm zur Vorlesung
* Einfuehrung in die Programmierung I
* Andreas Paffenholz
* TU Darmstadt, Wintersemester 2020/21
* (c) 2020-
* Sortieren mit MergeSort
*  * Bibliothek zu MergeSort
**************************************/

#include <stdlib.h>

#include "mergesort_gen.h"

void merge(void** a, int l, int m, int u, int (*vgl) (void*, void*)) {

   void* aux[u-l];
   int l_counter=l, u_counter=m, aux_counter=0;

   while ( l_counter < m && u_counter < u) {
      if ( vgl(a[l_counter],a[u_counter]) < 0 )
         aux[aux_counter++] = a[l_counter++];
      else
         aux[aux_counter++] = a[u_counter++];
   }
   
   while ( l_counter < m )
      aux[aux_counter++] = a[l_counter++];
   
   while ( u_counter < u )
      aux[aux_counter++] = a[u_counter++];

   for ( int i = l, aux_counter = 0; i < u; ++i, ++aux_counter )
      a[i] = aux[aux_counter];
}

void sort(void** a, int l, int u, int (*vgl) (void*, void*)) {
   if ( u-l > 1 ) {
      int m = l+(u-l)/2;
      sort(a,l,m, vgl);
      sort(a,m,u, vgl);
      merge(a,l,m,u, vgl);
   }
}

void merge_sort(void** a, int size, int (*vgl) (void*, void*)) {
   sort(a,0,size, vgl);
}