Advanced Programming - CS239

LAB 20: Sorting algorithms –

This lab will give you practice in sorting algorithms.

 

Getting Ready: Before going any further you should:

  1. Make a directory on your N: drive for this lab. (Note: You will need to use this class in future labs.)
  2. Set up your development environment.
  3. Copy my Hand.java program from lab 17.  You should also download the Card.class and Deck.class.

 

Part I: In this part of the lab, you will implement two different sort algorithms.  Each will take in an array of char and should sort the array in ascending order.

  1. Create a class Sorter which will house your sort algorithms.
  2. There are two attributes for the Sorter class – swaps and compares.  These integer attributes will hold the number of swaps and number of comparisons made by each of the algorithms. 
  3. Create a method insertionSort which will accept an array of numbers as a parameter.  Your method should implement the insertion sort algorithm.
  4. As you create the method, you should initialize swaps and compares to 0.  Then, each time you perform a comparison increment the compares attribute and each time you must swap out a value increment the swaps attribute.
  5. Create a method bubbleSort which will accept an array of numbers as a parameter.  Your method should implement the bubble sort algorithm.
  6. As before, count the swaps and comparisons (initialize to 0 when you first enter the method).
  7.  Cread a method, printStats, which will print the number of swaps and compares values (with appropriate labels.)

 

Part II: In this part of the lab, you will test your algorithms using different data. 

  1. Create a Driver that will:
    1. Create a Sorter object.
    2. Create an array of 100 random numbers
    3. Sort the numbers using each of the sorts.  (Note: You must make an actual copy of the original array for each of the sorts to use so that you begin each sort with the same array components.)
    4. Print the sorted array and the statistics from each of the sorts in the boxed areas on the next page. Note that there is a Part III below it.

 

Name _____________      Date:  _______

Names of those you worked with _________________

 

Original String:

 

 

 

 

 

 

Insertion sort results (including stats)

 

 

 

 

 

 

 

 

 

 

 

 

Bubble Sort results (including stats)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Part III: In this part of the lab, you will sort an array of objects.

  1. In your Hand program, create a method to sort the hand into suits and values. 
  2. In cards, Spades > Hearts > Diamonds > Clubs. And the normal order of values is:  Ace > King > Queen > Jack > 10 …. 2.
  3. Create a method sortHand that will order the cards based on item number 2.
  4. In your Driver, create a deck of cards and a Hand of 10 cards.  Print the hand before and after the call to sortHand.
  5.  

Note: be sure to shuffle your deck before dealing the hand

 

Printout showing hand before and after the call to sortHand and stats

 

 

 

 

 

 

 

 

 

 

 

 

Deliverable – Disk with your source code in the root directory (nothing else should be in the root) and a printout of these pages.