Marriage Sort

August 20, 2010

Here is our version of marriage sort:

(define (msort! lt? vec) ; marriage sort
  (define (v i) (vector-ref vec i))
  (define (v! i x) (vector-set! vec i x))
  (define (swap! i j) (let ((t (v i))) (v! i (v j)) (v! j t)))
  (let* ((end (- (vector-length vec) 1))
         (skip (if (positive? end) (isqrt end) -1)))
    (while (<= 0 skip)
      (let ((vbest 0) (i 1))
        (while (< i skip)
          (when (lt? (v vbest) (v i)) (set! vbest i))
          (set! i (+ i 1)))
        (while (< i end)
          (if (lt? (v vbest) (v i))
              (begin (swap! i end) (set! end (- end 1)))
              (set! i (+ i 1))))
        (swap! vbest end)
        (set! end (- end 1))
        (set! skip (if (positive? end) (isqrt end) -1)))))
  (isort! lt? vec))

The outer while controls the recursive sweeps, the first of the inner whiles finds the largest value in the sample, and the second of the inner whiles moves large values to the end of the array; the final swap! moves the largest sample value just before the new end. The three pointers are named skip, end and i; vbest points to the largest value in the sample. Here is isort:

(define (isort! lt? vec) ; insertion sort
  (define (v i) (vector-ref vec i))
  (define (v! i x) (vector-set! vec i x))
  (define (swap! i j) (let ((t (v i))) (v! i (v j)) (v! j t)))
  (let ((n (vector-length vec)))
    (do ((i 0 (+ i 1))) ((= i n))
      (do ((j i (- j 1)))
          ((or (<= j 0) (< (v (- j 1)) (v j))))
        (swap! (- j 1) j)))))

We used isqrt, when and while from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/4Sldvq9Q. You might also enjoy a solution in Factor by John Benediktsson, who sometimes posts his solutions here at Programming Praxis, and from whom this post was stolen.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
4 Comments »

4 Responses to “Marriage Sort”

  1. slabounty said
    August 23, 2010 at 10:57 PM

    Here’s a ruby version translated straight from the pseudo-code with “last” substituting for “end”. I took the insertion_sort straight from the wikipedia pseudo-code. 

    class Array
    def swap(i, j)
        self[i], self[j] = self[j], self[i]
    end

    def marriage_sort!
        last = self.length
        while true
            skip = Math.sqrt(last).to_i - 1
            break if skip <= 0

            # Pick the best element in the first vN - 1:
            best_pos = 0; i = 1
            while i < skip
                best_pos = i if self[i] > self[best_pos]
                i += 1
            end

            # Now pull out elements >= self[bestPos], and move to the end:
            i = skip
            while i < last
                if self[i] >= self[best_pos]
                    self.swap(i, last-1)
                    last -= 1
                else
                    i += 1
                end
            end

            # Finally, move our best pivot element to the end
            self.swap(best_pos, last-1)
            last-=1
        end

        # Finish off with insertion sort to put the elements into true sorted order
        self.insertion_sort!
    end

    def insertion_sort!
        self.each_index do |i|
            v = self[i]
            j = i-1
            done = false
            begin
                if self[j] > v
                    self[j+1] = self[j]
                    j = j-1
                    done = true if j < 0
                else
                    done = true
                end
            end while done == false
            self[j+1] = v
        end
        self
    end
end



a = [5, 7, 8, 10, 3, 2, 9, 4, 6, 1]
p a.marriage_sort!
  2. zcbenz said
    August 28, 2010 at 12:35 PM

    My C++ solution:

    #include <iostream>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

void insertion_sort (int *begin, int *end) {
    int *itr = begin+1;
    while (itr < end) {
        int save = *itr;
        int *current = itr;
        while (current > begin) {
            if (save < *(current-1))
                *current = *(current-1);
            else
                break;
            --current;
        }

        *current = save;
        ++itr;
    }
}

void marriage_sort (int *begin, int *end) {
    int *oend = end;
    int *skip = begin + (size_t)sqrt (end - begin);
    if (skip <= begin) return;

    int *maxi = max_element (begin, skip);
    while (skip < end) {
        if (*skip > *maxi) swap (*skip, *--end);
        ++skip;
    }
    swap (*maxi, *--oend);

    insertion_sort (begin, end);
}

int main(int argc, char *argv[])
{
    srand (time (NULL));
    const size_t SIZE = 16;
    int array[SIZE];

    generate (array, array+SIZE,
              []() { return rand()%40; });
    for_each (array, array+SIZE,
              [](int n) { cout << n << " "; });
    cout << endl;

    insertion_sort (array, array+SIZE);
    for_each (array, array+SIZE,
              [](int n) { cout << n << " "; });
    
    return 0;
}
  3. zcbenz said
    August 28, 2010 at 12:36 PM

    oops, insertion_sort (array, array+SIZE); should be marriage_sort (array, array+SIZE);

Leave a comment