Quadratic Sorting Algorithm Program

[slapsh0t11]

Hello! I need help with a program that I believe I am nearly done with. However, there seems to be a few details that preclude me from success. Here is my assignment:

Instructions:

1. Add the code for the 3 quadratic sorting algorithms to the sorting template program. Add the appropriate lines of code to count the number of steps for each algorithm. (in this case, Bubble, Selection, and Insertion sorts)

2. Test each sorting algorithm for the number of steps to sort 100, 200, 400 and 800 integers and display the number of steps for each case.

Here is my class file (Sorts.java):

import java.util.*;

/**
 *  Description of Class
 *
 * @author     Blake Walsh
 * @created    October 20, 2009
 */
public class Sorts{
  private long steps;

  /**
   *  Description of Constructor
   *
   * @param  list  Description of Parameter
   */
  public Sorts(){
    steps = 0;
  }

  /**
   *  Description of the Method
   *
   * @param  list  reference to an array of integers to be sorted
   */
  public void bubbleSort(ArrayList <Integer> list){
	//replace these lines with your code
	steps = 0;
	
	for(int outer = 0; outer < list.size() - 1; outer++)
	{
		for(int inner = 0; inner < list.size() - outer - 1; inner++)
		{
			steps += 3;
			if(list.get(inner) > list.get(inner + 1))//swap inner and inner+1
			{
				steps += 4;
				int temp = list.get(inner);
				list.set(inner, list.get(inner + 1));
				list.set(inner + 1, list.get(temp));
			}
		}
	}
	
	System.out.println();
	System.out.println("Bubble Sort");
	System.out.print(steps);
	System.out.println();
  }

  /**
   *  Description of the Method
   *
   * @param  list  reference to an array of integers to be sorted
   */
  public void selectionSort(ArrayList <Integer> list){
	//replace these lines with your code
	int min, temp;
	steps = 0;
	
	for(int outer = 0; outer < list.size() - 1; outer++)
	{
		min = outer;
		for(int inner = outer + 1; inner < list.size(); inner++)
		{
			steps += 2;
			if(list.get(inner) < list.get(min))
			{
				min = inner;//a new smallest item
			}
		}
		steps += 4;
		//swap outer and min
		temp = list.get(outer);
		list.set(outer, list.get(min));
		list.set(min, temp);
	}
	
	System.out.println();
	System.out.println("Selection Sort");
	System.out.print(steps);
	System.out.println();
  }

  /**
   *  Description of the Method
   *
   * @param  list  reference to an array of integers to be sorted
   */
  public void insertionSort(ArrayList <Integer> list){
	//replace these lines with your code
	steps = 0;
	
	for(int outer = 1; outer < list.size(); outer++)
	{
		int position = outer;
		int key = list.get(position);
		//shift larger values to the right
		steps += 2;
		while(position > 0 && list.get(position - 1) > key)
		{
			steps += 2;
			list.set(position, list.get(position - 1));
			position--;
		}
		
		list.set(position, key);
	}
	
	System.out.println();
	System.out.println("Insertion Sort");
	System.out.print(steps);
	System.out.println();
  }


 /**
   *  Takes in entire vector, but will merge the following sections
   *  together:  Left sublist from a[first]..a[mid], right sublist from
   *  a[mid+1]..a[last].  Precondition:  each sublist is already in
   *  ascending order
   *
   * @param  a      reference to an array of integers to be sorted
   * @param  first  starting index of range of values to be sorted
   * @param  mid    midpoint index of range of values to be sorted
   * @param  last   last index of range of values to be sorted
   */
  private void merge(ArrayList <Comparable> a, int first, int mid, int last){
	//replace these lines with your code
	System.out.println();
	System.out.println("Merge");
	System.out.println();

  }

  /**
   *  Recursive mergesort of an array of integers
   *
   * @param  a      reference to an array of integers to be sorted
   * @param  first  starting index of range of values to be sorted
   * @param  last   ending index of range of values to be sorted
   */
  public void mergeSort(ArrayList <Comparable> a, int first, int last){
	//replace these lines with your code
	System.out.println();
	System.out.println("Merge Sort");
	System.out.println();
  }

 
  /**
   *  Accessor method to return the current value of steps
   *
   */
  public long getStepCount(){
    return steps;
  }

  /**
   *  Modifier method to set or reset the step count. Usually called
   *  prior to invocation of a sort method.
   *
   * @param  stepCount   value assigned to steps
   */
  public void setStepCount(long stepCount){
    steps = stepCount;
  }
  
   /**
   *  Interchanges two elements in an ArrayList
   *
   * @param  list  reference to an array of integers
   * @param  a     index of integer to be swapped
   * @param  b     index of integer to be swapped
   */
  public void swap(ArrayList <Comparable> list, int a, int b){
	//replace these lines with your code
	System.out.println();
	System.out.println("Swap");
	System.out.println();
  }
}

Here is my tester file:

import java.util.ArrayList;
import java.util.Random;


public class QuadSortTester
{
	private static ArrayList <Integer> list = new ArrayList <Integer> ();
	private static Random randomNumber = new Random();
	
	public static void randomArray()
	{
		for(int num = 0; num < 100; num++)//200, 400, and 800 also to use
		{
			int x = randomNumber.nextInt();
			list.add(num, x);
		}
		System.out.println(list);
	}
	
	public static void main(String[] args)
	{
		Sorts mySorter = new Sorts();
		QuadSortTester.randomArray();
		mySorter.bubbleSort(list);
		mySorter.selectionSort(list);
		mySorter.insertionSort(list);
	}
}

Here is the error message I keep receiving (after the randomly-generated array of 100*N numbers):

Exception in thread "main" java.lang.Index OutOfBoundsExce ption: Index: 1982399355, Size: 100
at java.util.Array List.RangeCheck (Unknown Source)
at java.util.Array List.get(Unknow n Source)
at Sorts.bubbleSor t(Sorts.java:41 )
at QuadSortTester. main(QuadSortTe ster.java:24)

Note: the 1982388355 value in the above error message is the first value in my randomly generated array.


Any help that you could provide in getting this program to work would be much appreciated! Thanks in advance!

[slapsh0t11]

I also have a more specific question regarding my use of the variable STEPS to count how many comparisons, gets, and sets are made for each of the three sorting algorithms in this program. Are my values for "STEPS += ??" correct? If not, what should they be and why?

[slapsh0t11]

UPDATE: I made a bad typo that prevented the program from running in the first place. I have that resolved now. Line 41's list.get(temp) should read simply "temp"

HOWEVER! I would still like you guys to assess my += operations on the steps variable to see if I have the correct values being added. I would like to compare the number of steps necessary for each sorting algorithm across the board. Thanks!

[JosAH]

... too late again ...

kind regards,

Jos

[slapsh0t11]

BUMP. I still need help getting the step values correct for each sorting algorithm.