Bubble Sort Parallel Array

Question

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

}

Does bubble sort parallel? Also, sorting an array on two keys at once will not produce a correctly sorted array. Say you have `[1,100],[2,90]` - which pair is greater than the other? Either sort by number or by price. — Vesper, Jul 22 '15 at 13:54

score 1 · Accepted Answer · answered Jul 22 '15 at 14:21

1

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.

answered Jul 22 '15 at 14:21

OldCurmudgeon

64,482
16
119
213

Wow, it works like a charm. Thank you so much for your help. Unfortunately, this is an assignment and the professor insists on this setup. Also, i have stared at this loop and though it works, it doesn't seem to be 'clicking' in my own personal logic. Would you mind futher explaining why this statement works rather than my initial one? Again thank you so much for help – Cole Cramer Jul 22 '15 at 14:46
@ColeCramer - As you had it before you were comparing **both** figures and only swapping them if **both** were greater. My improvement says *if the **store** is greater or the **store**s match and the **price** is greater*. Hope that helps. – OldCurmudgeon Jul 22 '15 at 15:03

Bubble Sort Parallel Array

1 Answers1