Cole Cramer Cole Cramer - 4 months ago 15
Java Question

Bubble Sort Parallel Array

I need to read and load a data file into 2 arrays (1 parallel). The data consists of a list of 100 integers (ID#) that correspond with a double(Price) that look like this:

[ID] - [Price]

837 - 14.88

253 - 65.12

931 - 11.96

196 - 20.47

I need to use the

bubbleSort()
method to arrange the ID's(and their corresponding price) in descending order. Lastly, I need to use the Binary and Sequential search methods to locate a specific target which I will display.

My Issue - When I run this program my Sequential search is successful, but my binary search is not. I have pasted my code below in hopes that somebody will come to my rescue.

public class StoreInventory
{
public int[] storeItem = new int[200];
public double[] itemPrice = new double[200];
public int itemCount = 0;

StoreInventory() {}

public void loadItems()
{
try {
String filename = "MasterStoreInv.dat";
Scanner infile = new Scanner(new FileInputStream(filename));

while (infile.hasNext()) {
storeItem[itemCount] = infile.nextInt();
itemPrice[itemCount] = infile.nextDouble();
itemCount += 1;
}

infile.close();

} catch (IOException ex) {
itemCount = -1;
ex.printStackTrace();
}
}

public double getItemPrice(int item)
{
return itemPrice[item];
}

public void bubbleSort()
{
for (int i = 0; i < itemCount; i++) {
for (int x = 1; x < itemCount - i; x++) {
if (storeItem[x - 1] > storeItem[x] && itemPrice[x - 1] > itemPrice[x]) {
int temp = storeItem[x - 1];
double tempi = itemPrice[x - 1];
storeItem[x - 1] = storeItem[x];
itemPrice[x - 1] = itemPrice[x];
storeItem[x] = temp;
itemPrice[x] = tempi;
}
}
}
}

public int binSearch (int target)
{
int low = 0;
int high = itemCount - 1;

while(high >= low) {
int mid = (low + high) / 2;
if(storeItem[mid] == target) {
return mid;
}
if(storeItem[mid] < target) {
low = mid + 1;
}
if(storeItem[mid] > target) {
high = mid - 1;
}
}
return -1;
}

public int seqSearch (int target)
{
int ind = 0;
int found = -1;

while (ind < itemCount) {
if(target==storeItem[ind]) {
found = ind;
ind = itemCount;
}else {
++ind;
}
}
return found;
}

public static void main(String[] args)
{
StoreInventory inventory = new StoreInventory();
Scanner myScanner = new Scanner(System.in);
int target, item;
double itemPrice;


inventory.loadItems();
inventory.bubbleSort();

do {
System.out.println("Which item number do you want to see -->");
target = myScanner.nextInt();
/* Sequential Search */
item = inventory.seqSearch(target);
if (item >= 0) {
itemPrice = inventory.getItemPrice(item);
System.out.print("\nSequential search - Successful!\nID number: " + target + " Price: $" + itemPrice+ "\n");
}else {
System.out.print("\nSequential search - Failed\nID number not found\n\n");
}
/* Binary Search */
item = inventory.binSearch(target);
if (item >= 0) {
itemPrice = inventory.getItemPrice(item);
System.out.print("\nBinary search - Successful!\nID number: " + target + " Price: $" + itemPrice+ "\n\n");
}else {
System.out.print("\nBinary search - Failed\nID number not found\n\n");
}

System.out.print("Enter '1' to make another search\nEnter '0' to quit -->");

}while (myScanner.nextInt() >= 1);
myScanner.close();


}//END main

}

Answer

Your problem is here:

if (storeItem[x - 1] > storeItem[x] && itemPrice[x - 1] > itemPrice[x])

you are only moving items if both the item and the price is greater - this is not a proper sort. Imagine data such as:

5,10
1,20

These will not be swapped - and n'or will these:

1,20
5,10

You need to choose a proper ordering such as perhaps:

storeItem[x - 1] > storeItem[x] || (storeItem[x - 1] == storeItem[x] && itemPrice[x - 1] > itemPrice[x])

this will ensure that all entries have a strict order.

BTW - you may wish to consider building a class to store the pairs and making it implement Comparable.

Comments