squiggle.c

commit 03ca3e3b0cd46834e859c7367901b511ce80ce81
parent 578bfa27987bfeb7ca57f2d98fb807005145d206
Author: NunoSempere <nuno.sempere@protonmail.com>
Date:   Wed, 29 Nov 2023 21:45:42 +0000

prepare to incorporate quickselect into squiggle_more

Diffstat:
M
scratchpad/quickselect/quickselect
 | 
0

M
scratchpad/quickselect/quickselect.c
 | 
42
+++++++++++-------------------------------

2 files changed, 11 insertions(+), 31 deletions(-)
diff --git a/scratchpad/quickselect/quickselect b/scratchpad/quickselect/quickselect
Binary files differ.
diff --git a/scratchpad/quickselect/quickselect.c b/scratchpad/quickselect/quickselect.c
@@ -2,20 +2,14 @@
 #include <stdio.h>
 #include <stdlib.h>
 
-void swap_pointers(double *x, double* y){
-  double tmp = *x;
-  *x = *y;
-  *y = tmp;
-}
-
-void swap_in_array(int i, int j, double xs[]){
+void swp(int i, int j, double xs[]){
   double tmp = xs[i];
   xs[i] = xs[j];
   xs[j] = tmp;
 }
 
 void array_print(double xs[], int n){
-  printf("    [");
+  printf("[");
   for(int i=0; i<n;i++){
     printf("%f, ", xs[i]);
   }
@@ -23,32 +17,20 @@ void array_print(double xs[], int n){
 }
 
 int partition(int low, int high, double xs[], int length){
-  // srand(2);
-  array_print(xs, length);
-  int pivot = low + floor((high-low)/2); // low + floor(rand() % (high - low + 1));
+  // To understand this function: 
+  // - see the note after gt variable definition
+  // - go to commit 578bfa27 and the scratchpad/ folder in it, which has printfs sprinkled throughout
+  int pivot = low + floor((high-low)/2); 
   double pivot_value = xs[pivot];
-  printf("pivot_value: #%f\n", pivot_value);
-  swap_in_array(pivot, high, xs);
+  swp(pivot, high, xs);
   int gt = low; /* This pointer will iterate until finding an element which is greater than the pivot. Then it will move elements that are smaller before it--more specifically, it will move elements to its position and then increment. As a result all elements between gt and i will be greater than the pivot. */
   for(int i=low; i<high; i++){
-    printf("Step: #%d\n", i);
-    printf("  Before: \n");
-    printf("    gt: %d\n", gt);
-    array_print(xs, length);
     if(xs[i] < pivot_value){
-      printf("  Swaping element #%d: %f and element #%d: %f\n", gt, xs[gt], i, xs[i]);
-      swap_in_array(gt, i, xs);
+      swp(gt, i, xs);
       gt++;
     }
-    printf("  After: \n");
-    array_print(xs, length);
-    printf("    gt: %d\n", gt);
   }
-  printf("Step: Swap with last item\n");
-  swap_in_array(high, gt, xs);
-  printf("  After: \n");
-  array_print(xs, length);
-  printf("    gt: %d\n", gt);
+  swp(high, gt, xs);
   return gt;
 }
 
@@ -74,11 +56,9 @@ int main(){
   double xs[] = {2.1, 1.0, 6.0, 4.0, 7.0, -1.0, 2.0, 10.0};
   int length = 8;
   int k = 2;
-
-  // partition(0, length-1, xs, length);
-
-  double result = quickselect(k, xs, length);
   array_print(xs, 8);
+  double result = quickselect(k, xs, length);
   printf("The item in pos #%d is: %f\n", k, result);
+  array_print(xs, 8);
   return 0;
 }