How to analyze if an algorithm is implemented well?

Question

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 :)

Answer 1

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 :)

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

use it 😂😂😂