From cfa1c811c65f1b8a10d9034a5974d617cda92ec6 Mon Sep 17 00:00:00 2001
From: Nebuleon Fumika
Date: Sun, 27 Jan 2013 00:45:59 -0500
Subject: Reimplement Quicksort correctly for file selection screens. Before
 this commit, the emulator could sometimes give a file out of its order, for
 example an O* file between two S* files.

---
 source/nds/gui.c | 69 ++++++++++++++++++++++++++++----------------------------
 1 file changed, 34 insertions(+), 35 deletions(-)

(limited to 'source')

diff --git a/source/nds/gui.c b/source/nds/gui.c
index ece310c..c57c660 100644
--- a/source/nds/gui.c
+++ b/source/nds/gui.c
@@ -435,53 +435,52 @@ void change_ext(char *src, char *buffer, char *extension)
 --------------------------------------------------------*/
 static int sort_function(const void *dest_str_ptr, const void *src_str_ptr)
 {
-	char *dest_str = *((char **)dest_str_ptr);
-	char *src_str = *((char **)src_str_ptr);
+	char *dest_str = ((char *)dest_str_ptr);
+	char *src_str = ((char *)src_str_ptr);
 
 	// For files and directories, . and .. sort first.
-	if(src_str[0] == '.')
+	if(src_str[0] == '.' && dest_str[0] != '.')
 		return 1;
 
-	if(dest_str[0] == '.')
+	if(dest_str[0] == '.' && src_str[0] != '.')
 		return -1;
 
 	return strcasecmp(dest_str, src_str);
 }
 
-static int my_array_partion(void *array, int left, int right)
+static int my_array_partion(void **array, int left, int right)
 {
-    unsigned int pivot= *((unsigned int*)array + left);
-
-    while(left < right)
-    {
-        while(sort_function((void*)((unsigned int*)array+left), (void*)((unsigned int *)array+right)) < 0) {
-            right--;
-        }
-
-        if(right== left) break;
-        *((unsigned int*)array + left) = *((unsigned int*)array + right);
-        *((unsigned int*)array + right) = pivot;
-
-        if(left < right)
-        {
-            left++;
-            if(right== left) break;
-        }
-
-        while(sort_function((void*)((unsigned int*)array+right), (void*)((unsigned int *)array+left)) > 0) {
-            left++;
-        }
+	// Choose a pivot, left <= pivot <= right
+	unsigned int pivotIndex = left + (right - left) / 2;
+
+	// Move pivot value to the end
+	void *temp = array[pivotIndex];
+	array[pivotIndex] = array[right];
+	array[right] = temp;
+
+	// Move values that sort before the pivot value to before the new
+	// pivot's location
+	unsigned int storeIndex = left, i;
+	for (i = left; i <= right - 1; i++)
+	{
+		if (sort_function(array[i], array[right]) < 0)
+		{
+			temp = array[i];
+			array[i] = array[storeIndex];
+			array[storeIndex] = temp;
+			storeIndex++;
+		}
+	}
 
-        if(left== right) break;
-        *((unsigned int*)array + right) = *((unsigned int*)array + left);
-        *((unsigned int*)array + left) = pivot;
-        right--;
-    }
+	// Move the pivot value to its correct location
+	temp = array[storeIndex];
+	array[storeIndex] = array[right];
+	array[right] = temp;
 
-    return left;
+	return storeIndex;
 }
 
-static void my_qsort(void *array, int left, int right)
+static void my_qsort(void **array, int left, int right)
 {
     if(left < right)
     {
@@ -748,9 +747,9 @@ static int load_file_list(struct FILE_LIST_INFO *filelist_infop)
 #if 0
     my_qsort((void *)file_list, 0, num_files-1);
 #else	//to support ".." directory, but take it as file
-    my_qsort((void *)file_list, 1, num_files-1);
+    my_qsort((void **)file_list, 1, num_files-1);
 #endif
-    my_qsort((void *)dir_list, 0, num_dirs-1);
+    my_qsort((void **)dir_list, 0, num_dirs-1);
 
     return 0;
 }
-- 
cgit v1.2.3