This week's book giveaway is in the Artificial Intelligence and Machine Learning forum.
We're giving away four copies of Transfer Learning for Natural Language Processing (MEAP) and have Paul Azunre on-line!
See this thread for details.
Win a copy of Transfer Learning for Natural Language Processing (MEAP) this week in the Artificial Intelligence and Machine Learning forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • Paul Clapham
  • Devaka Cooray
  • Bear Bibeault
Sheriffs:
  • Junilu Lacar
  • Knute Snortum
  • Liutauras Vilda
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Piet Souris
Bartenders:
  • salvin francis
  • Carey Brown
  • Frits Walraven

How do I get the last element of an ArrayList<QuakeEntry> ?

 
Ranch Hand
Posts: 588
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,

Currently, I am taking this course whereby we need to using Bubble sort in place.  The thing is that we can't use compareTo etc....

But, there is a hint which is the last numSorted elements are already in sorted order.

So, I'd like to know how do use ArrayList<QuakeEntry> to get the last numSorted element in this case ?

Below is what I have attempted so far but obviously there is something that is wrong with my code :





Hope someone can give me some hints.

Thanks !

 
Marshal
Posts: 68899
275
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

tangara goh wrote:. . . need to using Bubble sort in place.

I presume you mean to sort in place with bubble sort.

The thing is that we can't use compareTo etc....

Obviously an algorithms course, so you will know what the algorithm is when you have finished. And you will know what advantages bubble sort has over quicksort and when bubble sort will run faster than merge sort. Be sure not to try writing your own sort algorithms for linked lists because of the risk of very slow execution; only do it for arrays and array lists.

And when you have finished the course, don't worry; you will probably only have to write your own sort algorithms when you are training somebody else

. . . numSorted . . .

You are passing an argument to a parameter of that name and then immediately reassigning it as a local variable. That doesn't look right. It isn't clear what that variable means. Does it mean that the caller is assuring you that a certain number of earthquakes are already sorted? If it does, then I wouldn't believe them. The following list of earthquakes is already sorted, mostly, but there is one element which needs to be moved into the previously “sorted” sublist:-

. . . use ArrayList<QuakeEntry> to get the last numSorted element in this case ? . . .

There are methods in the List interface to get() a particular element, or to get a sublist(). I am not sure what to suggest beyond that because I am not quite sure what you want to do and how that differs from a plain simple bubble sort. Surely if you have a run of elements already in order, you will simply iterate over them and take no further action.
 
Sheriff
Posts: 15519
263
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think you are misunderstanding the hint. It's not so much about the last item in the list per se but about how your iteration bounds change. It's about the last item you want to actually compare during the iteration. That is, it's really about which item you terminate the iteration with. That's what the hint refers to as "the last list item."

Think about the algorithm: you're "bubbling" the largest element up to the end of the list, right? So at the end of the first iteration, the largest value would already be at the end of the list, in its proper sort order. That means for each iteration after that, you need not compare the current value being bubbled up to the ones that have already been bubbled up before because you know those are already in the proper sort order.
 
tangara goh
Ranch Hand
Posts: 588
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

tangara goh wrote:. . . need to using Bubble sort in place.

I presume you mean to sort in place with bubble sort.

I am not sure what to suggest beyond that because I am not quite sure what you want to do and how that differs from a plain simple bubble sort. Surely if you have a run of elements already in order, you will simply iterate over them and take no further action.



Hi Campbell,

Since the forum doesn't allow attachment, I am typing out the question so that you can guide me further cos I really am keen to learn how to write the code properly.

Write the void method OnePassBubbleSort that has 2 parameters, an ArrayList of type QuakeEntry name quakeData and an int named numSorted that represents the number of times this method has already been called on this ArrayList and thus also represents the number of the elements that are guaranteed to already be where they belong when the ArrayList is sorted by magnitude.  This method makes one pass of bubble sort on the ArrayList.  It should take advantage of the fact that the last numSorted elements are already in sorted order.

Write the void method sortByMagnitudeWithBubbleSort that has one parameter, an ArrayList of type QuakeEntry named in.  If the ArrayList in has N elements in it, this method should call onePassBubbleSort N - 1 times to sort the elements in in.

Add code to sortByMagnitudeWithBubbleSort to print all the quakes before a pass, and then to print all the quakes after each pass, identifying the pass.  

Please help me to understand how should I write the Algorithm to meet the question requirements.

Tks.

 
Campbell Ritchie
Marshal
Posts: 68899
275
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I presume you know how to write a bubble sort? I am used to doing it with nested loops.
What you are doing is iterating the List in one method; for each pass you are calling a second method which represents the inner loop. I think you probably also want a swapTwoElements(List<E>, int, int) method. Two of those methods are utility methods, which should either be in a utility class or have private access.
It doesn't say anything about last elements; it says that the bottom (=right) part of the List has already been completely sorted. Remember that the completely sorted part of the List gradually enlarges until it comprises the whole List. You start not knowing that any elements are in their correct positions, so the size of the sorted part must be regarded as 0.

[rant]You have been given an over‑specified assignment requiring you to use poor method names. That assumes you have copied them correctly.
 
tangara goh
Ranch Hand
Posts: 588
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But, how do I handle the int numSorted ?  I presume this is the bottom or the last element with the biggest element.....
 
Campbell Ritchie
Marshal
Posts: 68899
275
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please don't quote the whole of a preceding post; in fact you don't need most of the quotes you are using. I have deleted the text I wrote. Also make sure not to write your text before the [/quote] otherwise it will appear to be part of the quote.

Didn't a previous post tell you how the count of sorted elements is worked out? During the first pass it is 0 but then you start counting. So when you start the second pass it is 1, and when you start the third pass it is 2, etc.
 
Junilu Lacar
Sheriff
Posts: 15519
263
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It doesn't seem like you have a good understanding of the algorithm. Have you tried sorting with this approach by hand, i.e., with paper and pencil, or even with just scraps of paper with numbers on them?
 
tangara goh
Ranch Hand
Posts: 588
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:It doesn't seem like you have a good understanding of the algorithm. Have you tried sorting with this approach by hand, i.e., with paper and pencil, or even with just scraps of paper with numbers on them?



Hi Junilu,

I understand the concept well but I am not sure why I just can't get around this numSorted thing.  
Actually, this assignment has made me re-consider if I can really do programming...

I have been working almost every day with a tiring body but I don't think this is an excuse right....anybody who is good can easily slip into development mode right...

 
Junilu Lacar
Sheriff
Posts: 15519
263
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

tangara goh wrote:
I understand the concept well but I am not sure why I just can't get around this numSorted thing.  


Well, you're contradicting yourself there. If you're not clear on the numSorted thing then you don't really understand the concept well.

 
tangara goh
Ranch Hand
Posts: 588
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:

tangara goh wrote:
I understand the concept well but I am not sure why I just can't get around this numSorted thing.  


Well, you're contradicting yourself there. If you're not clear on the numSorted thing then you don't really understand the concept well.



I think my English is not good so I don't really understand what it meant by take advantage of the fact that the last numSorted elements are already in sorted order.  Is numSorted the largest element ?
 
Junilu Lacar
Sheriff
Posts: 15519
263
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'll try to explain by way of examples:

If you have a list that contains {4, 6, 5, 3, 1, 2, 7}, then numSorted would be 1. Why? Because 7 is already where it should be in the sorted list.
If you had {4, 1, 5, 3, 2, 6, 7}, then numSorted would be 2. Why? Because 6 and 7 are already where they should be in the sorted list.
If you had {4, 1, 2, 3, 5, 6, 7}, then numSorted would be 3. Why? Because 5, 6, and 7 are already where they should be in the sorted list.

In the first case, since 7 is already where it needs to be, then you only need to run the bubble sort algorithm up to which element? Up to the element before 7, right?
In the second case, since 6 and 7 are already where they need to be, you only need to run the bubble sort up to which element? Up to the element before 6, right?
And so on.

Now translate each "up to the element before N" part to a calculation that involves numSorted and the index of N in the list.

I'll give you a chance to work through this on your own and if you still don't understand it, maybe giving you the answer will be more helpful.
 
tangara goh
Ranch Hand
Posts: 588
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:I'll try to explain by way of examples:


I'll give you a chance to work through this on your own and if you still don't understand it, maybe giving you the answer will be more helpful.



Thank you for explaining the above to me.  I took a peek at someone's answer and modified as follows :


The code that I reference wrote :


and he did not add this line : numSorted = 1;

So, if possible, I'd appreciate if you could let me  know any difference between the 2 ways that was written cos the result is the same.

 
Junilu Lacar
Sheriff
Posts: 15519
263
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why in the world would you declare a numSorted parameter and then as one of the first things you do, reassign 1 to it? What's the point of having a numSorted parameter if you do that?
 
tangara goh
Ranch Hand
Posts: 588
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:Why in the world would you declare a numSorted parameter and then as one of the first things you do, reassign 1 to it? What's the point of having a numSorted parameter if you do that?



Oyeah...thanks for highlighting to me cos your explanation mentioned that numSorted can be at any index right ? and if I were to declare as 1 then it defeat the whole purpose of the Algorithm..right ?

But, how do the computer figure out numSorted is at which index ?

Sorry...I am getting more confused now...
 
Junilu Lacar
Sheriff
Posts: 15519
263
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you're confused, don't claim that you understand the algorithm well then. Go and write numbers on pieces of paper and do the sorting by hand. But do it as if you're the computer, tracking values of i, j, and numSorted values on paper or whatever. I think this is the best way for you to get a clear understanding of what the relationship is between numSorted, the number of elements in the list, and the number of elements still left to be sorted.
 
Campbell Ritchie
Marshal
Posts: 68899
275
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Junilu Lacar wrote:. . . If you have a list that contains {4, 6, 5, 3, 1, 2, 7}, then numSorted would be 1. . . .

In order to know that, you have to,
  • 1: Iterate the List and verify that the largest element is at the right end, or
  • 2: Run one iteration of the sorting algorithm.
  • You only need to do one of those things, not both. Otherwise you have no way of knowing that any of the List's elements is in the correct position, and have to assume the number sorted is 0.

    . . . numSorted can be at any index right ? . . .
    But, how do the computer figure out numSorted is at which index ? . . .

    Don't look on it as an index; look on it as a count. I told you that yesterday.
     
    Junilu Lacar
    Sheriff
    Posts: 15519
    263
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I think the goal of breaking down the algorithm into two methods when you normally would just have a nested for-loop was to attempt to make the algorithm easier to understand. As it's clear in OP's case, it seems to have had the opposite effect.

    The "one pass" part was meant to break out the inner for-loop from the part that called the one-pass method which is the outer loop. Combining the two back together, you'd have something like this:

    In the outer loop, the numSorted loop variable will go from 0 to list.size() - 1 and when it terminates, the list will be all sorted.
     
    I’m tired of walking, and will rest for a minute and grow some wheels. This is the promise of this tiny ad:
    Two software engineers solve most of the world's problems in one K&R sized book
    https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
      Bookmark Topic Watch Topic
    • New Topic