Change quicksort to introsort

Salla302 · Dec 29, 2020 · 8fbde47 · 8fbde47
1 parent ab292a0
commit 8fbde47
Show file tree

Hide file tree

Showing 11 changed files with 858 additions and 51 deletions.
diff --git a/.gitignore b/.gitignore
@@ -1,7 +1,11 @@
-
+*.bin
 keyhunt
 test_bloom.c
 xpoints.c
+heapsort.c
+insertionsorttest.c
+introsort.c
+
 *.txt
 # Prerequisites
 *.d

diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -1,3 +1,7 @@
+Versionb 0.1.20201228
+- Change Quicksort to Introsort, this solve some edge cases of quicksort.
+- Introsort is avaible to keyhunt and hexcharstoraw. worst case. O(N log N).
+
 Version 0.1.20201223
 - Added new tool hexcharstoraw to create a raw binary file for xpoint from a text-hexadecimal file
 - Added option -w to work with raw binary file, this file contains xpoint in binary format fixed to 32 bytes

diff --git a/Makefile b/Makefile
@@ -5,8 +5,9 @@ default:
 	gcc -O3 -c base58/base58.c -o base58.o
 	gcc -O3 -c rmd160/rmd160.c -o rmd160.o
 	gcc -O3 -c keccak/keccak-tiny.c -o keccak.o -D"memset_s(W,WL,V,OL)=memset(W,V,OL)"
-	gcc -O3 -c keyhunt.c -o keyhunt.o
+	gcc -O3 -c tiny_sha3/sha3.c -o sha3.o
+	gcc -O3 -c keyhunt.c -o keyhunt.o -lm
 	gcc -o keyhunt keyhunt.o base58.o rmd160.o sha256.o bloom.o murmurhash2.o keccak.o -lgmp -lm -lpthread
-	gcc -O3 hexcharstoraw.c -o hexcharstoraw
+	gcc -O3 hexcharstoraw.c -o hexcharstoraw -lm
 clean:
 	rm -r *.o
diff --git a/hexcharstoraw.c b/hexcharstoraw.c
@@ -7,13 +7,18 @@ email: alberto.bsd@gmail.com
 #include <stdlib.h>
 #include <stdint.h>
 #include <string.h>
+#include <math.h>
 #include "util.h"
 
 int MAXLENGTHADDRESS = 32;
 
-void quicksort(char *arr, int low, int high);
+void _sort(char *arr,int n);
+void _insertionsort(char *arr, int n);
+void _introsort(char *arr,int depthLimit, int n);
 void swap(char *a,char *b);
-int partition (char *arr, int low, int high);
+int partition(char *arr, int n);
+void heapsort(char  *arr, int n);
+void heapify(char *arr, int n, int i);
 
 int main(int argc,char **argv) {
   char *line_input,*line_output,*aux;
@@ -26,7 +31,7 @@ int main(int argc,char **argv) {
   input = fopen(argv[1],"r");
   output = fopen(argv[2],"wb");
   line_input = malloc(1024);
-  line_output = malloc(32);
+  line_output = malloc(MAXLENGTHADDRESS);
   if(input == NULL || output == NULL ||  line_input== NULL || line_output == NULL ) {
     printf("error fopen or malloc\n");
   }
@@ -46,7 +51,7 @@ int main(int argc,char **argv) {
             free(aux);
           }
           hexs2bin(line_input,line_output);
-          fwrite(line_output,1,32,output);
+          fwrite(line_output,1,MAXLENGTHADDRESS,output);
           count++;
         }
         else  {
@@ -62,19 +67,21 @@ int main(int argc,char **argv) {
   fclose(output);
   free(line_input);
   output = fopen(argv[2],"rb");
+  printf("Allocating memory...\n");
   do {
-    line_input = malloc(count*32);
+    line_input = malloc(count*MAXLENGTHADDRESS);
   } while(line_input == NULL);
   i = 0;
   while(i < count) {
-    fread(line_input+(i*32),1,32,output);
+    fread(line_input+(i*32),1,MAXLENGTHADDRESS,output);
     i++;
   }
   fclose(output);
   output = fopen(argv[2],"wb");
   printf("File %s was create with %u records\n",argv[2],count);
-  printf("Sorting once... \n");
-  quicksort(line_input,0,count-1);
+  printf("Sorting once... ");
+  _sort(line_input,count);
+  _insertionsort(line_input,count);
   i = 0;
   while(i < count) {
     fwrite(line_input+(i*32),1,32,output);
@@ -94,27 +101,147 @@ void swap(char *a,char *b)  {
   memcpy(b,t,MAXLENGTHADDRESS);
 }
 
-int partition (char *arr, int low, int high)  {
-    char *pivot = arr + (high*MAXLENGTHADDRESS);    // pivot
-		//printf("Pivot : %s\n",pivot);
-    int j,i = (low - 1);  // Index of smaller element
-    for (j = low; j < high; j++)  {
-        // If current element is smaller than the pivot
-        if (memcmp(arr + (j*MAXLENGTHADDRESS),pivot,MAXLENGTHADDRESS) < 0)  {
-            i++;    // increment index of smaller element
-            swap(arr + (i*MAXLENGTHADDRESS), arr + (j*MAXLENGTHADDRESS));
+void _sort(char *arr,int n)  {
+  int depthLimit = ((int) ceil(log(n))) * 2;
+  _introsort(arr,depthLimit,n);
+}
+
+void _introsort(char *arr,int depthLimit, int n) {
+  int p;
+  if(n > 1)  {
+    if(n <= 16) {
+      _insertionsort(arr,n);
+    }
+    else  {
+      if(depthLimit == 0) {
+        heapsort(arr,n);
+      }
+      else  {
+        p = partition(arr,n);
+        if(p >= 2) {
+          _introsort(arr , depthLimit-1 , p);
         }
+        if((n - (p + 1)) >= 2 ) {
+          _introsort(arr + ((p+1) *MAXLENGTHADDRESS) , depthLimit-1 , n - (p + 1));
+        }
+      }
+    }
+  }
+}
+
+void _insertionsort(char *arr, int n) {
+  char *arrj,*temp;
+  char key[MAXLENGTHADDRESS];
+  int j,i;
+  for(i = 1; i < n ; i++ ) {
+    j= i-1;
+    memcpy(key,arr + (i*MAXLENGTHADDRESS),MAXLENGTHADDRESS);
+    arrj = arr + (j*MAXLENGTHADDRESS);
+    while(j >= 0 && memcmp(arrj,key,MAXLENGTHADDRESS) > 0) {
+      memcpy(arr + ((j+1)*MAXLENGTHADDRESS),arrj,MAXLENGTHADDRESS);
+      j--;
+      arrj = arr + (j*MAXLENGTHADDRESS);
+    }
+    memcpy(arr + ((j+1)*MAXLENGTHADDRESS),key,MAXLENGTHADDRESS);
+  }
+}
+
+int partition(char *arr, int n)  {
+  char pivot[MAXLENGTHADDRESS];
+  int j,i,t, r = (int) n/2,jaux = -1,iaux = -1, iflag, jflag;
+  char *a,*b,*hextemp,*hextemp_pivot;
+  i = - 1;
+  memcpy(pivot,arr + (r*MAXLENGTHADDRESS),MAXLENGTHADDRESS);
+  i = 0;
+  j = n-1;
+  do {
+    iflag = 1;
+    jflag = 1;
+    t = memcmp(arr + (i*MAXLENGTHADDRESS),pivot,MAXLENGTHADDRESS);
+    iflag = (t <= 0);
+    while(i < j && iflag) {
+      i++;
+      t = memcmp(arr + (i*MAXLENGTHADDRESS),pivot,MAXLENGTHADDRESS);
+      iflag = (t <= 0);
+    }
+    t = memcmp(arr + (j*MAXLENGTHADDRESS),pivot,MAXLENGTHADDRESS);
+    jflag = (t > 0);
+    while(i < j && jflag) {
+      j--;
+      t = memcmp(arr + (j*MAXLENGTHADDRESS),pivot,MAXLENGTHADDRESS);
+      jflag = (t > 0);
+    }
+    if(i < j) {
+      if(i == r )  {
+        r = j;
+      }
+      else  {
+        if(j == r )  {
+          r = i;
+        }
+      }
+
+      swap(arr + (i*MAXLENGTHADDRESS),arr + (j*MAXLENGTHADDRESS) );
+      jaux = j;
+      iaux = i;
+      j--;
+      i++;
+    }
+
+  } while(j > i );
+  if(jaux != -1 && iaux != -1)  {
+    if(iflag || jflag)  {
+      if(iflag) {
+        if(r != j)
+          swap(arr + (r*MAXLENGTHADDRESS),arr + ((j )*MAXLENGTHADDRESS) );
+        jaux = j;
+      }
+      if(jflag) {
+        if(r != j-1)
+          swap(arr + (r*MAXLENGTHADDRESS),arr + ((j-1 )*MAXLENGTHADDRESS) );
+        jaux = j-1;
+      }
+    }
+    else{
+      if(r != j)
+        swap(arr + (r*MAXLENGTHADDRESS),arr + ((j )*MAXLENGTHADDRESS) );
+      jaux = j;
+    }
+  }
+  else  {
+    if(iflag && jflag)  {
+      jaux = r;
+    }
+    else  {
+      if(iflag ) {
+        swap(arr + (r*MAXLENGTHADDRESS),arr + ((j)*MAXLENGTHADDRESS) );
+        jaux = j;
+      }
+    }
+  }
+  return jaux;
+}
+
+void heapify(char *arr, int n, int i) {
+    int largest = i;
+    int l = 2 * i + 1;
+    int r = 2 * i + 2;
+    if (l < n && memcmp(arr +(l*MAXLENGTHADDRESS),arr +(largest * MAXLENGTHADDRESS),MAXLENGTHADDRESS) > 0)
+        largest = l;
+    if (r < n && memcmp(arr +(r*MAXLENGTHADDRESS),arr +(largest *MAXLENGTHADDRESS),MAXLENGTHADDRESS) > 0)
+        largest = r;
+    if (largest != i) {
+        swap(arr +(i*MAXLENGTHADDRESS), arr +(largest*MAXLENGTHADDRESS));
+        heapify(arr, n, largest);
     }
-    swap(arr + ((i+1)*MAXLENGTHADDRESS), arr + (high*MAXLENGTHADDRESS));
-    return (i + 1);
 }
 
-void quicksort(char *arr, int low, int high)  {
-  int pi;
-  if (low < high)  {
-			//printf("quicksort from %i to %i\n",low,high);
-      pi = partition(arr, low, high);
-      quicksort(arr, low, pi - 1);
-      quicksort(arr, pi + 1, high);
+void heapsort(char  *arr, int n)  {
+  int i;
+  for ( i = n / 2 - 1; i >= 0; i--)
+    heapify(arr, n, i);
+  for ( i = n - 1; i > 0; i--) {
+    swap(arr , arr +(i*MAXLENGTHADDRESS));
+    heapify(arr, i, 0);
   }
 }