HW1 Solutions Page

For this homework, I had the grader recommend some of the better assignments and I chose from them one to use as the homework solution. The student that had their homework chosen received 1 bonus point after curving for having their homework selected. If you were chosen and would rather your homework not be used as the solution let me know and I will choose someone else's homework and they will receive the bonus point instead. The only changes I made were to convert the names listed in the homework files to SJSU student. The code in the homework didn't completely follow the Java Style Guidelines for the Department. Comments in the original program didn't follow the guidelines, some lines were over 80 columns, some lines had trailing whitespace, braces didn't align, and instead used 1-true brace. I fixed some of these issues. You are supposed to use three spaces for your tab stop but the code uses four, I left this because it would be a pain to change everywhere. In terms of the code the three-way merge in the student solution applies a two-way merge twice. This probably is a minimal change to the existing book code so is parsimonious in a sense, however, it is somewhat inefficient. I was imagining the solution to just directly implement the 3-way merge as I did in my Python code below:

[Hw1 Project-ZIP]

import sys

def three_way_mergesort(A):
    n = len(A)
    if n == 1:
        print "Input:%d" % A[0]
        print "Sorted:%d" % A[0]
        return;
    if n == 2:
        print "Input:%d %d" % (A[0], A[1])
        if A[1] < A[0]:
            tmp = A[1]
            A[1] = A[0]
            A[0] = tmp
        print "Sorted:%d %d" % (A[0], A[1])
        return;
    print "Input:" + output_sequence(A)
    third_n = len(A)/3
    two_third_n = 2 * third_n
    First = A[:third_n]
    Second = A[third_n:two_third_n]
    Last = A[two_third_n:]
    print "Subsequences:"
    print output_sequence(First)
    print output_sequence(Second)
    print output_sequence(Last)
    three_way_mergesort(First)
    three_way_mergesort(Second)
    three_way_mergesort(Last)
    merge(First, Second, Last, A)
    print "Sorted:" + output_sequence(A)

def output_sequence(A):
    space = ""
    out = ""
    for elt in A:
        out += space + str(elt)
        space = " "
    return out

def merge(A, B, C, Out):
    t = 0
    Indices = [0, 0, 0]
    Lens = [len(A), len(B), len(C)]
    n = Lens[0] + Lens[1] + Lens[2]
    min_index = 0
    value = A[0]
    while t < n:
        set_value = False
        if Indices[0] < Lens[0]:
            min_index = 0
            value = A[Indices[0]]
            set_value = True
        if Indices[1] < Lens[1] and ((not set_value) or B[Indices[1]] <= value):
            min_index = 1
            value = B[Indices[1]]
            set_value = True
        if Indices[2] < Lens[2] and ((not set_value) or C[Indices[2]] <= value):
            min_index = 2
            value = C[Indices[2]]
            set_value = True
        Indices[min_index] =Indices[min_index] + 1
        Out[t] = value
        t = t + 1

if len(sys.argv) < 2:
    print "Enter some numbers to sort"
    raise SystemExit(1)
A = sys.argv[1:];
for i in range(0,len(A)):
    try:
        A[i] = int(A[i])
    except ValueError:
        print "Items to sort must be integers"
        raise SystemExit(1)
three_way_mergesort(A);

Return to homework page.