+ 2

How to analyze if an algorithm is implemented well?

For example Selection Sort. https://code.sololearn.com/c3LaeS7i9I0Z/?ref=app I think first I have to analyze if my code really does what is expected. In this case: Are exchanged exactly the numbers which must be exchanged with Selection Sort? So the question remains about the "how". How do I know that my method for finding the smallest number is correct? And how do I know that my method of sorting the array is correct? (Do both methods uses the fastest way?) So that I can say in the end, Selection Sort has been implemented correctly? And what else should be considered when implementing an algorithm? Thanks :)

24th Mar 2019, 12:41 PM
Denise Roßberg
Denise Roßberg - avatar
5 ответов
+ 3
Looking good! The easy way out for shorter programs is to just put print statements everywhere and print the array after each loop iteration. Usually you'll want to write "tests", that means you know the input and the expected result and see if the functions do what they are supposed to. Especially important are tests for edge cases (0-, 1-element lists). The practice of writing tests before the actual code is called "test-driven development". For really really important programs (stuff that powers airplanes or nuclear reactors), you can also find mathematical proofs that your code is bug-free and correct. You can do this with interactive theorem provers like coq or agda for example. Or you can use Hoare Logic and do it by hand. Performance you'll just have to measure. You can use Big-O for eyeballing performance but anything beyond that is usually a lot of work. I think you've implemented selection sort correctly though :)
24th Mar 2019, 1:40 PM
Schindlabua - avatar
+ 10
For your specific case, I probably would have compared your algorithm with the following to see if the method was correct: https://www.hackerearth.com/practice/algorithms/sorting/selection-sort/tutorial/ For more complex algorithms, I don't think there is a way to prove that an algorithm is the fastest (most efficient). You could probably only prove that an implementation is not the most efficient by coming up with a more efficient implementation.
25th Mar 2019, 2:37 AM
Sonic - avatar
+ 2
Schindlabua Thank you very much. Akshay Karande Yes your right. But a print statement can not say if you found the smallest number in an effective way. You can only see if it is right or wrong. Maybe I did not explain my question well enough, but Schindlabua understood me.
24th Mar 2019, 2:23 PM
Denise Roßberg
Denise Roßberg - avatar
+ 1
I think u want to check whether ur algorithm is sorting by finding smallest number. To check this, simply print minimum number in getMin() before returning an index.
24th Mar 2019, 1:47 PM
Akshay Karande
use it 😂😂😂
25th Mar 2019, 3:24 AM
Anshumaan Mishra