• Post Reply Bookmark Topic Watch Topic
  • New Topic

Bubble Sort Array  RSS feed

 
Travis Westburry
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I need to read and load a data file into 2 arrays (1 paralell). 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 successfull, but my binary search is not. I have pasted my code below in hopes that somebody will come to my rescue. Thanks!

 
Knute Snortum
Sheriff
Posts: 4279
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is binSearch supposed to be recursive?
 
Campbell Ritchie
Marshal
Posts: 56541
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Travis Westburry wrote:I need . . . 2 arrays (1 paralell). . . .
you should avoid parallel arrays like the plague. They are error‑prone. Even worse when you are trying to sort arrays, because you have to swap the same elements in both. What you want is a class which encapsulates the ID and the price. I think I may have told you that already. You aren't the poor person who has been told to use parallel arrays regardless, are you?
What are you sorting by? Price? Or ID? Start by reading about object ordering. There is a good discussion in the Java™ Tutorials. It explains why you can't simply use i − j, though you might get away with that if the IDs can be relied upon to be always small and always positive. That way there is no risk of overflow, which would cause incorrect sorting. When you have read that section you will know how to write a Comparator which compares your two objects for their IDs. Or their IDs and their prices.

I thought at first you had the bubble sort method working correctly. I would put that method in another class, myself, and not do the swapping in that method. I would create a utility class like this:-I have written lots of documentation comments so as to give you full details about how the methods work. Now you can pass your array of store items and its corresponding Comparator (or in Java8 a λ) and write
For the time being forget about the empty constructor and the <T> bits.

What you are sorting on is both higher ID and higher price. What if the ID is higher and the price is lower? In that case you are treating it the same way as if both were lower. Is that what you want? You can write a Comparator which checks whether the IDs are the same, then higher price, or checks whether the prices are the same and then higher ID. “You pays your money and you takes your choice.” Which do you want?
 
Campbell Ritchie
Marshal
Posts: 56541
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knute Snortum wrote:Is binSearch supposed to be recursive?
I don't think it is usually recursive. If you look at the Arrays class' version, however, you see it doesn't return -1 for not found. You can achieve that by returning the one's complement of the expected search index:
return ~mid;
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Travis Westburry wrote:


This is actually a very weird sort. An item is only greater if *both* the item number *and* the price is larger.

What about two items where the item number (of one) is larger but the price is smaller (than the other)? In this case, the item will not be swapped, regardless of the original order.


As for the binary search, it is only using the item number, which of course, may not be in order based on this sorting algorithm.

Henry
 
Liutauras Vilda
Sheriff
Posts: 4917
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And what Henry just said, here you go, you have such a case:
837 - 14.88
931 - 11.96

Is it still the same exercise from your last weeks post?
Because I see Campbell is giving you the same good suggestions, but it seems you're not able to use them, because of restrictions in requirements.

Please specify exact requirements of your project, in this case would be the way easier to help you.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!