By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,341 Members | 1,379 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,341 IT Pros & Developers. It's quick & easy.

Quadratic Sorting Algorithm Program

P: 16
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):
Expand|Select|Wrap|Line Numbers
  1.  
  2. import java.util.*;
  3.  
  4. /**
  5.  *  Description of Class
  6.  *
  7.  * @author     Blake Walsh
  8.  * @created    October 20, 2009
  9.  */
  10. public class Sorts{
  11.   private long steps;
  12.  
  13.   /**
  14.    *  Description of Constructor
  15.    *
  16.    * @param  list  Description of Parameter
  17.    */
  18.   public Sorts(){
  19.     steps = 0;
  20.   }
  21.  
  22.   /**
  23.    *  Description of the Method
  24.    *
  25.    * @param  list  reference to an array of integers to be sorted
  26.    */
  27.   public void bubbleSort(ArrayList <Integer> list){
  28.     //replace these lines with your code
  29.     steps = 0;
  30.  
  31.     for(int outer = 0; outer < list.size() - 1; outer++)
  32.     {
  33.         for(int inner = 0; inner < list.size() - outer - 1; inner++)
  34.         {
  35.             steps += 3;
  36.             if(list.get(inner) > list.get(inner + 1))//swap inner and inner+1
  37.             {
  38.                 steps += 4;
  39.                 int temp = list.get(inner);
  40.                 list.set(inner, list.get(inner + 1));
  41.                 list.set(inner + 1, list.get(temp));
  42.             }
  43.         }
  44.     }
  45.  
  46.     System.out.println();
  47.     System.out.println("Bubble Sort");
  48.     System.out.print(steps);
  49.     System.out.println();
  50.   }
  51.  
  52.   /**
  53.    *  Description of the Method
  54.    *
  55.    * @param  list  reference to an array of integers to be sorted
  56.    */
  57.   public void selectionSort(ArrayList <Integer> list){
  58.     //replace these lines with your code
  59.     int min, temp;
  60.     steps = 0;
  61.  
  62.     for(int outer = 0; outer < list.size() - 1; outer++)
  63.     {
  64.         min = outer;
  65.         for(int inner = outer + 1; inner < list.size(); inner++)
  66.         {
  67.             steps += 2;
  68.             if(list.get(inner) < list.get(min))
  69.             {
  70.                 min = inner;//a new smallest item
  71.             }
  72.         }
  73.         steps += 4;
  74.         //swap outer and min
  75.         temp = list.get(outer);
  76.         list.set(outer, list.get(min));
  77.         list.set(min, temp);
  78.     }
  79.  
  80.     System.out.println();
  81.     System.out.println("Selection Sort");
  82.     System.out.print(steps);
  83.     System.out.println();
  84.   }
  85.  
  86.   /**
  87.    *  Description of the Method
  88.    *
  89.    * @param  list  reference to an array of integers to be sorted
  90.    */
  91.   public void insertionSort(ArrayList <Integer> list){
  92.     //replace these lines with your code
  93.     steps = 0;
  94.  
  95.     for(int outer = 1; outer < list.size(); outer++)
  96.     {
  97.         int position = outer;
  98.         int key = list.get(position);
  99.         //shift larger values to the right
  100.         steps += 2;
  101.         while(position > 0 && list.get(position - 1) > key)
  102.         {
  103.             steps += 2;
  104.             list.set(position, list.get(position - 1));
  105.             position--;
  106.         }
  107.  
  108.         list.set(position, key);
  109.     }
  110.  
  111.     System.out.println();
  112.     System.out.println("Insertion Sort");
  113.     System.out.print(steps);
  114.     System.out.println();
  115.   }
  116.  
  117.  
  118.  /**
  119.    *  Takes in entire vector, but will merge the following sections
  120.    *  together:  Left sublist from a[first]..a[mid], right sublist from
  121.    *  a[mid+1]..a[last].  Precondition:  each sublist is already in
  122.    *  ascending order
  123.    *
  124.    * @param  a      reference to an array of integers to be sorted
  125.    * @param  first  starting index of range of values to be sorted
  126.    * @param  mid    midpoint index of range of values to be sorted
  127.    * @param  last   last index of range of values to be sorted
  128.    */
  129.   private void merge(ArrayList <Comparable> a, int first, int mid, int last){
  130.     //replace these lines with your code
  131.     System.out.println();
  132.     System.out.println("Merge");
  133.     System.out.println();
  134.  
  135.   }
  136.  
  137.   /**
  138.    *  Recursive mergesort of an array of integers
  139.    *
  140.    * @param  a      reference to an array of integers to be sorted
  141.    * @param  first  starting index of range of values to be sorted
  142.    * @param  last   ending index of range of values to be sorted
  143.    */
  144.   public void mergeSort(ArrayList <Comparable> a, int first, int last){
  145.     //replace these lines with your code
  146.     System.out.println();
  147.     System.out.println("Merge Sort");
  148.     System.out.println();
  149.   }
  150.  
  151.  
  152.   /**
  153.    *  Accessor method to return the current value of steps
  154.    *
  155.    */
  156.   public long getStepCount(){
  157.     return steps;
  158.   }
  159.  
  160.   /**
  161.    *  Modifier method to set or reset the step count. Usually called
  162.    *  prior to invocation of a sort method.
  163.    *
  164.    * @param  stepCount   value assigned to steps
  165.    */
  166.   public void setStepCount(long stepCount){
  167.     steps = stepCount;
  168.   }
  169.  
  170.    /**
  171.    *  Interchanges two elements in an ArrayList
  172.    *
  173.    * @param  list  reference to an array of integers
  174.    * @param  a     index of integer to be swapped
  175.    * @param  b     index of integer to be swapped
  176.    */
  177.   public void swap(ArrayList <Comparable> list, int a, int b){
  178.     //replace these lines with your code
  179.     System.out.println();
  180.     System.out.println("Swap");
  181.     System.out.println();
  182.   }
  183. }
  184.  
  185.  

Here is my tester file:

Expand|Select|Wrap|Line Numbers
  1. import java.util.ArrayList;
  2. import java.util.Random;
  3.  
  4.  
  5. public class QuadSortTester
  6. {
  7.     private static ArrayList <Integer> list = new ArrayList <Integer> ();
  8.     private static Random randomNumber = new Random();
  9.  
  10.     public static void randomArray()
  11.     {
  12.         for(int num = 0; num < 100; num++)//200, 400, and 800 also to use
  13.         {
  14.             int x = randomNumber.nextInt();
  15.             list.add(num, x);
  16.         }
  17.         System.out.println(list);
  18.     }
  19.  
  20.     public static void main(String[] args)
  21.     {
  22.         Sorts mySorter = new Sorts();
  23.         QuadSortTester.randomArray();
  24.         mySorter.bubbleSort(list);
  25.         mySorter.selectionSort(list);
  26.         mySorter.insertionSort(list);
  27.     }
  28. }
  29.  
  30.  

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: 100
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)
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!
Oct 21 '09 #1
Share this Question
Share on Google+
4 Replies


P: 16
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?
Oct 21 '09 #2

P: 16
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!
Oct 21 '09 #3

Expert 10K+
P: 11,448
... too late again ...

kind regards,

Jos
Oct 21 '09 #4

P: 16
BUMP. I still need help getting the step values correct for each sorting algorithm.
Oct 23 '09 #5

Post your reply

Sign in to post your reply or Sign up for a free account.