473,322 Members | 1,806 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

Quadratic Sorting Algorithm Program

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
4 5290
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
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
JosAH
11,448 Expert 8TB
... too late again ...

kind regards,

Jos
Oct 21 '09 #4
BUMP. I still need help getting the step values correct for each sorting algorithm.
Oct 23 '09 #5

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

Similar topics

22
by: mike | last post by:
If I had a date in the format "01-Jan-05" it does not sort properly with my sort routine: function compareDate(a,b) { var date_a = new Date(a); var date_b = new Date(b); if (date_a < date_b)...
4
by: FBM | last post by:
Hi, I am working on a program that simulates one of the elements of ATM. The simulation stores events which occurs every some milliseconds for a certain amount of time. Every time that an event...
4
by: rushik | last post by:
Hello all, I am using structure in my program, and my aim is to sort this structure based on some optimized sorting algo. structure is struct data { int account;
3
by: amitsoni.1984 | last post by:
Hi, I need to do a quadratic optimization problem in python where the constraints are quadratic and objective function is linear. What are the possible choices to do this. Thanks Amit
6
by: Trev17 | last post by:
Hello, I am new to C++ and i have tried for several hours to make a program my teacher has given me as a lab. Here is the Lab question: the roots of the quadratic equation ax^2 + bx + c = 0, a...
7
by: abracadabra | last post by:
I am reading an old book - Programming Pearls 2nd edition recently. It says, "Even though the general C++ program uses 50 times the memory and CPU time of the specialized C program, it requires...
1
by: candacefaye1 | last post by:
1. write a C++ program to decide if the coefficients of a quadratic equation have real roots. The three choices will be to write the message “zero divide” when A is zero, write the message “no real...
18
by: =?ISO-8859-1?Q?Ney_Andr=E9_de_Mello_Zunino?= | last post by:
Hello. It seems a year is all it takes for one's proficiency in C++ to become too rusty. Professionally, I've been away from the language (and from programming in general), but I still preserve...
5
by: lemlimlee | last post by:
hello, this is the task i need to do: For this task, you are to develop a Java program that allows a user to search or sort an array of numbers using an algorithm that the user chooses. The...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.