Use insertion sort

1 files changed, 26 insertions, 13 deletions

diff --git a/src/entities.c b/src/entities.c
index fe05ef8..a1aa9db 100644
--- a/src/entities.c
+++ b/src/entities.c
@@ -1,6 +1,5 @@
 #include <stdint.h>
 #include <string.h>
-#include <stdlib.h>
 
 #include "vga.h"
 #include "map.h"
@@ -59,17 +58,6 @@ void entities_update()
         }
 }
 
-static int cmp_entities(const void *a, const void *b)
-{
-    const Entity **ea = (const Entity **)a;
-    const Entity **eb = (const Entity **)b;
-
-    if (((*ea)->y >> 4) == ((*eb)->y >> 4))
-        return (*ea)->used - (*eb)->used;
-    else
-        return (*ea)->y - (*eb)->y;
-}
-
 void entities_sort()
 {
     sort_cnt = 0;
@@ -81,7 +69,32 @@ void entities_sort()
     player_ent.y = player_y();
     sort[sort_cnt++] = &player_ent;
 
-    qsort(sort, sort_cnt, sizeof(Entity *), cmp_entities);
+    /* using insertion sort;
+     *
+     * The sorting criteria is the y coordinate unless the entities
+     * share a 16px area in which we check the value of used that defines 3
+     * layers: bg, fb and player.
+     * */
+
+    Entity *t;
+    uint8_t i = 1;
+
+    while (i < sort_cnt)
+    {
+        uint8_t j = i;
+        while (j > 0 && (
+                    sort[j - 1]->y > sort[j]->y
+                    || ((sort[j - 1]->y >> 4) == (sort[j]->y >> 4)
+                        && sort[j - 1]->used > sort[j]->used)
+                ))
+        {
+            t = sort[j];
+            sort[j] = sort[j - 1];
+            sort[j - 1] = t;
+            j--;
+        }
+        i++;
+    }
 }
 
 void entities_draw()