In a given array of integers, there are two arbitrary segments. We want to exchange their positions, such that regard each segment itself only, the elements' relative positions are not changed. The the order of the segments are changed. We can give two examples to illustrate the requirement. We also want the array operation to be in-place, namely we don't try to allocate more resource so we can keep the program low memory profile.

Swapping ...[D][E][F]... [A][B]... to ...[A][B]... [D][E][F]... or, ...[D][E]...[A][B][C]... to ...[A][B][C]... [D][E]... The segments don't have to be sorted. Just re-ordering.

When the two segments' sizes are equal, it is a trivia case.

/** * Swapping [D][E]... [A][B] to [A][B]... [D][E] * Requiring length |DE| equal to length |AB|/ * @param arr the array has the two segments * @param r_s starting position of the right segment * @param r_e end position of the right segment * @param l_s starting position of the left segment * @param l_e end position of the left segment */ public static void equalLengthSwap(int[] arr,int l_s, int l_e, int r_s, int r_e) { if (null == arr) { // throw new RuntimeException("null == arr"); return; } // at least length one and not overlapping if (!(l_s <= l_e && l_e < r_s && r_s <= r_e)) { // throw new RuntimeException("Illegal arguments : !(l_s <= l_e && l_e < r_s && r_s <= r_e)"); return; } // equal length if (!(r_e - r_s == l_e - l_s)) { // throw new RuntimeException("Illegal arguments : not equal lengths // !(r_e - r_s == l_e - l_s)"); return; } int len = r_e - r_s + 1; for (int i = 0; i < len; i++) { int t = arr[r_s + i]; arr[r_s + i] = arr[l_s + i]; arr[l_s + i] = t; } // System.out.println(Arrays.toString(arr)); }

While dealing with the segments without equal length, we can formalize the algorithm as the following. We also restrain our design by not using recursion, since recursion will also increase memory profile. It may also be easy to debug in while loop than recursion when we have many parameters to pass among recursion stack.

We know we the length of each segments, so we know the total count of elements to be moved. while elements moved < total count to be moved if remaining elements counts in the right and left are equal call the equal length segments swap function the count is increased by two times the remaining single segment count this will end the loop equal to end condition of recursion else if the right segment length less than the left do equal length swap between the left most part of the left and the right, by right segment length truncate the left side increase the count by right side length else do equal length swap between the right most part of the right and the left, by left segment length truncate the right side increase the count by left side length

This method may be used for memory manipulation in a very stressed situation. We also use it for the design of an in-place merge sort implementation. We attach the implementation and test cases.

package net.heteroclinic.algorithm; import java.util.Arrays; /** * Copyright 2017 Zhikai Wang <www.heteroclinic.net>. All rights reserved. * Science and Technology Promotion License * All third-party licenses are automatically cascaded. * Non-commercial usage of this file is not limited. * Commercial usage is allowed, given this file is not modified. * Inheritance/overriding/re-factoring is suggested at higher level. * This is a good-will software. Users' liability always. */ /** * {@code InPlaceSwap} is a class for prototyping, proof-of-concept purpose. * For an integer array, exchange positions of two arbitrary continuous segements. * Swapping * ...[D][E][F]... [A][B]... * to * ...[A][B]... [D][E][F]... * or, * ...[D][E]...[A][B][C]... * to * ...[A][B][C]... [D][E]... * The segments don't have to be sorted. Just re-ordering. * * @author zhikai * */ public class InPlaceSwap { /** * Swapping [D][E]... [A][B] to [A][B]... [D][E] * Requiring length |DE| equal to length |AB|/ * @param arr the array has the two segments * @param r_s starting position of the right segment * @param r_e end position of the right segment * @param l_s starting position of the left segment * @param l_e end position of the left segment */ public static void equalLengthSwap(int[] arr,int l_s, int l_e, int r_s, int r_e) { if (null == arr) { // throw new RuntimeException("null == arr"); return; } // at least length one and not overlapping if (!(l_s <= l_e && l_e < r_s && r_s <= r_e)) { // throw new RuntimeException("Illegal arguments : !(l_s <= l_e && l_e < r_s && r_s <= r_e)"); return; } // equal length if (!(r_e - r_s == l_e - l_s)) { // throw new RuntimeException("Illegal arguments : not equal lengths // !(r_e - r_s == l_e - l_s)"); return; } int len = r_e - r_s + 1; for (int i = 0; i < len; i++) { int t = arr[r_s + i]; arr[r_s + i] = arr[l_s + i]; arr[l_s + i] = t; } // System.out.println(Arrays.toString(arr)); } /** * Swapping * ...[D][E][F]... [A][B]... * to * ...[A][B]... [D][E][F]... * or, * ...[D][E]...[A][B][C]... * to * ...[A][B][C]... [D][E]... * @param arr the array has the two segments * @param r_s starting position of the right segment * @param r_e end position of the right segment * @param l_s starting position of the left segment * @param l_e end position of the left segment */ public static void inPlaceSegmentsSwap(int[] arr,int l_s, int l_e, int r_s, int r_e) { if (null == arr) { // throw new RuntimeException("null == arr"); return; } // at least length one and not overlapping, and no over array boundary if (!(l_s <= l_e && l_e < r_s && r_s <= r_e && r_e < arr.length)) { throw new RuntimeException("!(l_s <= l_e && l_e < r_s && r_s <= r_e && r_e < arr.length)"); //return; } int totalCountToSettle = r_e - r_s + 2 + l_e - l_s; int c = 0; while (c < totalCountToSettle) { int r_len = r_e - r_s + 1; int l_len = l_e - l_s + 1; if (r_len == l_len) { equalLengthSwap(arr, l_s, l_e, r_s, r_e); c += r_len * 2; } else if (l_len < r_len) { equalLengthSwap(arr, l_s, l_e,r_e-l_len+1, r_e); //equalLengthSwap(arr, r_s, r_e, l_e - r_len + 1, l_e); c += l_len ; r_e =r_e -l_len; //r_s =r_s + l_len; } else {// r_len < l_len //equalLengthSwap(arr, r_s, r_s+l_len-1, l_s, l_e); equalLengthSwap(arr, l_s,l_s+r_len-1, r_s, r_e); c += r_len; //l_s =l_s +l_len; l_s = l_s + r_len; } } if (c > totalCountToSettle) { throw new RuntimeException("c>totalCountToSettle contact debugging unit"); } } public static void main(String[] args) { { int[] arr = new int[] { 3, 4, 1, 2 }; int l_s = 0; int l_e = 1; int r_s = 2; int r_e = 3; equalLengthSwap(arr, l_s, l_e,r_s, r_e ); System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4] } { int[] arr = new int[] { 1, 2, 8, 9, 6, 7, 3, 4 }; int l_s = 2; int l_e = 3; int r_s = 6; int r_e = 7; equalLengthSwap(arr, l_s, l_e,r_s, r_e ); System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 6, 7, 8, 9] } { int[] arr = new int[] {4,5, 1,2,3, }; //System.out.println(Arrays.toString(arr));//[4, 5, 1, 2, 3] int l_s = 0; int l_e = 1; int r_s = 2; int r_e = 4; inPlaceSegmentsSwap(arr,l_s, l_e, r_s, r_e ); System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5] } { int[] arr = new int[] {4, 1 }; //System.out.println(Arrays.toString(arr));//[4, 5, 1, 2, 3] int l_s = 0; int l_e = 0; int r_s = 1; int r_e = 1; inPlaceSegmentsSwap(arr,l_s, l_e, r_s, r_e ); System.out.println(Arrays.toString(arr)); // [1, 4] } { int[] arr = new int[] {0,0,4,0,0,0,0, 1 }; //System.out.println(Arrays.toString(arr));//[4, 5, 1, 2, 3] int l_s = 2; int l_e = 2; int r_s = 7; int r_e = 7; inPlaceSegmentsSwap(arr,l_s, l_e, r_s, r_e ); System.out.println(Arrays.toString(arr)); // [0, 0, 1, 0, 0, 0, 0, 4] } { int[] arr = new int[] {0,0,3,4,5,6,0,0,0,0, 1 }; //System.out.println(Arrays.toString(arr));//[4, 5, 1, 2, 3] int l_s = 2; int l_e = 5; int r_s = 10; int r_e = 10; inPlaceSegmentsSwap(arr,l_s, l_e, r_s, r_e ); System.out.println(Arrays.toString(arr)); // [0, 0, 1, 3, 4, 5, 0, 0, 0, 0, 6] } { int[] arr = new int[] {0,0,11,12,13,0,0,0,0,1,2,3, 4,5,6,8,9 }; //System.out.println(Arrays.toString(arr));//[4, 5, 1, 2, 3] int l_s = 2; int l_e = 4; int r_s = 9; int r_e = 16; inPlaceSegmentsSwap(arr,l_s, l_e, r_s, r_e ); System.out.println(Arrays.toString(arr)); // [0, 0, 1, 2, 3, 0, 0, 0, 0, 4, 5, 6, 8, 9, 11, 12, 13] } //[2, 3, 15, 16, 17, 31, 18, 32, 4, 5, 13, 19, 20, 29, 14, 30, 12, 21, 22, 28, 6, 11, 23, 27, 7, 10, 23, 26, 8, 9, 24, 25] //p,r_e,l_s,l_s+l-1 = 16,19,20,20 //l_s,l_s+l-1,l_s+l,q = 20,20,21,23 //r_s,r_e,l_s,l_e = 16,19,20,23 //TO-DO need more tests { //p,q = 16,23 // l,b,s = 1,2,1 // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int[] arr = new int[] {2, 3, 15, 16, 17, 31, 18, 32, 4, 5, 13, 19, 20, 29, 14, 30, // 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 12, 21, 22, 28, 6, 11, 23, 27, 7, 10, 23, 26, 8, 9, 24, 25 }; //System.out.println(Arrays.toString(arr));//[4, 5, 1, 2, 3] int l_s = 20; int l_e = 20; int r_s = 21; int r_e = 23; inPlaceSegmentsSwap(arr,l_s, l_e, r_s, r_e ); System.out.println(Arrays.toString(arr)); r_s = 16; r_e = 19; l_s = 20; l_e = 23; inPlaceSegmentsSwap(arr, r_s, r_e, l_s, l_e); System.out.println(Arrays.toString(arr)); } } }