Reverse a sorted array

Given with an sorted array A, its size is already known as "n". Now a random figure "m" ( 0 < m < n) is given, and the array A is divided into two parts: first part before m position and the second part. please write an algorithm to reverse these two parts.
prerequisite is: time(O(n)) and space(O(1)).

Any one shed some light?

Regards,
lyceum
I don't understand, if A = 1, 2, 3, 4, 5 and m = 2, would the result be 3, 4, 5, 1, 2 or 2, 1, 5, 4, 3 ?
Or 2, 1, 3, 5, 4?

hamsterman (3138) Aug 23, 2011 at 9:33pm
I don't understand, if A = 1, 2, 3, 4, 5 and m = 2, would the result be 3, 4, 5, 1, 2 or 2, 1, 5, 4, 3 ?

if A = 1,2,3,4,5 and m = 2, then the result is supposed to be 3, 4, 5, 1, 2.

Another sample:
if A = 10,20,30,40,50 and m = 2, then the result is supposed to be 30, 40, 50, 10, 20.
Last edited on
This is a very simple homework. Why not just do it yourself?
I guess it's because what's simple for some people may not be simple for others.

EDIT: Removed suggestion to use certain functions because the problem description did state that the algorithm was supposed to be written.

Hint: Think about how you can swap elements to get the desired result. First, how would you swap the elements in the beginning example array to get the desired example array? Second, how would you generalize this?

-Albatross
Last edited on
I find that getting out a piece of paper and a pencil and drawing stuff helps a lot.

Once you know how to do it, you can make the computer do it.
Part of being a programmer is to solve problems and think of ways to do it. Without that, for all the C++ you might know... it's like knowing the words in a spoken langauge, but not when to use them.

First you get an idea on how to solve it, then you spoonfeed your compiler with that idea in the way it understands it, i.e. C++ in this case.
Last edited on
+1 Duoas

Very true.

Programming is the easy part. Developing the algorithm is where the true skill lies.
Programming is the easy part. Developing the algorithm is where the true skill lies.


I only agree 50% to the above statement. Very often we have the algorithm but during the programming using certain programming language and we want to use certain constructs, it is not available so we need to craft our own. That alone takes up quite some time and it is only part of the algorithm implementation. So in the end the amount of effort needed to produce an algorithm implementation can be a lot.

That is also why in certain Uni professors, lecturers etc they like Python cuz it has lot's of data structures pre-built that you just use immediately. Java come in close as second choice. C++ STL has it but not comprehensive enough. Perl syntax make the next developer maintain-ing difficult. So as to whether Python will dominate the programming scenes remain to be seen.

As to algorithm developing, let's face it, most small to medium outfits can ill-afford a research post. Most likely only big organizations and educational institutions and military etc designate such positions instead.

Yes I do see your point about limitations of a language and I guess my word choice wasn't good, but looking at your limitations when developing an algorithm is an important part of development.

And, yes I will agree with your that most outfits cannot afford a research post.
thanks all, problem solved.
Topic archived. No new replies allowed.