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!
4 5315
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?
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 11,448
Recognized Expert MVP
... too late again ...
kind regards,
Jos
BUMP. I still need help getting the step values correct for each sorting algorithm.
Sign in to post your reply or Sign up for a free account.
Similar topics |
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)
{ return -1; }
else
|
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 is stored in a double
linked list, the whole list is sorted for the next round.
My problem appears when subjecting the program to heavy load, that is,
when I run the simulation for more than 10,000 miliseconds (every event
occurs in...
|
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;
|
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
|
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 cannot equal 0 are given by the following formula -b + or - square root of (b^2 - 4ac) / 2a.
If b^2 - 4ac = 0 then equation has a single root. if b^2 - 4ac > 0 then equation has two real roots. if b^2 - 4ac < 0 then equation has two complex...
| |
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 just half the
code and is much easier to extend to other problems." in a sorting
problem of the very first chapter.
I modified the codes in the answer part, ran it and found it is almost
the contrary case. The qsortints.c is the C code that uses...
|
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 roots” if the discriminant is negative and find the two roots when there is no error condition. DO NOT FIND THE ROOT IF THERE IS AN ERROR CONDITION.
2. use a NESTED DECISION to do the three parts of the algorithm above.
3. write a...
|
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 an appreciation for it.
So I decided to toy with some idea, just for fun and for evaluating how
rusty I'd become. "Let me write a simple functor for sorting the
elements of a collection! I will start with a simple collection of
integers.", I...
|
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 search algorithms that can be used are Linear Search and Binary Search. The sorting algorithms are bubble, selection and Insertion sort.
First, the user is asked whether he/she wants to perform a search option, a sort operation, or exit the program. If...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
| |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 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 a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |