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

Binary insertionSort with ArrayList

 
Greenhorn
Posts: 8
Eclipse IDE Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello, I have to implement binary insertion sort with arraylist, but there is somewhere bug, which I haven't found yet.



The first line is unsorted list, the second should be sorted, but it isn't.



I would be glad if someone could help me


 
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
1. Add println() statements at critical steps along the way showing the current order, which elements are being compared/swapped, the result of the comparison, etc.--anything you think may be relevant.

2. Work through the process by hand, keeping track of those same intermediate values along the way.

3. Where the output from #1 differs from your manual results from #2, you've found the location of the bug, or at least narrowed it down to the code between the last printout and the current one.

4. Continue refining the above until you have found the problem.
 
Rene Ott
Greenhorn
Posts: 8
Eclipse IDE Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well, I'm still struggling with the problem. I made separate binary search method to make the code more readable.

I found the problem, but I don't know how to solve it :/.

This is the debugging output:



The problematic part:



It should stop searching position when MIDDLE == 1 and then return the MIDDLE to insert element (2) into that positon. But it goes forward until MIDDLE== 0, and then it inserts element into position 0.

Result is [2,1,3], but not [1,2,3].


 
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You might do well to sort an array. Look at what it says in the API about Collections#sort(). Creating an array, which is probably easy from your ArrayList (look through its documentation), and turning the array back to a List, are quite quick. You will probably find it easier to sort an array.
 
Tell me how it all turns out. Here is a tiny ad:
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
reply
    Bookmark Topic Watch Topic
  • New Topic