Instructions:Here is my class file (Sorts.java):
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.
Expand|Select|Wrap|Line Numbers
- 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:
Expand|Select|Wrap|Line Numbers
- 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.IndexOutOfBoundsException: Index: 1982399355, Size: 100Note: the 1982388355 value in the above error message is the first value in my randomly generated array.
at java.util.ArrayList.RangeCheck(Unknown Source)
at java.util.ArrayList.get(Unknown Source)
at Sorts.bubbleSort(Sorts.java:41)
at QuadSortTester.main(QuadSortTester.java:24)
Any help that you could provide in getting this program to work would be much appreciated! Thanks in advance!