JAVA - I\'m having trouble finding the problem in this program. I need it to run
ID: 3690043 • Letter: J
Question
JAVA - I'm having trouble finding the problem in this program. I need it to run and find all of the values that are duplicates. Then separate them, and show which duplicates were removed from the original set of numbers. For some reason, my program will only find the duplicates up to a value of 126...I have no idea why they wont find the duplicates past that number. Thank you in advance for your help.
import java.util.*;
public class P6
{
static int reps = 0;
static int SIZE = 1000;
static ArrayList<Integer> values = new ArrayList<Integer>();
//static int[] values = new int[SIZE]; // values to be sorted
static ArrayList<Integer> dup = new ArrayList<Integer>();
static ArrayList<Integer> nondup = new ArrayList<Integer>();
static void initValues()
// Initializes the values array with random integers from 0 to 99.
{
Random rand = new Random();
for (int index = 0; index < SIZE; index++)
values.add((rand.nextInt(1000-0)));
}
static public boolean isSorted()
// Returns true if the array values are sorted and false otherwise.
{
boolean sorted = true;
for (int index = 0; index < (SIZE - 1); index++)
if (values.get(index) > values.get(index+1))
sorted = false;
return sorted;
}
static public void deleteRepeats(){
for(int index = 0; index <(SIZE-1); index++){
if(values.get(index)==values.get(index+1)){
dup.add(values.get(index));
}
else{
nondup.add(values.get(index));
}
}
System.out.println(dup.size());
System.out.println("Duplicates removed: ");
for(int i = 0; i < dup.size(); i++){
if (((i + 1) % 10) == 0){
System.out.println((dup.get(i)));
}
else{
System.out.print((dup.get(i)) + " ");
}
}
System.out.println();
System.out.println("The new sorted list is: ");
for(int j = 0;j<nondup.size();j++){
if (((j + 1) % 10) == 0)
System.out.println((nondup.get(j)));
else
System.out.print((nondup.get(j)) + " ");
}
}
static public void swap(int index1, int index2)
// Precondition: index1 and index2 are >= 0 and < SIZE.
//
// Swaps the integers at locations index1 and index2 of the values array.
{
int temp = values.get(index1);
values.set(index1, values.get(index2));
values.set(index2,temp);
}
static public void printValues()
// Prints all the values integers.
{
int value;
System.out.println("The values array is:");
for (int index = 0; index < SIZE; index++)
{
value = values.get(index);
if (((index + 1) % 10) == 0)
System.out.println(value);
else
System.out.print((value) + " ");
}
System.out.println();
}
/////////////////////////////////////////////////////////////////
//
// Selection Sort
static int minIndex(int startIndex, int endIndex)
// Returns the index of the smallest value in
// values[startIndex]..values[endIndex].
{
int indexOfMin = startIndex;
for (int index = startIndex + 1; index <= endIndex; index++)
if (values.get(index) < values.get(indexOfMin))
indexOfMin = index;
return indexOfMin;
}
static void selectionSort()
// Sorts the values array using the selection sort algorithm.
{
int endIndex = SIZE - 1;
for (int current = 0; current < endIndex; current++){
swap(current, minIndex(current, endIndex));
}
/*for (int current = 0; current < endIndex; current++){
deleteRepeats(values);
}*/
//deleteRepeats(values);
}
/////////////////////////////////////////////////////////////////
//
// Bubble Sort
static void bubbleUp(int startIndex, int endIndex)
// Switches adjacent pairs that are out of order
// between values[startIndex]..values[endIndex]
// beginning at values[endIndex].
{
for (int index = endIndex; index > startIndex; index--)
if (values.get(index) < values.get(index-1))
swap(index, index - 1);
}
static void bubbleSort()
// Sorts the values array using the bubble sort algorithm.
{
int current = 0;
while (current < (SIZE - 1))
{
bubbleUp(current, SIZE - 1);
current++;
}
}
/////////////////////////////////////////////////////////////////
//
// Short Bubble Sort
static boolean bubbleUp2(int startIndex, int endIndex)
// Switches adjacent pairs that are out of order
// between values[startIndex]..values[endIndex]
// beginning at values[endIndex].
//
// Returns false if a swap was made; otherwise, returns true.
{
boolean sorted = true;
for (int index = endIndex; index > startIndex; index--)
if (values.get(index) < values.get(index-1))
{
swap(index, index - 1);
sorted = false;
}
return sorted;
}
static void shortBubble()
// Sorts the values array using the bubble sort algorithm.
// The process stops as soon as values is sorted.
{
int current = 0;
boolean sorted = false;
while ((current < (SIZE - 1)) && !sorted)
{
sorted = bubbleUp2(current, SIZE - 1);
current++;
}
}
/////////////////////////////////////////////////////////////////
//
// Insertion Sort
static void insertItem(int startIndex, int endIndex)
// Upon completion, values[0]..values[endIndex] are sorted.
{
boolean finished = false;
int current = endIndex;
boolean moreToSearch = true;
while (moreToSearch && !finished)
{
if (values.get(current) < values.get(current-1))
{
swap(current, current - 1);
current--;
moreToSearch = (current != startIndex);
}
else
finished = true;
}
}
static void insertionSort()
// Sorts the values array using the insertion sort algorithm.
{
for (int count = 1; count < SIZE; count++)
insertItem(0, count);
}
/////////////////////////////////////////////////////////////////
//
// Merge Sort
static void merge (int leftFirst, int leftLast, int rightFirst, int rightLast)
// Preconditions: values[leftFirst]..values[leftLast] are sorted.
// values[rightFirst]..values[rightLast] are sorted.
//
// Sorts values[leftFirst]..values[rightLast] by merging the two subarrays.
{
List<Integer> tempArray = new ArrayList<Integer>(SIZE);
int index = leftFirst;
int saveFirst = leftFirst; // to remember where to copy back
while ((leftFirst <= leftLast) && (rightFirst <= rightLast))
{
if (values.get(leftFirst) < values.get(rightFirst))
{
tempArray.set(index, values.get(leftFirst));
leftFirst++;
}
else
{
tempArray.set(index,values.get(rightFirst));
rightFirst++;
}
index++;
}
while (leftFirst <= leftLast)
// Copy remaining items from left half.
{
tempArray.set(index,values.get(leftFirst));
leftFirst++;
index++;
}
while (rightFirst <= rightLast)
// Copy remaining items from right half.
{
tempArray.set(index,values.get(rightFirst));
rightFirst++;
index++;
}
for (index = saveFirst; index <= rightLast; index++)
values.set(index,tempArray.get(index));
}
static void mergeSort(int first, int last)
// Sorts the values array using the merge sort algorithm.
{
if (first < last)
{
int middle = (first + last) / 2;
mergeSort(first, middle);
mergeSort(middle + 1, last);
merge(first, middle, middle + 1, last);
}
}
/////////////////////////////////////////////////////////////////
//
// Quick Sort
static int split(int first, int last)
{
int splitVal = values.get(first);
int saveF = first;
boolean onCorrectSide;
first++;
do
{
> while (onCorrectSide) // move first toward last
if (values.get(first) > splitVal)
> else
{
first++;
<= last);
}
<= last);
while (onCorrectSide) // move last toward first
if (values.get(last) <= splitVal)
> else
{
last--;
<= last);
}
if (first < last)
{
swap(first, last);
first++;
last--;
}
} while (first <= last);
swap(saveF, last);
return last;
}
static void quickSort(int first, int last)
{
if (first < last)
{
int splitPoint;
splitPoint = split(first, last);
// values[first]..values[splitPoint - 1] <= splitVal
// values[splitPoint] = splitVal
// values[splitPoint+1]..values[last] > splitVal
quickSort(first, splitPoint - 1);
quickSort(splitPoint + 1, last);
}
}
/////////////////////////////////////////////////////////////////
//
// Heap Sort
static int newHole(int hole, int lastIndex, int item)
// If either child of hole is larger than item this returns the index
// of the larger child; otherwise it returns the index of hole.
{
int left = (hole * 2) + 1;
int right = (hole * 2) + 2;
if (left > lastIndex)
// hole has no children
return hole;
else
if (left == lastIndex)
// hole has left child only
if (item < values.get(left))
// item < left child
return left;
else
// item >= left child
return hole;
else
// hole has two children
if (values.get(left) < values.get(right))
// left child < right child
if (values.get(right) <= item)
// right child <= item
return hole;
else
// item < right child
return right;
else
// left child >= right child
if (values.get(left) <= item)
// left child <= item
return hole;
else
// item < left child
return left;
}
static void reheapDown(int item, int root, int lastIndex)
// Precondition: Current root position is "empty".
//
// Inserts item into the tree and ensures shape and order properties.
{
int hole = root; // current index of hole
int newhole; // index where hole should move to
newhole = newHole(hole, lastIndex, item); // find next hole
while (newhole != hole)
{
values.set(hole, values.get(newhole)); // move value up
hole = newhole; // move hole down
newhole = newHole(hole, lastIndex, item); // find next hole
}
values.set(hole,item); // fill in the final hole
}
static void heapSort()
// Sorts the values array using the heap sort algorithm.
{
int index;
// Convert the array of values into a heap.
for (index = SIZE/2 - 1; index >= 0; index--)
reheapDown(values.get(index), index, SIZE - 1);
// Sort the array.
for (index = SIZE - 1; index >=1; index--)
{
swap(0, index);
reheapDown(values.get(0), 0, index - 1);
}
}
/////////////////////////////////////////////////////////////////
//
// Main
public static void main(String[] args)
{
initValues();
printValues();
System.out.println("values is sorted: " + isSorted());
System.out.println();
// make call to sorting method here (just remove //)
selectionSort();
// bubbleSort();
// shortBubble();
// insertionSort();
// mergeSort(0, SIZE - 1);
// quickSort(0, SIZE - 1);
// heapSort();
printValues();
deleteRepeats();
System.out.println("values is sorted: " + isSorted());
System.out.println();
}
}
Explanation / Answer
Hi, I have modified the code. it is working fine now. Highlighted is the change here.
P6.java
import java.util.*;
public class P6
{
static int reps = 0;
static int SIZE = 1000;
static ArrayList<Integer> values = new ArrayList<Integer>();
//static int[] values = new int[SIZE]; // values to be sorted
static ArrayList<Integer> dup = new ArrayList<Integer>();
static ArrayList<Integer> nondup = new ArrayList<Integer>();
static void initValues()
// Initializes the values array with random integers from 0 to 99.
{
Random rand = new Random();
for (int index = 0; index < SIZE; index++)
values.add((rand.nextInt(1000-0)));
}
static public boolean isSorted()
// Returns true if the array values are sorted and false otherwise.
{
boolean sorted = true;
for (int index = 0; index < (SIZE - 1); index++)
if (values.get(index) > values.get(index+1))
sorted = false;
return sorted;
}
static public void deleteRepeats(){
for(int index = 0; index <(SIZE-1); index++){
if(values.get(index).intValue()==values.get(index+1).intValue()){
dup.add(values.get(index));
}
else{
nondup.add(values.get(index));
}
}
System.out.println(dup.size());
System.out.println(nondup.size());
System.out.println("Duplicates removed: ");
for(int i = 0; i < dup.size(); i++){
if (((i + 1) % 10) == 0){
System.out.println((dup.get(i)));
}
else{
System.out.print((dup.get(i)) + " ");
}
}
System.out.println();
System.out.println("The new sorted list is: ");
for(int j = 0;j<nondup.size();j++){
if (((j + 1) % 10) == 0)
System.out.println((nondup.get(j)));
else
System.out.print((nondup.get(j)) + " ");
}
}
static public void swap(int index1, int index2)
// Precondition: index1 and index2 are >= 0 and < SIZE.
//
// Swaps the integers at locations index1 and index2 of the values array.
{
int temp = values.get(index1);
values.set(index1, values.get(index2));
values.set(index2,temp);
}
static public void printValues()
// Prints all the values integers.
{
int value;
System.out.println("The values array is:");
for (int index = 0; index < SIZE; index++)
{
value = values.get(index);
if (((index + 1) % 10) == 0)
System.out.println(value);
else
System.out.print((value) + " ");
}
System.out.println();
}
/////////////////////////////////////////////////////////////////
//
// Selection Sort
static int minIndex(int startIndex, int endIndex)
// Returns the index of the smallest value in
// values[startIndex]..values[endIndex].
{
int indexOfMin = startIndex;
for (int index = startIndex + 1; index <= endIndex; index++)
if (values.get(index) < values.get(indexOfMin))
indexOfMin = index;
return indexOfMin;
}
static void selectionSort()
// Sorts the values array using the selection sort algorithm.
{
int endIndex = SIZE - 1;
for (int current = 0; current < endIndex; current++){
swap(current, minIndex(current, endIndex));
}
/*for (int current = 0; current < endIndex; current++){
deleteRepeats(values);
}*/
//deleteRepeats(values);
}
/////////////////////////////////////////////////////////////////
//
// Bubble Sort
static void bubbleUp(int startIndex, int endIndex)
// Switches adjacent pairs that are out of order
// between values[startIndex]..values[endIndex]
// beginning at values[endIndex].
{
for (int index = endIndex; index > startIndex; index--)
if (values.get(index) < values.get(index-1))
swap(index, index - 1);
}
static void bubbleSort()
// Sorts the values array using the bubble sort algorithm.
{
int current = 0;
while (current < (SIZE - 1))
{
bubbleUp(current, SIZE - 1);
current++;
}
}
/////////////////////////////////////////////////////////////////
//
// Short Bubble Sort
static boolean bubbleUp2(int startIndex, int endIndex)
// Switches adjacent pairs that are out of order
// between values[startIndex]..values[endIndex]
// beginning at values[endIndex].
//
// Returns false if a swap was made; otherwise, returns true.
{
boolean sorted = true;
for (int index = endIndex; index > startIndex; index--)
if (values.get(index) < values.get(index-1))
{
swap(index, index - 1);
sorted = false;
}
return sorted;
}
static void shortBubble()
// Sorts the values array using the bubble sort algorithm.
// The process stops as soon as values is sorted.
{
int current = 0;
boolean sorted = false;
while ((current < (SIZE - 1)) && !sorted)
{
sorted = bubbleUp2(current, SIZE - 1);
current++;
}
}
/////////////////////////////////////////////////////////////////
//
// Insertion Sort
static void insertItem(int startIndex, int endIndex)
// Upon completion, values[0]..values[endIndex] are sorted.
{
boolean finished = false;
int current = endIndex;
boolean moreToSearch = true;
while (moreToSearch && !finished)
{
if (values.get(current) < values.get(current-1))
{
swap(current, current - 1);
current--;
moreToSearch = (current != startIndex);
}
else
finished = true;
}
}
static void insertionSort()
// Sorts the values array using the insertion sort algorithm.
{
for (int count = 1; count < SIZE; count++)
insertItem(0, count);
}
/////////////////////////////////////////////////////////////////
//
// Merge Sort
static void merge (int leftFirst, int leftLast, int rightFirst, int rightLast)
// Preconditions: values[leftFirst]..values[leftLast] are sorted.
// values[rightFirst]..values[rightLast] are sorted.
//
// Sorts values[leftFirst]..values[rightLast] by merging the two subarrays.
{
List<Integer> tempArray = new ArrayList<Integer>(SIZE);
int index = leftFirst;
int saveFirst = leftFirst; // to remember where to copy back
while ((leftFirst <= leftLast) && (rightFirst <= rightLast))
{
if (values.get(leftFirst) < values.get(rightFirst))
{
tempArray.set(index, values.get(leftFirst));
leftFirst++;
}
else
{
tempArray.set(index,values.get(rightFirst));
rightFirst++;
}
index++;
}
while (leftFirst <= leftLast)
// Copy remaining items from left half.
{
tempArray.set(index,values.get(leftFirst));
leftFirst++;
index++;
}
while (rightFirst <= rightLast)
// Copy remaining items from right half.
{
tempArray.set(index,values.get(rightFirst));
rightFirst++;
index++;
}
for (index = saveFirst; index <= rightLast; index++)
values.set(index,tempArray.get(index));
}
static void mergeSort(int first, int last)
// Sorts the values array using the merge sort algorithm.
{
if (first < last)
{
int middle = (first + last) / 2;
mergeSort(first, middle);
mergeSort(middle + 1, last);
merge(first, middle, middle + 1, last);
}
}
/////////////////////////////////////////////////////////////////
//
// Quick Sort
static int split(int first, int last)
{
int splitVal = values.get(first);
int saveF = first;
boolean onCorrectSide;
first++;
do
{
> while (onCorrectSide) // move first toward last
if (values.get(first) > splitVal)
> else
{
first++;
<= last);
}
<= last);
while (onCorrectSide) // move last toward first
if (values.get(last) <= splitVal)
> else
{
last--;
<= last);
}
if (first < last)
{
swap(first, last);
first++;
last--;
}
} while (first <= last);
swap(saveF, last);
return last;
}
static void quickSort(int first, int last)
{
if (first < last)
{
int splitPoint;
splitPoint = split(first, last);
// values[first]..values[splitPoint - 1] <= splitVal
// values[splitPoint] = splitVal
// values[splitPoint+1]..values[last] > splitVal
quickSort(first, splitPoint - 1);
quickSort(splitPoint + 1, last);
}
}
/////////////////////////////////////////////////////////////////
//
// Heap Sort
static int newHole(int hole, int lastIndex, int item)
// If either child of hole is larger than item this returns the index
// of the larger child; otherwise it returns the index of hole.
{
int left = (hole * 2) + 1;
int right = (hole * 2) + 2;
if (left > lastIndex)
// hole has no children
return hole;
else
if (left == lastIndex)
// hole has left child only
if (item < values.get(left))
// item < left child
return left;
else
// item >= left child
return hole;
else
// hole has two children
if (values.get(left) < values.get(right))
// left child < right child
if (values.get(right) <= item)
// right child <= item
return hole;
else
// item < right child
return right;
else
// left child >= right child
if (values.get(left) <= item)
// left child <= item
return hole;
else
// item < left child
return left;
}
static void reheapDown(int item, int root, int lastIndex)
// Precondition: Current root position is "empty".
//
// Inserts item into the tree and ensures shape and order properties.
{
int hole = root; // current index of hole
int newhole; // index where hole should move to
newhole = newHole(hole, lastIndex, item); // find next hole
while (newhole != hole)
{
values.set(hole, values.get(newhole)); // move value up
hole = newhole; // move hole down
newhole = newHole(hole, lastIndex, item); // find next hole
}
values.set(hole,item); // fill in the final hole
}
static void heapSort()
// Sorts the values array using the heap sort algorithm.
{
int index;
// Convert the array of values into a heap.
for (index = SIZE/2 - 1; index >= 0; index--)
reheapDown(values.get(index), index, SIZE - 1);
// Sort the array.
for (index = SIZE - 1; index >=1; index--)
{
swap(0, index);
reheapDown(values.get(0), 0, index - 1);
}
}
/////////////////////////////////////////////////////////////////
//
// Main
public static void main(String[] args)
{
initValues();
printValues();
System.out.println("values is sorted: " + isSorted());
System.out.println();
// make call to sorting method here (just remove //)
selectionSort();
// bubbleSort();
// shortBubble();
// insertionSort();
// mergeSort(0, SIZE - 1);
// quickSort(0, SIZE - 1);
// heapSort();
System.out.println(" -------------------------------- ");
printValues();
System.out.println(" ------------Delete------------------- ");
deleteRepeats();
System.out.println("values is sorted: " + isSorted());
System.out.println();
}
}
Output:
Since it is a long output. I am not displaying here.
values is sorted: true
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.