To check if a list is sorted, a typical approach is to check every element and its next element, and see if they are sorted. Intuitively, I understand it is correct. But is there a more mathematical or rigorous way to prove this? Thanks
4
-
$\begingroup$ Well yes, transitivity of order and the finiteness of the list implies this by induction. If the list is infinite, this may not be true. $\endgroup$– Rushabh MehtaCommented Dec 7, 2021 at 1:20
-
1$\begingroup$ It cannot get simpler than that. Maybe, if a < b and b < c then a < c, is something you are looking for? Or are you talking about the invariance in the approach? $\endgroup$– Gray_RhinoCommented Dec 7, 2021 at 1:21
-
$\begingroup$ @Gray_Rhino edit: yes this is close to what I am looking for. I read some more about proving transitivity on relation, now I understand. Thank you so much! $\endgroup$– seermerCommented Dec 7, 2021 at 1:26
-
$\begingroup$ @DonThousand Thanks! I was confused about the proof of transitivity and how to use it here, now I understand. $\endgroup$– seermerCommented Dec 7, 2021 at 1:30
Add a comment
|