From 5f3cc5b96b8b30a46051081403a6ac9210aee6af Mon Sep 17 00:00:00 2001
From: Dominik Kaiser <dominik@dominik-XPS.fritz.box>
Date: Tue, 16 Apr 2024 17:59:00 +0200
Subject: [PATCH] Add radixsort for new data system

---
 sorting.c | 42 ++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 40 insertions(+), 2 deletions(-)

diff --git a/sorting.c b/sorting.c
index 8f5d31f..422625e 100644
--- a/sorting.c
+++ b/sorting.c
@@ -6,13 +6,51 @@
 /*   By: dkaiser <dkaiser@student.42heilbronn.de    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2024/04/13 15:04:19 by dkaiser           #+#    #+#             */
-/*   Updated: 2024/04/16 09:27:53 by dkaiser          ###   ########.fr       */
+/*   Updated: 2024/04/16 17:54:16 by dkaiser          ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
+#include "libft/ft_printf.h"
 #include "push_swap.h"
 
-void stack_sort(t_psdata *data)
+static int is_sorted(t_stack *stack)
+{
+    int i;
+
+    if (stack->size < 2)
+        return 1;
+    i = 1;
+    while (i < stack->size)
+    {
+        if (stack->stack[i] < stack->stack[i-1])
+            return 0;
+        i++;
+    }
+    return 1;
+}
+
+static void radixsort(t_psdata *data, int bit)
 {
+    int i;
+    int size;
 
+    i = 0;
+    size = data->a->size;
+    while (i < size)
+    {
+        if (data->a->size && ((data->a->stack[0] >> bit) & 1) == 0)
+            run_command(data, PB);
+        else if (data->a->size > 1)
+            run_command(data, RA);
+        i++;
+    }
+    while (data->b->size > 0)
+        run_command(data, PA);
+    if (!is_sorted(data->a))
+        radixsort(data, bit + 1);
+}
+
+void stack_sort(t_psdata *data)
+{
+    radixsort(data, 0);
 }
-- 
2.47.2