The ArrayList class includes both a bubbleSort() and quickSort methods. Modify t
ID: 3547010 • Letter: T
Question
The ArrayList class includes both a bubbleSort() and quickSort methods. Modify the main program so that times for both sort methods are displayed. For timing your code in Java you can use method System.currentTimeMillis(). By getting the current time "before and after" calling a sort method,and then computing the difference, you can find how long it took in milliseconds to execute the sort.
Time both of them for various list lengths, filling the array lists with random numbers. Use at least 10 different list lengths, and be sure you include both small values and large values for the list lengths. Create a table to record the times.
Regarding the efficiency of both sorting methods, what conclusion can be reached from this experiment? Both the table and your conclusions should be included in a Word document.
Also, do not add capabilities not requested, and do not any changes to the ArrayList class. Change only the Lab4B class, to inplement the timing.
// Class implementing an array based list.
// Bubblesort and quicksort algorithms are implemented also.
class ArrayList
{
private static int SIZE; //size of the array that stores the list items
private int[] list; //array to store the list items
private int length; //amount of items in the list
// Default constructor
public ArrayList()
{
SIZE = 20;
list = new int[SIZE];
length = 0;
}
// Three-Arg constructor
public ArrayList(int size)
{
SIZE = size;
list = new int[SIZE];
length = 0;
}
// Determines whether the list is empty
public boolean isEmpty()
{
return length == 0;
}
// Prints the list elements
public void display()
{
for (int i = 0; i < length; i++)
System.out.print(list[i] + " ");
System.out.println();
}
// Adds the element x to the end of the list. List length is increased by 1
public void add(int x)
{
if (length == SIZE)
System.out.println("Insertion Error: list is full");
else
{
list[length] = x;
length++;
}
}
// Removes the element at the given location from the list.
public void removeAt(int pos)
{
for (int i = pos; i < length - 1; i++)
list[i] = list[i + 1];
length--;
}
// Returns the number of items in the list (accessor method).
public int getLength()
{
return length;
}
// Returns the size of the list (accessor method).
public int getSize()
{
return SIZE;
}
// Removes all of the items from the list
public void clear()
{
length = 0;
}
// Replaces the item in the list at the position specified by location
public void replace(int location, int item)
{
if (location < 0 || location >= length)
System.out.println("Error: invalid location");
else
list[location] = item;
}
// Adds an item to the list at the position specified by location
public void add(int location, int item)
{
if (location < 0 || location >= length)
System.out.println("Error: invalid position");
else if (length == SIZE)
System.out.println("Error: Array is full");
else
{
for (int i = length; i > location; i--)
list[ i] = list[ i - 1];
list[location] = item;
length++;
}
}
public void remove(int item)
{
for (int i = 0; i < length; i++)
if (list[i] == item)
{
removeAt(i);
i--; //consecutive values won't be all removed; that's why i-- is here
}
}
// Returns the element at location
public int get(int location)
{
int x = -1;
if (location < 0 || location >= length)
System.out.println("Error: invalid location");
else
x = list[location];
return x;
}
// The methods listed below are new additions to the ArrayList class
// Makes a deep copy to another ArrayList object
public ArrayList copy()
{
ArrayList newList = new ArrayList(this.SIZE);
newList.length = this.length;
for (int i = 0; i < length; i++)
newList.list[i] = this.list[i];
return newList;
}
// Bubble-sorts this ArrayList
public void bubbleSort()
{
for (int i = 0; i < length - 1; i++)
for (int j = 0; j < length - i - 1; j++)
if (list[j] > list[j + 1])
{
//swap list[j] and list[j+1]
int temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
}
}
// Quick-sorts this ArrayList
public void quickSort()
{
quickSort(0, length - 1);
}
// Recursive quicksort algorithm.
private void quickSort(int begin, int end)
{
int temp;
int pivot = findPivotLocation(begin, end);
// swap list[pivot] and list[end]
temp = list[pivot];
list[pivot] = list[end];
list[end] = temp;
pivot = end;
int i = begin;
int j = end - 1;
boolean iterationCompleted = false;
while (!iterationCompleted)
{
while (list[i] < list[pivot])
i++;
while ((j >= 0) && (list[pivot] < list[j]))
j--;
if (i < j)
{
//swap list[i] and list[j]
temp = list[i];
list[i] = list[j];
list[j] = temp;
i++;
j--;
} else
iterationCompleted = true;
}
//swap list[i] and list[pivot]
temp = list[i];
list[i] = list[pivot];
list[pivot] = temp;
if (begin < i - 1)
quickSort(begin, i - 1);
if (i + 1 < end)
quickSort(i + 1, end);
}
// Computes the pivot location
private int findPivotLocation(int b, int e)
{
return (b + e) / 2;
}
}
// Class to test bubblesort and quicksort algorithms implemented in ArrayList
public class Lab4B
{
public Lab4B()
{
//creating a list of integers
int n = 25;
ArrayList numbers = new ArrayList(n);
//filling the list with random integers
for (int i = 0; i < n; i++)
numbers.add((int) (Math.random() * 100));
//printing the list
System.out.println("Original list of numbers:");
numbers.display();
//testing bubblesort
ArrayList numbersCopy1 = numbers.copy();
System.out.println(" Bubble-sorted list of numbers:");
numbersCopy1.bubbleSort();
numbersCopy1.display();
//testing quicksort
ArrayList numbersCopy2 = numbers.copy();
System.out.println(" Quick-sorted list of numbers:");
numbersCopy2.quickSort();
numbersCopy2.display();
}
public static void main(String[] args)
{
Lab4B myAppl = new Lab4B();
}
}
Explanation / Answer
class ArrayList {
private static int SIZE; //size of the array that stores the list items
private int[] list; //array to store the list items
private int length; //amount of items in the list
// Default constructor
public ArrayList() {
SIZE = 20;
list = new int[SIZE];
length = 0;
}
// Three-Arg constructor
public ArrayList(int size) {
SIZE = size;
list = new int[SIZE];
length = 0;
}
// Determines whether the list is empty
public boolean isEmpty() {
return length == 0;
}
// Prints the list elements
public void display() {
for (int i = 0; i < length; i++) {
System.out.print(list[i] + " ");
}
System.out.println();
}
// Adds the element x to the end of the list. List length is increased by 1
public void add(int x) {
if (length == SIZE) {
System.out.println("Insertion Error: list is full");
} else {
list[length] = x;
length++;
}
}
// Removes the element at the given location from the list.
public void removeAt(int pos) {
for (int i = pos; i < length - 1; i++) {
list[i] = list[i + 1];
}
length--;
}
// Returns the number of items in the list (accessor method).
public int getLength() {
return length;
}
// Returns the size of the list (accessor method).
public int getSize() {
return SIZE;
}
// Removes all of the items from the list
public void clear() {
length = 0;
}
// Replaces the item in the list at the position specified by location
public void replace(int location, int item) {
if (location < 0 || location >= length) {
System.out.println("Error: invalid location");
} else {
list[location] = item;
}
}
// Adds an item to the list at the position specified by location
public void add(int location, int item) {
if (location < 0 || location >= length) {
System.out.println("Error: invalid position");
} else if (length == SIZE) {
System.out.println("Error: Array is full");
} else {
for (int i = length; i > location; i--) {
list[ i] = list[ i - 1];
}
list[location] = item;
length++;
}
}
public void remove(int item) {
for (int i = 0; i < length; i++) {
if (list[i] == item) {
removeAt(i);
i--; //consecutive values won't be all removed; that's why i-- is here
}
}
}
// Returns the element at location
public int get(int location) {
int x = -1;
if (location < 0 || location >= length) {
System.out.println("Error: invalid location");
} else {
x = list[location];
}
return x;
}
// The methods listed below are new additions to the ArrayList class
// Makes a deep copy to another ArrayList object
public ArrayList copy() {
ArrayList newList = new ArrayList(this.SIZE);
newList.length = this.length;
for (int i = 0; i < length; i++) {
newList.list[i] = this.list[i];
}
return newList;
}
// Bubble-sorts this ArrayList
public void bubbleSort() {
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - i - 1; j++) {
if (list[j] > list[j + 1]) {
//swap list[j] and list[j+1]
int temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
}
}
}
}
// Quick-sorts this ArrayList
public void quickSort() {
quickSort(0, length - 1);
}
// Recursive quicksort algorithm.
private void quickSort(int begin, int end) {
int temp;
int pivot = findPivotLocation(begin, end);
// swap list[pivot] and list[end]
temp = list[pivot];
list[pivot] = list[end];
list[end] = temp;
pivot = end;
int i = begin;
int j = end - 1;
boolean iterationCompleted = false;
while (!iterationCompleted) {
while (list[i] < list[pivot]) {
i++;
}
while ((j >= 0) && (list[pivot] < list[j])) {
j--;
}
if (i < j) {
//swap list[i] and list[j]
temp = list[i];
list[i] = list[j];
list[j] = temp;
i++;
j--;
} else {
iterationCompleted = true;
}
}
//swap list[i] and list[pivot]
temp = list[i];
list[i] = list[pivot];
list[pivot] = temp;
if (begin < i - 1) {
quickSort(begin, i - 1);
}
if (i + 1 < end) {
quickSort(i + 1, end);
}
}
// Computes the pivot location
private int findPivotLocation(int b, int e) {
return (b + e) / 2;
}
}
// Class to test bubblesort and quicksort algorithms implemented in ArrayList
public class Lab4B {
public Lab4B() {
//creating a list of integers
int n = 25;
ArrayList numbers = new ArrayList(n);
//filling the list with random integers
for (int i = 0; i < n; i++) {
numbers.add((int) (Math.random() * 100));
}
//printing the list
System.out.println("Original list of numbers:");
numbers.display();
Long[] bubblelist = new Long[10];
Long[] quicklist = new Long[10];
//testing bubblesort
ArrayList numbersCopy1 = numbers.copy();
System.out.println(" Bubble-sorted list of numbers:");
long start = System.currentTimeMillis();
numbersCopy1.bubbleSort();
long finish = System.currentTimeMillis();
numbersCopy1.display();
System.out.println("Time taken is : " + (finish - start));
bubblelist[0]=finish - start;
for (int i = 1; i < 10; i++) {
start = System.currentTimeMillis();
numbersCopy1.bubbleSort();
finish = System.currentTimeMillis();
bubblelist[i]=finish - start;
}
//testing quicksort
ArrayList numbersCopy2 = numbers.copy();
System.out.println(" Quick-sorted list of numbers:");
start = System.currentTimeMillis();
numbersCopy2.quickSort();
finish = System.currentTimeMillis();
System.out.println("Time taken is : " + (finish - start));
numbersCopy2.display();
quicklist[0]=finish - start;
for (int i = 1; i < 10; i++) {
start = System.currentTimeMillis();
numbersCopy2.quickSort();
finish = System.currentTimeMillis();
quicklist[i]=finish - start;
}
for(int i=0;i<10;i++)
{
System.out.println("Time taken by bubble sort and quick sort are as follows : " +bubblelist[i] + " " + quicklist[i] );
}
}
public static void main(String[] args) {
Lab4B myAppl = new Lab4B();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.