6c

Advanced Placement

Computer Science Lab

 

 

Arrays and Sorting

 

 

 

 

Introduction

 

In previous programs we learned how to create arrays to store sequential or related data during the running of a program.  In this exercise we are going to learn how to search and sort elements of an array.  We are going to deploy various sort algorithms and compare their efficiency of sorting.  In order to compare the various program we first need a method to time the program.  The listing below shows how to use the system clock to obtain a time element in milliseconds.

 

 

 

 

 

long time;

time = System.currentTimeMillis();

System.out.print(“System time is milliseconds “);

System.out.println(time);

 

 

 

 

 

By making the array large enough and the task long enough, you should be able to construct tests of various sort algorithms.  There are two sorting algorithms in your text, the selection sort and the insertion sort. In addition there is the bubble sort which is shown below:

 

 

 

 

/**

 * BubbleSortApp.java

 * WDS

 * Version 1.00 02/21/05

 */

public class BubbleSortApp

{

   

    public static void main(String[] args)

    {

          //create the array

          int[] bArr = new int[100];

 

          //instantiate the class & pass array

          ArrayBub arr;           //

          arr = new ArrayBub(bArr);

         

          arr.display();

          arr.shuffleArray();

          arr.display(); 

          arr.bubbleSort();

          arr.display();

 

    }//end main

   

}//end class

 

 

class ArrayBub

  {

     private int[] bubArray;

     private int nElems;

 

     public ArrayBub(int[] a)     // constructor

     {

          bubArray = a;

          nElems = bubArray.length;

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

          {

              bubArray[i] = i;

          }

     }//end constructor

    

     public void shuffleArray()

    {

          int temp;

          int rand;

       

          //Shuffle the deck

          for ( int i = nElems - 1; i > 0; i-- )

          {

              rand = (int)(Math.random()*(i+1));

              temp = bubArray[i];

              bubArray[i] = bubArray[rand];

              bubArray[rand] = temp;

          }

     }//end shuffleArray()

 

 

     public void display()  

     {

          for(int j = 0; j < nElems; j++)

              System.out.print(bubArray[j] + " ");              System.out.println("");

          System.out.println("");

     }//end display

 

 

     public void bubbleSort()

     {

     int out, in;

 

     for(out = nElems - 1; out > 1; out--)

     {

          for(in = 0; in < out; in++)

          {

               if( bubArray[in] > bubArray[in+1] )

               {

                   swap(in, in+1);

               }  

        }

     }            

   } // end bubbleSort()

 

 

     private void swap(int one, int two)

     {

          int temp = bubArray[one];

          bubArray[one] = bubArray[two];

          bubArray[two] = temp;

     }

 

} // end class ArrayBub

 

 

 

 

 

There are also other sorting algorithms such as shell sort and quick sort.  Listings of these can be found on various Internet sites

 

 

 

 

 

Procedure

 

A.  Experimenting with Arrays

 

1.         Start a new application and create and sort an array as above.

 

2.         Insert the timing methods and increase the size of the array so that a significant amount of time elapses.

 

 

B.  Sorts of Other Types

 

1.         Create similar programs that can using other sorting algorithms as defined in your text book.

 

2.         Add the timing method.

 

 

 

 

 

Programming Assignment

 

Write a series of programs that creates and shuffles a large enough array to evaluate each of four different sorting algorithms. 

 

Turn in a program listing your source code.  Source code should use proper formatting.  Also turn in a copy of your output as in previous assignments.  This can be obtained by running the program and then using AltPrintScreen to copy the window of the output onto the clipboard. Then paste the contents of the clipboard into WordPad and print out the document.  In addition to the source code, the output, also turn in the answer to the questions listed below.