Method LinkList_Sort::isSorted

[samuelsoder]

The implementation of the Linked List isSorted method in src/main/java/com/thealgorithms/sorts/LinkList_Sort.java has reported cyclomatic complexity 16 by lizard.

Part 1 steps:

• [x] ~Manual calculation of cyclomatic complexity @tjog~ (Skipped)
• [x] ~Manual calculation of cyclomatic complexity @kaggenius~ (Skipped)

Part 2 steps:

• [x] Instrument code coverage manually (in a new branch called something like issue<No>/manual-instrument)
• [x] Save the result of manual and automatic instrumentation, either in this issue by screenshot or in the branch and link to it.
• [x] Add tests to improve code coverage (on a different branch than before, called something like issue<No>/increase-coverage). Assignment PDF gives more detailed steps on what steps should be taken to identify types of tests to add etc.
• [x] Create a plan or draft for refactoring the function. A clear description is required to pass the assignment.

[tjog]

The isSorted method is currently not tested by mvn test and therefore does not get counted towards the jacoco report. There is a test file for the class in src/test/java/com/thealgorithms/others/LinkList_Sort_test.java, but that does not get run since it ends in test and not Test (yeah, jUnit not very clear on this). Anyway, when the test file is renamed and moved to mirror the corresponding implementation's package com.thealgorithms.sort it turns out the tests fail. The isSorted method contains lines that always sorts the linkedlist they build, and a couple tests did assertFalse, which then failed of course.

Anyhow, fixing up the test file and removing the try (Scanner sc = new Scanner(System.in)) (it was messing with jacoco somehow), results in the following coverage report for the class and method isSorted:

Class summary


isSorted

 

[tjog]

Manual instrumentation can be viewed in https://github.com/DD2480-2022-group-7/Java/commit/e24b6851f1129b023d45d1d1bfba61d8aee58bea . It reported the same result as jacoco at 85% coverage.

[tjog]

The current implementation of the LinkList_Sort::isSorted method can only get its branch coverage increased in the switch case (no default: test case currently) and the other branches are actually unreachable code no matter the input.

Lines https://github.com/DD2480-2022-group-7/Java/blob/45e8a821573e488a4a7a672ebb1318a94a8fa167/src/main/java/com/thealgorithms/sorts/LinkList_Sort.java#L13-L15 reference the same object as the input p is not copied. Then running whatever sort algorithm was chosen on a linked list and then copying it over to "a" actually writes to p. The Arrays.sort(b) afterwards then sorts the same underlying p again, since it already should be sorted. In total, the LinkList_Sort.compare is invoked referencing a and b even though they are exactly the same, which means it will always return true, making the other branch unreachable.

[tjog]

Before being able to increase coverage the unreachable branches needs to be addressed. The commit https://github.com/DD2480-2022-group-7/Java/commit/9b5de875d4d63175ccef595fb6abd4bb264844d6 begins on that work by making the interface/implementation consistent across the different sorting options you can provide. Next steps are hard to imagine without much refactoring. The proposed new purpose of this function is not sort and check it is sorted, but only "sort by this method and return the start Node". The control that something is actually sorted should be part of the test cases, which could call this method with a sorted list.

Next steps:

• [x] Refactor method isSorted to only perform a check on the Linked List (parameters change to only being a single Node instance)
• [x] Extract the sorting by a particular method to a new method sortWith that takes the parameters int p[] , int option
• [x] Change test cases to call sortWith followed by an assertTrue on the result of calling isSorted on the value returned by sortWith

[tjog]

New tests added in https://github.com/DD2480-2022-group-7/Java/commit/a162699a9ae9fa6fa6cc3bd751aff860c10fcc8d result in 100% coverage, see the following JaCoCo report:

Entire class


sortWith method


isSorted method