Skip to main content
Code Review

Return to Answer

added 5 characters in body
Source Link
Billal BEGUERADJ
Billal BEGUERADJ
  • 1
  • 10
  • 25
  • 35

@MathiasEttinger gave some good tips on using Python features to simplify the code, preserving the algorithm.

Your algorithm itself is good, achieving O(n^2)\$ O(n^2)\$ complexity on both comparisons and data movement, which I think is about as good as you can get within the arbitrary constraints. Nobody is likely to use a pancake sort for real work; an ordinary selection sort moves less data with the same number of comparisons, and heapsort does better on both metrics.

The one algorithmic improvement I can think of is to make the sort adaptive, that is, to take less time on sorted or partially sorted data than it does on random data. For this, you could keep track of the last time the new value was less than the saved maximum during your find-max search. This gives you the portion of the end of the array that's already sorted - which will be zero-length if you needed to do any flips on that pass. So, if you didn't need to flip, set the new end-pointer to the last decreasing element instead of just decrementing it.

@MathiasEttinger gave some good tips on using Python features to simplify the code, preserving the algorithm.

Your algorithm itself is good, achieving O(n^2) complexity on both comparisons and data movement, which I think is about as good as you can get within the arbitrary constraints. Nobody is likely to use a pancake sort for real work; an ordinary selection sort moves less data with the same number of comparisons, and heapsort does better on both metrics.

The one algorithmic improvement I can think of is to make the sort adaptive, that is, to take less time on sorted or partially sorted data than it does on random data. For this, you could keep track of the last time the new value was less than the saved maximum during your find-max search. This gives you the portion of the end of the array that's already sorted - which will be zero-length if you needed to do any flips on that pass. So, if you didn't need to flip, set the new end-pointer to the last decreasing element instead of just decrementing it.

@MathiasEttinger gave some good tips on using Python features to simplify the code, preserving the algorithm.

Your algorithm itself is good, achieving \$ O(n^2)\$ complexity on both comparisons and data movement, which I think is about as good as you can get within the arbitrary constraints. Nobody is likely to use a pancake sort for real work; an ordinary selection sort moves less data with the same number of comparisons, and heapsort does better on both metrics.

The one algorithmic improvement I can think of is to make the sort adaptive, that is, to take less time on sorted or partially sorted data than it does on random data. For this, you could keep track of the last time the new value was less than the saved maximum during your find-max search. This gives you the portion of the end of the array that's already sorted - which will be zero-length if you needed to do any flips on that pass. So, if you didn't need to flip, set the new end-pointer to the last decreasing element instead of just decrementing it.

Source Link
Chromatix
Chromatix
  • 211
  • 1
  • 2

@MathiasEttinger gave some good tips on using Python features to simplify the code, preserving the algorithm.

Your algorithm itself is good, achieving O(n^2) complexity on both comparisons and data movement, which I think is about as good as you can get within the arbitrary constraints. Nobody is likely to use a pancake sort for real work; an ordinary selection sort moves less data with the same number of comparisons, and heapsort does better on both metrics.

The one algorithmic improvement I can think of is to make the sort adaptive, that is, to take less time on sorted or partially sorted data than it does on random data. For this, you could keep track of the last time the new value was less than the saved maximum during your find-max search. This gives you the portion of the end of the array that's already sorted - which will be zero-length if you needed to do any flips on that pass. So, if you didn't need to flip, set the new end-pointer to the last decreasing element instead of just decrementing it.