CS210: Assignments

Department of Computer Science and Engineering, IIT Kanpur

CS210: Data Structures

Dr. R. K. Ghosh

Assignment 1

Deadline for submission: Friday, 10 Aug, 2001, Midnight.

In this assignment, you are required to write a Java program to sort an array of integers using Quicksort and Mergesort algorithms and then search the array for a particular integer value using Binary Search algorithm.

You are required to write a class for this which implements the interface "SortAndSearchInterface". You can download the interface file by clicking here. It contains the following code:

/*

            * CS210: Data Structures

            * Assignment 1

            *

            *
          File       :
          SortAndSearchInterface.java

            * Description: Interface for sorting and
          searching an integer

            *        
               array.

            *

            * Department of Computer Science and
          Engineering,

            * Indian Institute of Technology, Kanpur.

            * India.

            *

            * Dated: 5 Aug, 2001.

            */

          

           public interface SortAndSearchInterface

           {

                /*

                 * Method QuickSort()
          sorts the integer array using

                 * Quick Sort
          algorithm. The pivot value is to be

                 * chosen randomly.

                 */

               

                public void QuickSort(int
          array[]);

               

               

                /*

                 * Method MergeSort()
          sorts the integer array using

                 * Merge Sort
          algorithm.

                 */

               

                public void MergeSort(int
          array[]);

               

               

                /*

                 * Method
          BinarySearch() searches for an integer value

                 * "valueToSearch" and
          returns true if successful, else

                 * returns false.
          Assumes that the array is already

                 * sorted. If it is
          not, then return value is undefined.

                 */

               

                public boolean
          BinarySearch(int array[], int valueToSearch);

               

           }

Comments explain much of what you are supposed to code. As said in the comments, the pivot value in QuickSort() is to be chosen randomly. And the BinarySearch() method will assume a sorted array as input.

Your code for the sorting/searching class should not be graphical, i.e. it should not require a GUI to run. Do not use AWT or Swing components in that code.

After you implement the above interface as a class, you will have to write another class which will contain main() function. Ask user to input integers from keyboard. Put the integers into an array and test your sorting and searching class using that array. You may also populate the array with random integers instead of reading from the keyboard. You are at liberty to write this class the way you want.

The final submission should contain only the file that contains the class which implements the sort and search. Mail that single java file as an attachment to kedar@cse.iitk.ac.in. Be sure to put some informative comment (with your Roll No and Name) in the file to identify whose file it is. Please DO NOT mail the file to any other email address.

Note: You will find the Java API documentation useful when you start to write your code. See the Resources section for that and for other references.

Page last updated 7 Aug, 2001 by Kedar