SF.net SVN: matplotlib: [4010] trunk/py4science/examples/quicksort.c

[<jd...@us...>]

Revision: 4010
          http://matplotlib.svn.sourceforge.net/matplotlib/?rev=4010&view=rev
Author:   jdh2358
Date:     2007-10-25 20:40:33 -0700 (Thu, 25 Oct 2007)

Log Message:
-----------
added quicksort example

Added Paths:
-----------
    trunk/py4science/examples/quicksort.c

Added: trunk/py4science/examples/quicksort.c
===================================================================
--- trunk/py4science/examples/quicksort.c	                        (rev 0)
+++ trunk/py4science/examples/quicksort.c	2007-10-26 03:40:33 UTC (rev 4010)
@@ -0,0 +1,115 @@
+/* Copyright (c) 2007 the authors listed at the following URL, and/or
+the authors of referenced articles or incorporated external code:
+http://en.literateprograms.org/Quicksort_(C)?action=history&offset=20070511214343
+
+Permission is hereby granted, free of charge, to any person obtaining
+a copy of this software and associated documentation files (the
+"Software"), to deal in the Software without restriction, including
+without limitation the rights to use, copy, modify, merge, publish,
+distribute, sublicense, and/or sell copies of the Software, and to
+permit persons to whom the Software is furnished to do so, subject to
+the following conditions:
+
+The above copyright notice and this permission notice shall be
+included in all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+Retrieved from: http://en.literateprograms.org/Quicksort_(C)?oldid=10011
+*/
+
+#include <stdlib.h>
+
+#include "quicksort.h"
+
+#define MIN_QUICKSORT_LIST_SIZE    32
+
+static int compare_elements_helper(void *base, size_t element_size, int idx1, int idx2,
+                                   int(*comparer)(const void *, const void*))
+{
+    char* base_bytes = base;
+    return comparer(&base_bytes[idx1*element_size], &base_bytes[idx2*element_size]);
+}
+
+#define element_less_than(i,j)  (compare_elements_helper(base, element_size, (i), (j), comparer) < 0)
+
+static void exchange_elements_helper(void *base, size_t element_size, int idx1, int idx2)
+{
+    char* base_bytes = base;
+    int i;
+    for (i=0; i<element_size; i++)
+    {
+        char temp = base_bytes[idx1*element_size + i];
+        base_bytes[idx1*element_size + i] = base_bytes[idx2*element_size + i];
+        base_bytes[idx2*element_size + i] = temp;
+    }
+}
+
+#define exchange_elements(i,j)  (exchange_elements_helper(base, element_size, (i), (j)))
+
+void insertion_sort(void * base, size_t num_elements, size_t element_size,
+                    int (*comparer)(const void *, const void *))
+{
+   int i;
+   for (i=0; i < num_elements; i++)
+   {
+       int j;
+       for (j = i - 1; j >= 0; j--)
+       {
+           if (element_less_than(j, j + 1)) break;
+           exchange_elements(j, j + 1);
+       }
+   }
+}
+
+int partition(void * base, size_t num_elements, size_t element_size,
+               int (*comparer)(const void *, const void *), int pivotIndex)
+
+{
+    int low = 0, high = num_elements - 1;
+    exchange_elements(num_elements - 1, pivotIndex);
+
+    while (1) {
+        while (element_less_than(low, num_elements-1)) {
+	    low++;
+	}
+	while (!element_less_than(high, num_elements-1)) {
+	    high--;
+	}
+
+        if (low > high) break;
+        exchange_elements(low, high);
+
+    }
+    exchange_elements(low, num_elements - 1);
+    return low;
+
+}
+
+void quicksort(void * base, size_t num_elements, size_t element_size,
+               int (*comparer)(const void *, const void *))
+{
+    int pivotIndex;
+
+    if (num_elements < MIN_QUICKSORT_LIST_SIZE) {
+        insertion_sort(base, num_elements, element_size, comparer);
+        return;
+    }
+
+    pivotIndex = rand() % num_elements;
+
+    pivotIndex = partition(base, num_elements, element_size, comparer, pivotIndex);
+
+    quicksort(base, pivotIndex, element_size, comparer);
+    quicksort(((char*)base) + element_size*(pivotIndex+1),
+              num_elements - (pivotIndex + 1), element_size, comparer);
+
+}
+
+


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.