Hi
I have this array A = <3,2,9,0,7,5,4,8,6,1> and I want to write all its worst partitions are these correct?thanks
a1 = <0,2,9,3,7,5,4,8,6,1>
a2 = <1,9,3,7,5,4,8,6,2>
a3 = <2,3,7,5,4,8,6,9>
a4 = <3,7,5,4,8,6,9>
a5 = <4,5,7,8,6,9>
a6 = <5,7,8,6,9>
a7 = <6,8,7,9>
a8 = <7,8,9>
a9 = <8,9>
a10 = <9>
My understanding is that you want to display the worst sequence of partitions of a given array (partitions like the ones performed by quicksort).
In this case you can sort the array, and then display all "tails" of the array, starting from index 0 and ending with index n-1.
In your example, the sorted array is:
[0,1,2,3,4,5,6,7,8,9]
and then the tails are:
[0,1,2,3,4,5,6,7,8,9]
[1,2,3,4,5,6,7,8,9]
[2,3,4,5,6,7,8,9]
....
[8,9]
[9]
If you display all partitions, then this is an O(n^2) algorithm (obviously can't be improved). If you only need to display the pivots, you can do it in O(n*log n).