Sorting and Searching

Write a program that lets you create a binary file that contains random integers between 0 and 9999. The name and number of items to be saved in the file is to be determined by keyboard input.

// The "Ass2s3p1.java" class.
import java.awt.*;
import hsa.Console;
import java.io.*;

public class Ass2s3p1.java
{
    static Console cs = new Console ();
    static RandomAccessFile f;


    public static void main (String [] args) throws IOException
    {
     int datum;
     cs.print ("enter the name of the random numbers file: ");
     String fileName = cs.readLine ();
     cs.print ("enter how many random numbers you wish to generate: ");
     int len = cs.readInt ();
     f = new RandomAccessFile (fileName, "rw");
     for (int i = 0 ; i < len ; i++)
     {
         datum = (int) (Math.random () * 10000);
         f.writeInt (datum);
     }
     f.close ();
     cs.println("done");
    } // main method
} // Ass2s3p1.java class

Write a program that loads the file of 2.3.1 into an array and sorts them using Bubble sort.

// The "Ass2s3p2" class.
// Insertion Sort
import java.awt.*;
import hsa.TextConsole;
import java.io.*;

public class Ass2s3p2
{
    static TextConsole cs = new TextConsole ();
    static RandomAccessFile f;
    static int list [];
    static int len;
    static long startTime, stopTime;

    public static void main (String [] args) throws IOException
    {
     cs.print ("enter the name of the random numbers file: ");
     String fileName = cs.readLine ();
     readFile (fileName);
     startTime = System.currentTimeMillis ();
     new BubbleSort (list,len);
     stopTime = System.currentTimeMillis ();
     printList ();
     cs.println ("Sorting time = " + (stopTime - startTime) + " milliseconds");

    } // main method


    public static void readFile (String binFile) throws IOException
    {
     f = new RandomAccessFile (binFile, "r");
     len = (int) f.length () / 4;
     list = new int [len];
     for (int i = 0 ; i < len ; i++)
     {
         list [i] = f.readInt ();
     }
     f.close ();
    } //end readFile

    public static void printList ()
    {
     for (int i = 0 ; i < len ; i++)
     {
         if (i % 15 == 14)
          cs.println (list [i], 5);
         else
          cs.print (list [i], 5);
     }
     cs.println ();
    } //end printList
} // Ass2s3p2 class

// The "BubbleSort" class.

public class BubbleSort
{
    boolean isSorted = false;

    public BubbleSort (int list [], int len)
    {
     do
         pass (list, len);
     while (!isSorted);
    } // end constructor


    private void pass (int list [], int len)
    {
     isSorted = true;
     for (int i = 1 ; i < len ; i++)
         if (list [i - 1] > list [i])
         {
          swap (list, i - 1, i);
          isSorted = false;
         }
    } // end pass


    private void swap (int list [], int a, int b)
    {
     int temp = list [a];
     list [a] = list [b];
     list [b] = temp;
    }
} // SBubbleSort class

Write a program that loads the file of 2.3.1 into an array and sorts them using Selection sort..

// The "SelectionSort" class.

public class SelectionSort
{

    public SelectionSort (int list [], int len)
    {
     int smallest, position;
         for (int i = 0 ; i < len - 1 ; i++)
     {
         smallest = list [i];
         position = i;
         for (int j = i + 1 ; j < len ; j++)
         {
          if (smallest > list [j])
          {
              smallest = list [j];
              position = j;
          }
         }
         swap(list, i,position);
     }
    } // end constructor


    private void swap (int list [], int a, int b)
    {
     int temp = list [a];
     list [a] = list [b];
     list [b] = temp;
    }
} // SelectionSort class

Write a program that loads the file of 2.3.1 into an array and sorts them using Insertion sort.

// The "InsertionSort" class.

public class InsertionSort
{

    public InsertionSort (int list [], int len)
    {
     int i, j;
     for (i = 1 ; i < len ; i++)
     {
         j = i - 1;
         while (j >= 0 && list [i] < list [j])
             j--;
         rightShift (list, j + 1, i);
     }
    } // end constructor


    // all data moves one postion to the right, but list[b] moves to list[a]
    private void rightShift (int list [], int a, int b)
    {
     int temp;
     if (a > b)
     {
         temp = a;
         a = b;
         b = temp;
     }
     temp = list [b];
     for (int i = b ; i > a ; i--)
         list [i] = list [i - 1];
     list [a] = temp;
    } // end swap
} // InsertionSort class

Write a program that loads the file of 2.3.1 into an array and sorts them using Quick sort.

// The "QuickSort" class.

public class QuickSort
{
    public QuickSort (int list [], int len)
    {
     pivot (list, 0, len-1);
    } // end constructor


    private void pivot (int list [], int left, int right)
    {
     int middle = left;
     swap (list, left, (left + right) / 2);
     for (int i = left + 1 ; i <= right ; i++)
         if (list [i] <= list [left])
         {
          middle++;
          swap (list, i, middle);
         }
     swap (list, left, middle);
     if (left + 1 < middle)
         pivot (list, left, middle - 1);
     if (middle + 1 < right)
         pivot (list, middle + 1, right);
    } // end pivot


    private void swap (int list [], int a, int b)
    {
     int temp = list [a];
     list [a] = list [b];
     list [b] = temp;
    }
} // QuickSort class

Write a program that will search the file names.dat for specific last names entered by keyboard, using a binary search.

// The "Ass2s3p13" class.
import java.awt.*;
import java.io.*;
import hsa.Console;

public class Ass2s3p13
{
    static Console cs = new Console ();
    static RandomAccessFile f;
    static long len = 0;

    public static void main (String [] args) throws IOException
    {
     f = new RandomAccessFile ("names.dat", "r");
     len = f.length ();
     cs.print ("enter a name (enter \"stop\" to quit: ");
     String name = cs.readLine ();
     while (!name.equalsIgnoreCase ("STOP"))
     {
         int code = binarySearch (name);
         if (code == -1)
              cs.println ("sorry, " + name + " is not in our database");
         else
              cs.println (name + " is name #" + code + " in our files");
         cs.print ("enter a name (enter \"stop\" to quit: ");
         name = cs.readLine ();
     }
     cs.println ("\nbye");
     f.close ();
    } // main method


    public static int binarySearch (String myName) throws IOException
    {
     int low = 0;
     int high = (int) (len / 30 - 1);
     int middle;
     String testName;
     do
     {
         middle = (low + high) / 2;
         testName = readName (middle);
         if (myName.toUpperCase ().compareTo (testName.toUpperCase ()) < 0)
              high = middle - 1;
         if (myName.toUpperCase ().compareTo (testName.toUpperCase ()) > 0)
              low = middle + 1;
     }
     while (!myName.equalsIgnoreCase (testName) && low <= high);
     if (myName.equalsIgnoreCase (testName))
         return middle;
     return -1;

    }


    public static String readName (int p) throws IOException
    {
     f.seek (p * 30);
     byte nameBytes [] = new byte [30];
     f.readFully (nameBytes);
     return new String (nameBytes, 0).trim ();
    }
} // Ass2s3p13 class