INFORMATION & COMPUTER SCIENCE DEPARTMENT, KFUPM

ICS201, SECTIONS 52  (002 Semester)

INTRODUCTION TO COMPUTER SCIENCE

LAB  #07 Searching and Sorting

 

Instructor: Bashir M. Ghandi

 


Objectives:

 

1.         Sorting Algorithms Animation Applets.

Click on each of the following links to visualize the steps involved in each of the sorting algorithms learnt in the lectures:

 

Note: The algorithm for the Quick sort applet is slightly different from the one we learnt, but they are both based of the same idea.

 

2.         Updating the algorithms to work for Comparable Objects

As we saw in the lectures, the standard sorting and searching methods work with both primitive types and objects whose classes implements the Comparable interface.

 

We can equally improve on the various sorting and searching methods we saw in the lectures by overloading the methods in the respective classes to handle array of Comparable objects.  The following two examples improved on SelectSort and LinearSearch to accept Comparable objects.

 

Example 1:  Improved Select Sort

public class SelectSort {

   public static int minimumPosition(int[] a, int from) {

      int minPos = from;

      for (int i = from + 1; i < a.length; i++)

         if (a[i] < a[minPos])

               minPos = i;

      return minPos;

   }

 

   public static int minimumPosition(Comparable[] a, int from) {

      int minPos = from;

      for (int i = from + 1; i < a.length; i++)

         if (a[i].compareTo(a[minPos])<0)

               minPos = i;

      return minPos;

   }

   public static void sort(int[] a) {

      for (int n = 0; n < a.length - 1; n++) {

         int minPos = minimumPosition(a, n);

         if (minPos != n)

            ArrayUtil.swap(a, minPos, n);

      }

   }

  

   public static void sort(Comparable[] a) {

      for (int n = 0; n < a.length - 1; n++) {

         int minPos = minimumPosition(a, n);

         if (minPos != n)

            ArrayUtil.swap(a, minPos, n);

      }

   }

}

 

 

Example 2 :  Improved Linear Search

public class LinearSearch {

   public static int search(int[] a, int v) {

      for (int i = 0; i < a.length; i++) {

         if (a[i] == v)

            return i;

      }

      return -1;

   }

  

   public static int search(Comparable[] a, Comparable v) {

      for (int i = 0; i < a.length; i++) {

         if (a[i].compareTo(v)==0)

            return i;

      }

      return -1;

   }

}

 

Notice that the  ArrayUtil class is also updated to have a swap method for handling comparable objects.  Also notice the addition of a method copyArray().  We shall make use of it later in this lab.

import java.util.Random;

 

public class ArrayUtil {

   public static int[] randomIntArray(int length, int n) {

      int[] a = new int[length];

      Random generator = new Random();

     

      for (int i = 0; i < a.length; i++)

         a[i] = generator.nextInt(n);

     

      return a;

   }

   public static void swap(int[] a, int i, int j) {

      int temp = a[i];

      a[i] = a[j];

      a[j] = temp;

   }

   public static void swap(Comparable[] a, int i, int j) {

      Comparable temp = a[i];

      a[i] = a[j];

      a[j] = temp;

   }

   public static void print(int[] a) {

      for (int i = 0; i < a.length; i++)

         System.out.print(a[i] + " ");

      System.out.println();

   }

   public static Comparable[] copyArray(Comparable[] a, int size) {

      String[] b = new String[size];

      if (size <= a.length)

         for (int i=0; i<size; i++)

           b[i] = (String) a[i];

      return b;

   }

}

 

 

3.         Comparing running time of the various algorithms using integers and comparable Strings.

An easy way of comparing the efficiency of the various algorithms is to test them with different data type and size and measure the time taken by each.

 

To do this, we fist need to simulate a stop watch which would be needed for measuring the time.  The StopWatch class shown below implements such a stop watch.

 

 

public class StopWatch {

   private long elapsedTime;

   private long startTime;

 

   public StopWatch() {

      elapsedTime = 0;

      startTime = 0;

   }

   public void start() {

      startTime = System.currentTimeMillis();

   }

   public void stop() {

      long endTime = System.currentTimeMillis();

      elapsedTime = endTime - startTime;

   }

   public long getElapsedTime() {

      return elapsedTime;

   }

}

 

Example 3:  The SortingAnalyzer application shown below is designed to measure the times taken by the various sorting methods for both integers and Comparable objects.  [Notice that the Comparable object handling  is not completed]  

import java.awt.*;

import java.awt.event.*;

import javax.swing.*;

import javax.swing.border.*;

import java.io.*;

 

public class SortingAnalizer extends JFrame {

      private String[] methods = {"Selection Sort","Insertion Sort","Merge Sort",

                                      "Quick Sort","All Sorting Methods"};

      private String method = "Selection Sort";

      private int arraySize = 100;

      private String dataType = "Integers"; 

      private JComboBox methodBox;

      private JTextField sizeT;

      private JTextField selectT;

      private JTextField insertT;

      private JTextField mergeT;

      private JTextField quickT;

      private ButtonGroup group;

      private JRadioButton integerB;

      private JRadioButton objectB;

      private int[] intArray;

      private Comparable[] allObjects, objectArray;

           

      public SortingAnalizer() throws IOException {

            super("Sorting Analizer");

            setSize(350,350);

            BufferedReader in = new BufferedReader(new FileReader("names.txt"));

            allObjects = new Comparable[1200];

            for (int i=0; i<allObjects.length; i++)

                allObjects[i] = in.readLine();

            Container cp = getContentPane();

            cp.setLayout(new BorderLayout());

            JPanel inputP = new JPanel();

            inputP.setLayout(new BoxLayout(inputP, BoxLayout.Y_AXIS));

            JPanel methodP = new JPanel();

            methodP.setBorder(new TitledBorder("Sorting Methods"));

            methodBox = new JComboBox(methods);

            methodBox.setEditable(false);

            methodP.add(methodBox);

            inputP.add(methodP);

           

            JPanel sizeP = new JPanel();

            sizeP.setLayout(new BoxLayout(sizeP, BoxLayout.X_AXIS));

            sizeP.setBorder(new EmptyBorder(10,10,10,10));

            JPanel typeP = new JPanel();

            typeP.setBorder(new TitledBorder("Data type"));

            inputP.add(sizeP);

            inputP.add(typeP);

            sizeP.add(new JLabel("Array Size [Maximum for objects is 1,200] "));

            sizeT = new JTextField("100");

            sizeP.add(sizeT);

            group = new ButtonGroup();

          integerB = new JRadioButton("Integers");

          integerB.setSelected(true);

          group.add(integerB);

          typeP.add(integerB);

          objectB = new JRadioButton("Objects");

          group.add(objectB);

          typeP.add(objectB);

            JPanel outputP = new JPanel();

            outputP.setLayout(new FlowLayout());

            JPanel labelP = new JPanel();

            labelP.setLayout(new GridLayout(4,1));

            JPanel resultP = new JPanel();

            resultP.setLayout(new GridLayout(4,1));

            outputP.add(labelP);

            outputP.add(resultP);

            outputP.setBorder(new TitledBorder("Time Taken"));

            labelP.add(new JLabel("Selection Sort"));

            labelP.add(new JLabel("Insertion Sort"));

            labelP.add(new JLabel("Merge Sort"));

            labelP.add(new JLabel("Quick Sort"));

            selectT = new JTextField(15);

            insertT = new JTextField();

            mergeT = new JTextField();

            quickT = new JTextField();

            resultP.add(selectT);

            resultP.add(insertT);

            resultP.add(mergeT);

            resultP.add(quickT);

            JPanel buttonsP = new JPanel();

            buttonsP.setLayout(new FlowLayout());

            JButton sort = new JButton("Sort");

            buttonsP.add(sort);

            cp.add(inputP, BorderLayout.NORTH);

            cp.add(outputP, BorderLayout.CENTER);    

            cp.add(buttonsP, BorderLayout.SOUTH);    

           

            sort.addActionListener(new ActionListener() {

            public void actionPerformed(ActionEvent e) {

               method = methods[methodBox.getSelectedIndex()];

               arraySize = Integer.parseInt(sizeT.getText().trim());

               if (integerB.isSelected())

                   dataType = "Integers";

               else

                   dataType = "Objects";

                  if (dataType.equals("Integers")) {

                        handleSort(intArray);

                  }

                  else {

                        if (arraySize > 1200) {

                            arraySize = 1200;

                            sizeT.setText(""+1200);

                        }

 //                     handleSort(objectArray); [You are to implement this method]

                  }    

            }

        });

      }

     

      public static void main(String[] args) throws IOException {

            SortingAnalizer f = new SortingAnalizer();

            f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

            f.show();

      }

 

      public void handleSort(int[] intArray) {

        intArray = ArrayUtil.randomIntArray(arraySize, 100000);

            StopWatch timer = new StopWatch();

            selectT.setText("");

            insertT.setText("");

            mergeT.setText("");

            quickT.setText("");

            if (method.equals(methods[0])) {

                  timer.start();

                  SelectSort.sort(intArray);

                  timer.stop();

                  selectT.setText(timer.getElapsedTime() + " milliseconds");

            }

            else if (method.equals(methods[1])) {

                  timer.start();

                  InsertSort.sort(intArray);

                  timer.stop();

                  insertT.setText(timer.getElapsedTime() + " milliseconds");

            }

            else if (method.equals(methods[2])) {

                  timer.start();

                  MergeSort.sort(intArray);

                  timer.stop();

                  mergeT.setText(timer.getElapsedTime() + " milliseconds");

            }

            else if (method.equals(methods[3])) {

                  timer.start();

                  QuickSort.sort(intArray);

                  timer.stop();

                  quickT.setText(timer.getElapsedTime() + " milliseconds");

            }

            else if (method.equals(methods[4])) {

                  timer.start();

                  SelectSort.sort(intArray);

                  timer.stop();

                  selectT.setText(timer.getElapsedTime() + " milliseconds");

              intArray = ArrayUtil.randomIntArray(arraySize, 100000);

                  timer.start();

                  InsertSort.sort(intArray);

                  timer.stop();

                  insertT.setText(timer.getElapsedTime() + " milliseconds");

              intArray = ArrayUtil.randomIntArray(arraySize, 100000);

                  timer.start();

                  MergeSort.sort(intArray);

                  timer.stop();

                  mergeT.setText(timer.getElapsedTime() + " milliseconds");

              intArray = ArrayUtil.randomIntArray(arraySize, 100000);

                  timer.start();

                  QuickSort.sort(intArray);

                  timer.stop();

                  quickT.setText(timer.getElapsedTime() + " milliseconds");

            }

      }

}

 

 

 

4.         Assignment:

  1. Improve each of the following classes so that they work for both Integer and Comparable objects.  Test each modification by writing a simple text-based application to sort/search an array of Strings created from the file, names.txt.  The classes to be modified are:

 

Note:  All the relevant  files can also be obtained from the folder, ICS201/cs/labs/lab07,  on my computer (icswww) by login in as guest (for both username and password).

 

  1. Complete the application in example 3 by overloading the handleSort() method so that it works for Comparable objects.  Hint:  Make use of the copyarray() method defined in the ArrayUtil class to initialize the array variable, objectArray with the required number of elements (arraySize) from the allObjects array already inilialized, and then sort it.  DO NOT sort the allObjects array itself.

 

  1. Write an application similar to the one in example three to analyze the two searching methods.  Your application should work both for integers and comparable objects.