Win a copy of Node.js Design Patterns: Design and implement production-grade Node.js applications using proven patterns and techniques this week in the Server-Side JavaScript and NodeJS 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

why this bubble sort only passed 1 test and failed the other ?

 
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

tangara goh wrote:I did it with the above lines of code with the 1 loop and 2 loops and it ended up the same hence my question here.


I just ran that code that you said is working and it is NOT producing a sorted array either way.

So we don't keep going back and forth, please post the code you're running exactly as it is written. That is, copy-paste the code you're running and saying that it's correct.
 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here's the code I'm running:

The result of that code is INCORRECT.

However, you're correct in saying that it produces the same result with 1 loop or 2 loops. So at least it's consistently wrong. But it's still wrong either way.
 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ok, I may have gone a little overboard with this but here's what I have used to play around with this problem. It shows that Alison P's code is wrong either way. It also shows how you can implement the algorithm described in the Wikipedia article I cited earlier.

It also shows that you can write your own test harness, although I wouldn't recommend it because there's already JUnit.
 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
And here's the output from the code:

*** Sorting using Wikipedia optimized algorithm

n = 4, data = [55, 44, 66, 7]
n = 3, data = [44, 55, 7, 66]
n = 2, data = [44, 7, 55, 66]
n = 1, data = [7, 44, 55, 66]
Sorted array: [7, 44, 55, 66]
Array sorted in 4 swaps
First element: 7
Last element: 66

Result ==> Pass

*** Sorting using Alison P - one loop algorithm

[55, 44, 66, 7]
[44, 55, 66, 7]
[44, 55, 66, 7]
Sorted array: [44, 55, 7, 66]
Array sorted in 2 swaps
First element: 44
Last element: 66

Result ==> FAIL

*** Sorting using Alison P - two loops algorithm

[55, 44, 66, 7]
[44, 55, 66, 7]
[44, 55, 66, 7]
[44, 55, 66, 7]
[44, 55, 66, 7]
[44, 55, 66, 7]
[44, 55, 66, 7]
[44, 55, 7, 66]
[44, 55, 7, 66]
Sorted array: [44, 55, 7, 66]
Array sorted in 2 swaps
First element: 44
Last element: 66

Result ==> FAIL

*** Sorting using Wikipedia optimized algorithm

n = 5, data = [7, 2, 9, 3, 1]
n = 4, data = [2, 7, 3, 1, 9]
n = 3, data = [2, 3, 1, 7, 9]
n = 2, data = [2, 1, 3, 7, 9]
n = 1, data = [1, 2, 3, 7, 9]
Sorted array: [1, 2, 3, 7, 9]
Array sorted in 7 swaps
First element: 1
Last element: 9

Result ==> Pass

*** Sorting using Alison P - one loop algorithm

[7, 2, 9, 3, 1]
[2, 7, 9, 3, 1]
[2, 7, 9, 3, 1]
[2, 7, 3, 9, 1]
Sorted array: [2, 7, 3, 1, 9]
Array sorted in 3 swaps
First element: 2
Last element: 9

Result ==> FAIL

*** Sorting using Alison P - two loops algorithm

[7, 2, 9, 3, 1]
[2, 7, 9, 3, 1]
[2, 7, 9, 3, 1]
[2, 7, 9, 3, 1]
[2, 7, 9, 3, 1]
[2, 7, 9, 3, 1]
[2, 7, 9, 3, 1]
[2, 7, 9, 3, 1]
[2, 7, 9, 3, 1]
[2, 7, 3, 9, 1]
[2, 7, 3, 9, 1]
[2, 7, 3, 9, 1]
[2, 7, 3, 9, 1]
[2, 7, 3, 1, 9]
[2, 7, 3, 1, 9]
[2, 7, 3, 1, 9]
Sorted array: [2, 7, 3, 1, 9]
Array sorted in 3 swaps
First element: 2
Last element: 9

Result ==> FAIL
 
Ranch Hand
Posts: 821
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Junilu Lacar wrote:

tangara goh wrote:That's the reason I am asking in this forum because I know Alison P is a super top coder.


I'm not saying her original program was wrong but you have to remember that no programmer is perfect. Even the best programmers can make mistakes. That's why testing is super important.

But now that we're here, none of the solutions so far have shown a simple optimization



Tks for the reminder Junilu, I have seen added one more loop where it start reading from the length of array -1 and while i > 0 and decrement from there to avoid going thru the whole sequence.

Now, I am running into another issue where I am trying to see if this guys's solution works or not..so far it is not working and I do not know why.  Hope you guys can let me know.





and then I tried to use the 2 utility converter method  - both not working out;



and it doesn't work in the main method either.



the error is



I hope someone can tell me what is wrong and if the latest sorting method is it good?
 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

tangara goh wrote:Now, I am running into another issue where I am trying to see if this guys's solution works or not..so far it is not working and I do not know why.  Hope you guys can let me know.


Take a good long look at the swapping logic. Is there anything missing? (Hint: there is) Can you tell us what's missing?
 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

tangara goh wrote:
the error is

I hope someone can tell me what is wrong...


At this point in your learning you really should be able to figure this one out on your own. The error message says the "argument type(s) String, void" so if you look at the expression "sorted array is: " + s.smartBubbleSort(n) which term is a String and which term is void? Does concatenating a String and void make sense? What types do you need on either side of the "+" operator instead?
 
Saloon Keeper
Posts: 1336
40
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have problems with both of the conversion methods, slightly paraphrased here:


Let's start with some Java-specific complications to the fairly easy Bubble Sort that have made things confusing here.

1. There is no two-parameter swap() method that you can call by passing two references that will just swap them for you.
I believe you are past recognizing that, but how to deal with this?

a. You can get past it using only an array by writing the swap of two elements explicitly, but you must get it right, it has 3 steps, not two.
b. Far more complicated, you can use various methods for use on List types, by converting your array for use as a List, or creating a List that corresponds to a copy of your array contents.

Now there is nothing in approach b. that a good Advanced or even Intermediate Java programmer shouldn't know, but there are a variety of tricky things that one needs to know to do this.
I. What are the limitations on what can be stored in a List, rather than an Array?
....At present, even in the latest versions of Java, you can not directly store ANY primitive types in ANY of the Collection types.  Not List, not Set, neither as keys nor as values in Map structures.
....This is an annoying limitation of Java that is not common to other languages.  We paper over this by the compiler giving us auto-boxing and auto-unboxing to and from the Wrapper types, but it actually is just invisibly adding the boxing, unboxing and casts to our code behind the scenes before compiling!  The restriction is not even specific to the Collection types, primitives can not be used as generic type parameters in general, only references to the Wrapper types around them.  This creates lumps, bumps and hassles thru-out one's use of Java, but in particular, it means that the code I show above won't compile, because you will get the error:
The method convertArraysToList(T[]) in the type BadArrayConvert is not applicable for the arguments (int[])

Additionally, were we to change the line in main to what we actually wanted to type:
ArrayList<int> intList = convertArraysToList(intArray);

We will get the error:
Syntax error, insert "Dimensions" to complete ReferenceType

That strange error is because you are allowed to use an entire ARRAY of something as a generic type parameter, e.g. this is fine:


So at this moment I question whether you want to be fussing about these Java Generics issues which are completely irrelevant to Bubble Sort, despite being essential to being an Advanced or Intermediate Java programmer.  Good bubble sort solutions can be made without getting into any of these areas.

If you just want to understand the Bubble Sort for now, and not the Java-specific problems involved in working with arrays of primitive types as if they were List objects, come back to the rest of this later.
If you want to at least see something about it (including maybe why you should avoid ArrayList/List entirely for this problem and for today) keep going.

II. For your approach to converting an Array to an ArrayList to work, the Array must be of reference type already.



I would prefer the name convertArrayToList() because that is more conventional than pluralizings it, but it would work.
It would also be unnecessary in this case, because you can work fine with a FIXED-SIZE but writable list backed by the array.
That is precisely what java.util.Arrays, method asList() gives you!


I believe the second method you had to try to convert the int[] to a List shares the same generics problems as the first and adds some of its own.
For instance, it is attempting currently to iterate over a new and empty list!

You eventually need to know Java Generics well, and the various possible ways to convert between List and Array types.
You don't need it for this problem tho.

If you really want to do the problem with List, which is questionable in the context of the original problem, you should just use Arrays.asList()
You will need to start with an array of the reference type Integer, but you would need to do that for either of your methods to work anyway.
So they do not need to be written to work with your array as a fixed-size but mutable List.
Eventually you should know how to write them and make them work, but never do so.
Always prefer a library method that has already been written, debugged, optimized and extensively tested to writing your own version of the same thing while you are trying to solve some other problem.

Okay, you could say that about writing Bubble Sort, but that was the problem they ask you to solve, so it doesn't count.
 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jesse Silverman wrote:I have problems with both of the conversion methods, slightly paraphrased here:


I see no need to go through all those gyrations, especially for this problem. The way the problem is stated strongly hints at using an int[]; using List<Integer> just unnecessarily complicates things.

If you insist on not using an int[] and performing conversions between int[] and List<Integer>, there's already Arrays.asList() and Collection.toList() so why reinvent the wheel?

Converting a List<Integer> to a primitive int[] is also fairly straightforward:

Do you really need to make it more complicated than that?
 
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic