// the HOST_DEBUG and PREALLOCATE macros for your timing run.
#include "util.h"
+#include <string.h>
+#include <assert.h>
// The INSERTION_THRESHOLD is the size of the subarray when the
// algorithm switches to using an insertion sort instead of
// quick sort.
-#define INSERTION_THRESHOLD 7
+#define INSERTION_THRESHOLD 10
// NSTACK is the required auxiliary storage.
// It must be at least 2*lg(DATA_SIZE)
#define NSTACK 50
-// Swap macro for swapping two values.
-
-#define SWAP(a,b) temp=(a);(a)=(b);(b)=temp;
-
//--------------------------------------------------------------------------
// Input/Reference Data
+#define type int
#include "dataset1.h"
+// Swap macro for swapping two values.
+
+#define SWAP(a,b) do { typeof(a) temp=(a);(a)=(b);(b)=temp; } while (0)
+#define SWAP_IF_GREATER(a, b) do { if ((a) > (b)) SWAP(a, b); } while (0)
+
//--------------------------------------------------------------------------
// Quicksort function
-void sort( int n, int arr[] )
+static void insertion_sort(size_t n, type arr[])
{
- int i,j,k;
- int ir = n;
- int l = 1;
- int jstack = 0;
- int a, temp;
+ type *i, *j;
+ type value;
+ for (i = arr+1; i < arr+n; i++)
+ {
+ value = *i;
+ j = i;
+ while (value < *(j-1))
+ {
+ *j = *(j-1);
+ if (--j == arr)
+ break;
+ }
+ *j = value;
+ }
+}
- int istack[NSTACK];
+static void selection_sort(size_t n, type arr[])
+{
+ for (type* i = arr; i < arr+n-1; i++)
+ for (type* j = i+1; j < arr+n; j++)
+ SWAP_IF_GREATER(*i, *j);
+}
- for (;;) {
+void sort(size_t n, type arr[])
+{
+ type* ir = arr+n;
+ type* l = arr+1;
+ type* stack[NSTACK];
+ type** stackp = stack;
+ for (;;)
+ {
#if HOST_DEBUG
printArray( "", n, arr );
#endif
// Insertion sort when subarray small enough.
- if ( ir-l < INSERTION_THRESHOLD ) {
-
- for ( j = l+1; j <= ir; j++ ) {
- a = arr[j-1];
- for ( i = j-1; i >= l; i-- ) {
- if ( arr[i-1] <= a ) break;
- arr[i] = arr[i-1];
- }
- arr[i] = a;
- }
+ if ( ir-l < INSERTION_THRESHOLD )
+ {
+ insertion_sort(ir - l + 1, l - 1);
- if ( jstack == 0 ) break;
+ if ( stackp == stack ) break;
// Pop stack and begin a new round of partitioning.
- ir = istack[jstack--];
- l = istack[jstack--];
-
+ ir = *stackp--;
+ l = *stackp--;
}
- else {
-
+ else
+ {
// Choose median of left, center, and right elements as
// partitioning element a. Also rearrange so that a[l-1] <= a[l] <= a[ir-].
-
- k = (l+ir) >> 1;
- SWAP(arr[k-1],arr[l])
- if ( arr[l-1] > arr[ir-1] ) {
- SWAP(arr[l-1],arr[ir-1])
- }
- if ( arr[l] > arr[ir-1] ) {
- SWAP(arr[l],arr[ir-1])
- }
- if ( arr[l-1] > arr[l] ) {
- SWAP(arr[l-1],arr[l])
- }
+ SWAP(arr[((l-arr) + (ir-arr))/2-1], l[0]);
+ SWAP_IF_GREATER(l[-1], ir[-1]);
+ SWAP_IF_GREATER(l[0], ir[-1]);
+ SWAP_IF_GREATER(l[-1], l[0]);
// Initialize pointers for partitioning.
- i = l+1;
- j = ir;
+ type* i = l+1;
+ type* j = ir;
// Partitioning element.
- a = arr[l];
+ type a = l[0];
- for (;;) { // Beginning of innermost loop.
- do i++; while (arr[i-1] < a); // Scan up to find element > a.
- do j--; while (arr[j-1] > a); // Scan down to find element < a.
- if (j < i) break; // Pointers crossed. Partitioning complete.
- SWAP(arr[i-1],arr[j-1]); // Exchange elements.
- } // End of innermost loop.
+ for (;;) { // Beginning of innermost loop.
+ while (*i++ < a); // Scan up to find element > a.
+ while (*(j-- - 2) > a); // Scan down to find element < a.
+ if (j < i) break; // Pointers crossed. Partitioning complete.
+ SWAP(i[-1], j[-1]); // Exchange elements.
+ } // End of innermost loop.
// Insert partitioning element.
- arr[l] = arr[j-1];
- arr[j-1] = a;
- jstack += 2;
+ l[0] = j[-1];
+ j[-1] = a;
+ stackp += 2;
// Push pointers to larger subarray on stack,
// process smaller subarray immediately.
#if HOST_DEBUG
- if ( jstack > NSTACK ) { printf("NSTACK too small in sort.\n"); exit(1); }
+ assert(stackp < stack+NSTACK);
#endif
- if ( ir-i+1 >= j-l ) {
- istack[jstack] = ir;
- istack[jstack-1] = i;
+ if ( ir-i+1 >= j-l )
+ {
+ stackp[0] = ir;
+ stackp[-1] = i;
ir = j-1;
}
- else {
- istack[jstack] = j-1;
- istack[jstack-1] = l;
+ else
+ {
+ stackp[0] = j-1;
+ stackp[-1] = l;
l = i;
}
}
-
}
-
}
//--------------------------------------------------------------------------
#if PREALLOCATE
// If needed we preallocate everything in the caches
- sort( DATA_SIZE, input_data );
+ sort(DATA_SIZE, verify_data);
+ if (verify(DATA_SIZE, input_data, input_data))
+ return 1;
#endif
// Do the sort