Random Notes: Homework 7

I will talk in class about MergeSort and QuickSort, and go into detail about using Quicksort for arrays. But as usual, we also want to consider linked lists. This homework is a merge sort with linked lists. The base case, as usual, is a list of length 0 or 1; just return the input. For the recursive case, the first problem is to divide the input list into two halves. It doesn't matter which numbers go in which half, as long as they are roughly equal. So let us put element number 1,3,5... in one half, and number 2,4,6... in the other. For this you need two recursive methods. They are

public static intlist odd_members(intlist L)
    if L is null return null
    else return a new list with first member: L.first
                                remaining members: even_members(L.rest)
public static intlist even_members(intlist L)
    if L is null return null
    else return odd_members(L.rest)

Do you see how this works? We'll talk about it in class. Now the function calls itself to sort the two halves. Finally, put the halves together, with a method like this:

public static intlist merge(intlist K, intlist L)
if K is empty
   return L
if L is empty 
   return K;
if(L.first < K.first)
   return a new list with first member: L.first
                          rest: merge(L.rest,K)
  return a new list with first member: K.first
                         rest: merge(L,K.rest)

And there is your answer. As usual, prompt the user and read a list of positive numbers terminated by -1. Put them in a list (we talked about this), sort the list, print the result.
Possible Solution:
Compile two files in the same folder:
   javac list.java
                            javac homework7.java
Then run:    java homework7

1/ list.java

class list
{
     public int first;
     public list rest;

     public list(int x, list y)
    {
    first = x;
        rest = y;
    }
}

2/ homework7.java

import java.util.Scanner;

public class homework7
{

   public static void main(String[] args)
{
       int n = 0;
       list l = null, odd_list = null, even_list = null, merge_list = null;

      Scanner scanner = new Scanner (System.in);

      while (n != -1)
     {
          System.out.println("enter a number: ");
         n = scanner.nextInt();
         if (n!= -1)
          l = insert(n, l);
     }
      odd_list = odd(l);
      even_list = even(l);
      merge_list = merge(odd_list, even_list);

     show_list(merge_list);
     System.out.println();

    }

static list odd(list y)
{
   if (y == null)
     return null;
   else
     return new list(y.first, even(y.rest));
}

static list even(list y)
{
   if (y == null)
     return null;
   else
     return odd(y.rest);
}

static list insert(int x, list y)
{
   list current = y;

   if (y == null)
     return new list(x, y);
   else
   {
     while (current.rest != null)
       current = current.rest;
     current.rest = new list(x, null);
     return y;
   }
}

static list merge(list x, list y)
{
if (x == null)
    return y;
else if (y == null)
    return x;
else
{
    if (x.first < y.first)
      return new list(x.first, merge(x.rest, y));
    else
      return new list(y.first, merge(x, y.rest));
}
}

static void show_list(list y)
{
if(y != null)
{
   System.out.print(y.first + " ");
   show_list(y.rest);
}
}

}

Saturday, October 27, 2012

Homework 7