1

Is there a way to swap two sections of an array without needed to create a new one? Like cutting a deck of cards? I was able to do this by allocating a new array and then inserting the top sector first then the lower sector elements after.

I have made attempts to do it without the extra array and have two temporary variables to hold the elements while the algorithm does the swapping between the sections. The thing is that my attempt would work for specific cases.

For example:

original array: 0 1 2| 3 4 5 6 7

cut at index two

swapped array:

3 4 5 6 7| 0 1 2

Improve this question
8
  • 4
    "...but it would be a bit confusing to write it down" - erm, what? Commented Sep 18, 2013 at 4:49
  • I don't know if there is. You need to store the array temporarily somewhere while you move the other half. Commented Sep 18, 2013 at 4:50
  • I should have used a better choice of words. I meant swapping between two sectors at any index in the array Commented Sep 18, 2013 at 4:54
  • This might clarify: trivial sample please Commented Sep 18, 2013 at 4:55
  • 1
    Yes, in O(n) time. See Jerry's answer. You can also do it with three smartly-done std::reverse() calls. Commented Sep 18, 2013 at 5:05

2 Answers 2

Reset to default
5

You can use std::rotate for this task. It does a left rotate of the data in the collection, so you specify a "cut" point, and it moves the elements so the one immediately after the specified cut point will be at the beginning, and those that were before the cut point will be moved to the end.

enter image description here

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

+1 Nice explanation. The tri-reverse method mentioned in general comment was a common way to do this prior to the beautiful std::rotate. A sample can be found here for anyone that is interested in one way this is doable.
For those interested, David Gries' "The Science of Programming" has a whole section (18.1) dedicated to this problem, and a (tail) recursive algorithm is presented (closely related to the GCD algorithm), where sections of equal length are swapped back and forth; the "reverse-based" algorithm is left as an exercise, and a third algorithm ("dolphin algorithm") is also mentioned, where you take one element out and move it to its destination, knocking the next element out and so on. Here's a short description and analysis of the three.
@DanielKO: The MSVC library std::rotate implements all three of those methods and selects one based on the type of iterator.
0

Yes, you can - store the first element of the second half, shift first half to the right. Assign 0'th array element to this stored number. You've just moved the first number of second half to the start. Repeat it for next etc.

Draft of the code:

for(int i = start; i < arr.size(); i++){
    double temp = arr[i];
    for(int j = start-1; j > i - start; j--){
        arr[j+1] = arr[j];
    }
    arr[i - start] = temp;
}
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.