Yeah, you're right. It'll work only for consecutive elements. And by swapping only consecutive elements, it'll take many swaps to sort the array.
Another way would be to start from the left and every time you hit an element larger than the previous one, call reverse successively until all elements are in order. example: 8 7 4 2 3 9 Here, 3 > 2, so reverse (4), 3 2 4 7 8 9 reverse (1) 2 3 4 7 8 9 now continue, but look for smaller elements than the previous. in above example, if number was 5 (instead of 3, two more reverse calls would be required). On Sep 18, 9:13 pm, Krunal Modi <[email protected]> wrote: > @Minotauras: > > There are some problems in you swap(x,y) > in your example : for reverse(3) you have considered 0 based indexing > and for reverse(2) 1 based index !! > see: > Original array : 1 8 3 4 5 and we want to swap(2,3) // swap 3 and 4. > Means, 0 BASED INDEX > > reverse(3): 4 3 8 1 5 > reverse(2): 8 3 4 1 5 <-------- > reverse(3): 1 4 3 8 5 > > AND > > If you meant swap(x,y) => rev(y) ; rev(1) ; rev(y) then, your > swap(x,y) can't be used in ALL sorting algos. > > For example, > Original array : 1 4 3 2 > and we want to swap(1,3) // because we want 1 2 3 4 > so.... > rev(3) - 2 3 4 1 > rev(1) - 3 2 4 1 > rev(3) - 1 4 2 3 > > So we have a restriction of swapping only two consecutive numbers.... > so...In swap(x,y) x is not needed because {x<y && x+1=y} > > On Sep 17, 12:17 am, Minotauraus <[email protected]> wrote: > > > > > > > > > write a function swap(x, y) > > which does: > > reverse(y) > > reverse(1) > > reverse(y) > > > so 1 8 3 4 5, swap (2, 3) // swap 3 and 4 > > reverse(3) gives: 4 3 8 1 5 > > reverse(2) : 3 4 8 1 5 > > reverse(3): 1 8 3 4 5 //thus we have swapped 3, 4 using the reverse(x) > > function. > > > Use any sorting algorithm and you'll need 3k * n(log n) > > assuming reverse(x) takes O(k) > > > I guess there is a way to optimize the number of reverse(x) calls > > > On Sep 16, 8:41 am, Srinivas <[email protected]> wrote: > > > > You have been given a function rev(x) which works as follows: > > > It reverses a[0] to a[x] elements of a. > > > e.g. Given array is > > > a : 1 8 3 4 5 > > > rev(3) will convert the array to > > > a : 4 3 8 1 5 > > > Use this function only (and comparison, of course) to sort given array > > > 'a'. The only criterion is > > > that the number of times this function is called should be minimum. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
