A Median-Of-Three Killer Sequence

November 8, 2016

Here is our median-of-three killer:

(define (m3-killer n)
  (if (odd? n) (error 'm3-killer "length must be even")
    (let* ((k (/ n 2)) (ary (make-vector n #f)))
      (do ((i 1 (+ i 1))) ((< k i) ary)
        (when (odd? i)
          (vector-set! ary (- i 1) i)
          (vector-set! ary i (+ k i)))
        (vector-set! ary (+ k i -1) (+ i i))))))

A timing test shows that it takes less than a second to sort a million random integers, but sorting the median-of-three killer takes 6.5 seconds:

> (time (time-quicksort 10 1000000))
(time (time-quicksort 10 ...))
    554 collections
    9298 ms elapsed cpu time, including 78 ms collecting
    9312 ms elapsed real time, including 37 ms collecting
    2328076520 bytes allocated, including 2335573896 bytes reclaimed
> (time (begin (sort < (m3-killer 1000000)) 'done))
(time (begin (sort < ...) ...))
    197 collections
    6490 ms elapsed cpu time, including 32 ms collecting
    6500 ms elapsed real time, including 28 ms collecting
    833222352 bytes allocated, including 828448656 bytes reclaimed
done

Of course, the comparison gets worse as the arrays increase in size.

You can run the program at http://ideone.com/FmC65N.

Pages: 1 2

5 Responses to “A Median-Of-Three Killer Sequence”

  1. John Cowan said

    I hope this is leading up to introsort, which has the interesting property that its performance is bounded below by n log n, and yet it is not deterministic like mergesort.

  2. matthew said

    Something odd there – the “killer” sequence should result in quadratic performance & a massive slowdown rather than just a factor of 6.

    I think the reason is that your partition functions don’t position the pivot element between the two partitions as the killer sequence expects.

    Here’s another version (this is based on Knuth’s description of Sedgewick’s modification of Dijkstra’s redevelopment of Hoare’s original, from “Structured programming with go to statements”, which has a very interesting discussion of partitioning, amongst much else – Hoare’s original paper is worth a read too – he points out, for example, that not moving the pivot to its final position makes proving termination harder (as we might end up with one empty partition and one the same size as the original array – I don’t think this can happen with the suggested algorithm, but it’s not obvious).

    Note that the pivot (which is moved to the end of the array) and the first element (which is less that or equal to the pivot) act as sentinels for the first iteration through the loop – the median calculation sets this up nicely, so we still don’t need to check array bounds when moving the pointers.

     - 
    int partition(T *a, int n) {
      int last = n-1, mid = n/2;
      if (a[0] > a[last]) std::swap(a[0],a[last]);
      if (a[last] > a[mid]) std::swap(a[last],a[mid]);
      if (a[0] > a[last]) std::swap(a[0],a[last]);
      T pivot = a[last];
      int i = 0, j = last;
      while(true) {
        do i++; while(a[i] < pivot);
        do j--; while(a[j] > pivot);
        if (i >= j) break;
        std::swap(a[i],a[j]);
      }
      std::swap(a[i],a[last]);
      return i;
    }
    
    void qsort(T *a, int n) {
      if (n > 1) {
        int p = partition(a,n);
        qsort(a,p);
        qsort(a+p+1,n-p-1);
      }
    }
    
  3. Daniel said

    Here’s a solution in C99.

    Based on the killer sequences in the problem, It seems that the problem assumes that median-of-three is calculated from the first element, the middle element, and the last element in an array. My quicksort from the corresponding previous problem calculated median from the first three elements in an array. I’ve modified my earlier code to calculate medians in the same way assumed by this problem.

    Compiler optimizations were disabled. I had to increase the stack size to prevent stack overflows.

    There are two sections to the output. The first shows example median-of-three killer sequences, generated by init_median_of_three_killer. The second section shows runtimes for sorting random arrays versus killer arrays. Each experiment was conducted with 10 separate sorts, and the time reported is the aggregate time for all 10 sorts. Rows correspond to various array sizes.

    A random array sorts faster than a killer array with the same size. However, sorting either type appears to be O(n^2). For both array types, doubling array size roughly quadruples the time to sort, suggesting O(n^2). I understand why this is the case for killer arrays, but am not sure why the algorithm scales this way for random arrays. Do others experience similar behavior? Is there a reason to expect this? It seems to indicate a bug in my code, but I couldn’t find one (although I didn’t test thoroughly).

    #include <stddef.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    void insertionsort(int* array, size_t n) {
    	for (int i = 1; i < n; ++i) {
    		for (int j = i; j > 0 && array[j-1] > array[j]; --j) {
    			int tmp = array[j];
    			array[j] = array[j-1];
    			array[j-1] = tmp;
    		}
    	}
    }
    
    int partition(int* array, size_t n) {
    	int pivot = array[0];
    	// improvement 3: median-of-three
    	if (n >= 3) {
    		int sample[3];
    		sample[0] = array[0];
    		sample[1] = array[n/2];
    		sample[2] = array[n-1];
    		insertionsort(sample, 3);
    		pivot = sample[1];
    	}
    	int i = -1;
    	int j = n;
    	while (1) {
    		do ++i; while (array[i] < pivot);
    		do --j; while (array[j] > pivot);
    		if (i >= j) return j;
    		// improvement 1: inline swap
    		int tmp = array[i];
    		array[i] = array[j];
    		array[j] = tmp;
    	}
    }
    
    void quicksort(int* array, size_t n) {
    	if (n < 2) return;
    	// improvement 2: early cutoff to insertion sort
    	if (n < 22) {
    		insertionsort(array, n);
    		return;
    	}
    	int p = partition(array, n);
    	quicksort(array, p + 1);
    	quicksort(array + p + 1, n - p - 1);
    }
    
    void init_random_array(int* array, size_t n) {
    	for (int i = 0; i < n; ++i) {
    		array[i] = rand();
    	}
    }
    
    void init_median_of_three_killer(int* array, size_t n) {
    	// if n is odd, set the last element to n-1, and proceed
    	// with n decremented by 1
    	if (n % 2 != 0) {
    		array[n-1] = n;
    		--n;
    	}
    	size_t m = n/2;
    	for (int i = 0; i < m; ++i) {
    		// first half of array (even indices)
    		if (i % 2 == 0) array[i] = i + 1;
    		// first half of array (odd indices)
    		else array[i] = m + i + (m % 2 != 0 ? 1 : 0);
    		// second half of array
    		array[m + i] = (i+1) * 2;
    	}
    }
    
    void print_array(int* array, size_t n) {
    	printf("[");
    	for (int i = 0; i < n; ++i) {
    		if (i > 0) printf(", ");
    		printf("%d", array[i]);
    	}
    	printf("]");
    }
    
    int main(void) {
    	// Part 1: "write a program that creates a 'killer sequence'
    	//          for the median-of-three partition"
    	printf("Median-of-Three Killer Sequences\n");
    	for (int n = 1; n <= 20; ++n) {
    		printf("%d: ", n);
    		int array[n];
    		init_median_of_three_killer(array, n);
    		print_array(array, n);
    		printf("\n");
    	}
    	printf("\n");
    
    	// Part 2: "compare its time to the time required for sorting a
    	//          random partition"
    
    	srand(time(NULL));
    	clock_t tic;
    	clock_t toc;
    	int max_order = 18;
    	int* array = malloc((1<<max_order)*sizeof(int));
    	int loops = 10;
    	double elapsed;
    	double results[max_order+1][2];
    
    	// Random Array Sort Times
    	for (int order = 0; order <= max_order; ++order) {
    		int n = 1 << order;
    		elapsed = 0;
    		for (int i = 0; i < loops; ++i) {
    			init_random_array(array, n);
    			tic = clock();
    			quicksort(array, n);
    			toc = clock();
    			elapsed += (double)(toc-tic) / CLOCKS_PER_SEC;
    		}
    		results[0][order] = elapsed;
    	}
    
    	// Killer Array Sort Times
    	for (int order = 0; order <= max_order; ++order) {
    		int n = 1 << order;
    		elapsed = 0;
    		for (int i = 0; i < loops; ++i) {
    			init_median_of_three_killer(array, n);
    			tic = clock();
    			quicksort(array, n);
    			toc = clock();
    			elapsed += (double)(toc-tic) / CLOCKS_PER_SEC;
    		}
    		results[1][order] = elapsed;
    	}
    
    	printf("Random Array vs. Killer Array Sort Times\n");
    	for (int order = 0; order <= max_order; ++order) {
    		int n = 1 << order;
    		double random_sort_time = results[0][order];
    		double killer_sort_time = results[1][order];
    		printf("%d: %0.3f, %0.3f\n", n, random_sort_time, killer_sort_time);
    	}
    
    	free(array);
    	return 0;
    }
    

    Output:

    Median-of-Three Killer Sequences
    1: [1]
    2: [1, 2]
    3: [1, 2, 3]
    4: [1, 3, 2, 4]
    5: [1, 3, 2, 4, 5]
    6: [1, 5, 3, 2, 4, 6]
    7: [1, 5, 3, 2, 4, 6, 7]
    8: [1, 5, 3, 7, 2, 4, 6, 8]
    9: [1, 5, 3, 7, 2, 4, 6, 8, 9]
    10: [1, 7, 3, 9, 5, 2, 4, 6, 8, 10]
    11: [1, 7, 3, 9, 5, 2, 4, 6, 8, 10, 11]
    12: [1, 7, 3, 9, 5, 11, 2, 4, 6, 8, 10, 12]
    13: [1, 7, 3, 9, 5, 11, 2, 4, 6, 8, 10, 12, 13]
    14: [1, 9, 3, 11, 5, 13, 7, 2, 4, 6, 8, 10, 12, 14]
    15: [1, 9, 3, 11, 5, 13, 7, 2, 4, 6, 8, 10, 12, 14, 15]
    16: [1, 9, 3, 11, 5, 13, 7, 15, 2, 4, 6, 8, 10, 12, 14, 16]
    17: [1, 9, 3, 11, 5, 13, 7, 15, 2, 4, 6, 8, 10, 12, 14, 16, 17]
    18: [1, 11, 3, 13, 5, 15, 7, 17, 9, 2, 4, 6, 8, 10, 12, 14, 16, 18]
    19: [1, 11, 3, 13, 5, 15, 7, 17, 9, 2, 4, 6, 8, 10, 12, 14, 16, 18, 19]
    20: [1, 11, 3, 13, 5, 15, 7, 17, 9, 19, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
    
    Random Array vs. Killer Array Sort Times
    1: 0.000, 0.000
    2: 0.000, 0.000
    4: 0.000, 0.000
    8: 0.000, 0.000
    16: 0.000, 0.000
    32: 0.000, 0.000
    64: 0.000, 0.000
    128: 0.000, 0.000
    256: 0.000, 0.000
    512: 0.000, 0.000
    1024: 0.000, 0.000
    2048: 0.000, 0.015
    4096: 0.000, 0.078
    8192: 0.015, 0.282
    16384: 0.078, 1.218
    32768: 0.282, 4.985
    65536: 1.218, 20.344
    131072: 4.985, 84.890
    262144: 20.344, 334.953
    
  4. Daniel said

    > “It seems to indicate a bug in my code, but I couldn’t find one (although I didn’t test thoroughly).”

    I found the bug. My declaration for the results array had a problem.
    Before: double results[max_order+1][2];
    After: double results[2][max_order+1];

    The corrected time comparisons are below. As expected, the updated output no longer suggests that sorting random arrays is O(n^2), as opposed to my earlier problematic results.

    Random Array vs. Killer Array Sort Times
    1: 0.000, 0.000
    2: 0.000, 0.000
    4: 0.000, 0.000
    8: 0.000, 0.000
    16: 0.000, 0.000
    32: 0.000, 0.000
    64: 0.000, 0.000
    128: 0.000, 0.000
    256: 0.000, 0.000
    512: 0.000, 0.016
    1024: 0.000, 0.000
    2048: 0.000, 0.016
    4096: 0.000, 0.078
    8192: 0.015, 0.297
    16384: 0.016, 1.265
    32768: 0.031, 4.953
    65536: 0.078, 20.500
    131072: 0.188, 87.032
    262144: 0.390, 349.21
    
  5. […] sorting algorithm that we have been working up to in three previous exercises is introspective sort, or introsort, invented by David Musser in 1997 for the C++ Standard Library. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: