Implement Smooth Sort

[JAPNITSINGH]

trafficstars

• [x] I have read CONTRIBUTING.md.
• [x] This pull request is all my own work -- I have not plagiarized it.
• [x] All filenames are in PascalCase.
• [x] All functions and variable names follow Java naming conventions.
• [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
• [x] All new code is formatted with clang-format -i --style=file path/to/your/file.java

[JAPNITSINGH]

Additionaly done the following to fix pervious issues:

• [x] I have run mvn pmd:check to ensure there are no pmd errors
• [x] I have run mvn checkstyle:checkstyle to ensure correct style is followed

[codecov-commenter]

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 41.97%. Comparing base (f1e2606) to head (174de3f). Report is 8 commits behind head on master.

Additional details and impacted files

@@             Coverage Diff              @@
##             master    #5236      +/-   ##
============================================
+ Coverage     40.67%   41.97%   +1.29%     
- Complexity     2502     2602     +100     
============================================
  Files           519      522       +3     
  Lines         15447    15542      +95     
  Branches       2949     2968      +19     
============================================
+ Hits           6283     6523     +240     
+ Misses         8869     8725     -144     
+ Partials        295      294       -1     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[JAPNITSINGH]

At the moment the code is way too complex. I would suggest to:

• implement LeonardoHeap (or use one of the existing implementations in heaps),
• use it in the implementation of SmoothSort.

I did try to use existing implementaions of Heaps, however Leonardo Heap is a bit different from the others since this heap contains multiple loenardo trees of very specific shapes and the root node being the right most elemnent in the list.

I can crate a new class LeonardoHeap in heaps, however I believe I might not endup using the interface Heap.java in this implementation, would that be alright?

[JAPNITSINGH]

Adding this comment to provide updates and ensure this PR is not marked as stale:

I have refactored the code, not yet pushed as I want to do some more changes and try to use the interface Heap.java I shall comment here once the changes are ready to be reviewed.

[JAPNITSINGH]

Hi @vil02 ,

I have made some modifications to the code, can you please have a look and provide comments on it.

1. I have created a new class LeonardoHeap where I have moved all the heap's functionality.
2. SmoothSort.java is now just putting elements into the heap and extracting max elements from the heap and putting it in the array.
3. I had tried to use the interface Heap.java however it did not quite work out properly with the generic T so I ended up not using it.
4. The condition array[prevRootNodeIndex].compareTo(array[indexOfRightChild]) > 0 evaluating to true and array[prevRootNodeIndex].compareTo(array[indexOfLeftChild]) > 0 to false now happens (I was greedly max-heapfying earlier which might have been the problem but it seems to be fixed now)
5. I have updated the condition on when "maxHeapifyLeonardoTree" is supposed to be called (earlier it was being called everytime)
6. I am using LeonardoNumber in my code, however I strongly feel it is better to use dynamic programing instead of recursively calculating the solutions everytime.
7. I have used SingleBitOperations for updating leonardoLevelTracker

[JAPNITSINGH]

Hi @vil02 , are any further changes required in the test cases? Or in the code perhaps?

[JAPNITSINGH]

Pushed some changes, I am yet to push some more. I will request review once done.

[JAPNITSINGH]

Hi @vil02 I have made the changes listed below and needed a few inputs:

Changes:

1. Used for-each loop in SmoothSort.java
2. Removed leonardoHeapSize
3. Removed redundant leonardo prefix in LeonardoHeap.java
4. Moved the initialization outside the constructor in LeonardoHeap.java
5. Removed getHeapsize method.
6. Modified LeonardoHeapTest.java to provide 100% coverage on running mvn clean && mvn test -Dtest=LeonardoHeapTest

I wanted your inputs on this part: I have added a LeonardoHeapHelper.java class where I have moved findConsecutiveLeonardoTreeIndices and findAllTreeIndices to the Helper class. I wanted to know if this class( and it's function names) should be renamed and moved to the bitwise operations package, or do you wish to place them else where.

For context : findConsecutiveLeonardoTreeIndices takes in a number as an input and returns the indeices first occourence of consecutive 1 bits in it's binary form. findAllTreeIndices takes in a number as an input and returns all bits that are 1 in it's binary form (in decending order)

[JAPNITSINGH]

Pushed some changes removed the Helper class and added final access modifier to variable that weren't subject to change, I am yet to push some more changes (that is the changes to shiftRootAndRestoreHeap ). I will request review once done.

[JAPNITSINGH]

Hey @vil02 , I have made some changes:

1. removed the Helper class
2. added final access modifier to variable that weren't subject to change
3. Added a few more functions to split shiftRootAndRestoreHeap into smaller chuncks make the code more readable

I tried to get rid of the while loop and use recursion but I ran into problem where I wanted the function to return two things rootNodeIndexForHeapify and treeLevelforHeapify, and I coulnd't achieve that in a clean way. So the loop exists in the code for now and I have optimized the way I used swapped (now renamed to swapRequired)

[JAPNITSINGH]

Hi @vil02, would you kindly have a look and let me know if there are more changes to be made?

[JAPNITSINGH]

Hi @vil02 , I need a liitle more time to complete the tasks, I am a bit occupird with my college. I shall update here as soon as I get time to cmplete this.

[github-actions[bot]]

This pull request has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contribution!

[github-actions[bot]]

Please reopen this pull request once you have made the required changes. If you need help, feel free to ask in our Discord server or ping one of the maintainers here. Thank you for your contribution!