introsortquickmergelongjmp adicionado

Esta versão utiliza LONG JUMP para espacar da recursão do quicksortM3 Signed-off-by: Bruno Ribas <brunoribas@gmail.com>
bcribas · Oct 6, 2020 · 1208c91 · 1208c91
1 parent 67a6044
commit 1208c91
Show file tree

Hide file tree

Showing 2 changed files with 84 additions and 0 deletions.
diff --git a/introsortquickmergelongjmp.c b/introsortquickmergelongjmp.c
@@ -0,0 +1,61 @@
+/*
+ * Copyright(C) 2020, Bruno César Ribas <bruno.ribas@unb.br>
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of version 2.1 of the GNU Lesser General Public License
+ * as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it would be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ *
+ */
+#include <stdio.h>
+#include <math.h>
+#include <setjmp.h>
+#include "introsortquickmergelongjmp.h"
+#include "ordenacaomacros.h"
+#include "insertionsort.h"
+#include "mergesort.h"
+#include "separa.h"
+
+int trapstop=0;
+int trapsize=0;
+jmp_buf env;
+static void quicksortM3(Item *V,int l, int r,int rec)
+{
+  if (r-l<=32) return;
+
+  if(rec==0)
+  {
+    trapstop=1;
+    longjmp(env,1);
+    return;
+  }
+
+  exch(V[(l+r)/2],V[r-1]);
+  cmpexch(V[l],V[r-1]);
+  cmpexch(V[l],V[r]);
+  cmpexch(V[r-1],V[r]);
+
+
+  int j=separa(V,l+1,r-1);
+  quicksortM3(V,l,j-1,rec-1);
+  quicksortM3(V,j+1,r,rec-1);
+}
+
+void introsortquickmergelongjmp(Item *V,int l,int r)
+{
+  trapsize=2*((int)log2((double)(r-l+1)));
+  setjmp(env);
+  if(trapstop==0)
+    quicksortM3(V,l,r,trapsize);
+
+  if(trapstop==1)
+  {
+    fprintf(stderr,"trap/");
+    mergesort(V,l,r);
+  }
+  else
+    insertionsort(V,l,r);
+}
diff --git a/introsortquickmergelongjmp.h b/introsortquickmergelongjmp.h
@@ -0,0 +1,23 @@
+/*
+ * Copyright(C) 2020, Bruno César Ribas <bruno.ribas@unb.br>
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of version 2.1 of the GNU Lesser General Public License
+ * as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it would be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ *
+ */
+#ifndef __introsortquickmergeLONGJMPH__
+#define __introsortquickmergeLONGJMPH__
+#include "ordenacaomacros.h"
+
+void introsortquickmergelongjmp(Item *V,int l,int r);
+
+#ifdef __introsortquickmergelongjmponly__
+#define sort(v,l,r) introsortquickmergelongjmp(v,l,r)
+#endif
+
+#endif