Re: In-place list manipulation


"Aki Tuomi" <cmouse@xxxxxxxxxxx> wrote in message
news:47458372$0$3522$39db0f71@xxxxxxxxxxxxxxx
When doing mergesort in place, I have ran into a following problem:

How to perform in-place interleave during merge without need of auxilliary
list or array?

I have two sets of indexes: a.start, a.stop and b.start and b.stop. These
contain start and stop indexes in the list where the data is. My question
is, how do I do merge the two into the list in-place?

Example:

List = {1,3,2,5,4,6,7,8,9}

a.start = 1
a.stop = 2

b.start = 3
b.stop = 4

a = {3,2}
b = {5,4}

merge(a,b,List)

List = {1,2,3,4,5,6,7,8,9}

I have solved this now by copying the two segments into temporary arrays
and then copy data back from there, but it does not really feel right. Any
ideas?

Aki Tuomi


Thank you for your feedback, Richard and Gene. Here is the (almost) in-place
MergeSort with java...

This works by creating an index tree and then doing pre-order walk and
merges the segments together. So everything else works without copying data
in or out from list, but the actual merge applies some arrays.

After some thought, I realized that you need at least a.b - a.a sized array
to accomondate the values that need to be kept safe.

Aki Tuomi

public class MergeSort {
private class Pair {
public Pair(int a, int b) {
this.a = a;
this.b = b;
left = null;
right = null;
visited = false;
}

public int a;
public int b;
public Pair left;
public Pair right;
public boolean visited;

public List<Integer> values(List<Integer> list) {
return list.subList(a, b);
}

public boolean split() {
if (b - a > 0) {
int pivot = a + (b - a) / 2;
left = new Pair(a, pivot);
right = new Pair(pivot + 1, b);
return true;
}
return false;
}

public String toString() {
return "[" + a + "," + b + "]";
}
}

private void merge(Pair a, Pair b, List<Integer> list) {
// perform merge...
// need two arrays.

Integer[] aArr = new Integer[a.b - a.a + 1];
Integer[] bArr = new Integer[b.b - b.a + 1];

int aidx = 0;
int bidx = 0;
int sidx = a.a;

aArr = list.subList(a.a, a.b + 1).toArray(aArr);
bArr = list.subList(b.a, b.b + 1).toArray(bArr);

while (aidx < aArr.length || bidx < bArr.length) {
if (aidx == aArr.length) {
list.set(sidx++, bArr[bidx++]);
} else if (bidx == bArr.length) {
list.set(sidx++, aArr[aidx++]);
} else if (aArr[aidx] < bArr[bidx]) {
list.set(sidx++, aArr[aidx++]);
} else {
list.set(sidx++, bArr[bidx++]);
}
}
}

public void sort(List<Integer> list) {
Stack<Pair> stack = new Stack<Pair>();
Pair root;

// while there are splittable.
root = new Pair(0, list.size() - 1);

stack.push(root);

while (!stack.isEmpty()) {
Pair p = stack.pop();
if (p.split()) {
stack.push(p.left);
stack.push(p.right);
}
}

// walk the tree
stack.push(root);
while (!stack.isEmpty()) {
Pair p = stack.peek();
if (p.left != null && !p.left.visited) {
stack.push(p.left);
continue;
}
if (p.right != null && !p.right.visited) {
stack.push(p.right);
continue;
}
p.visited = true;
if (p.left != null && p.right != null) {
merge(p.left, p.right, list);
p.left = p.right = null;
}
stack.pop();
}
}
}


.

Relevant Pages

  • Re: why cant functions return arrays
    ... int f; ... for such a language restricton. ... have been able to pass and return fixed-size arrays by value by ... Since there were no prototypes in K&R, there was no way to inform the ...
    (comp.lang.c)
  • Re: Implementing an 8 bit fixed point register
    ... It seems like implementing ALU operations on such arrays would ... If one only wants int arithmetic and all-bits logic, ... def bitset ... your approach could be easily modified to support slices: ...
    (comp.lang.python)
  • Re: first-class types
    ... Are there languages that pass whole arrays ... Algol 60 is particularly weird, ... In call-by-name evaluation, the arguments to functions are not ... int sum{ ...
    (comp.arch)
  • Re: 32 or 64 bit processor info in C
    ... For a brief momenet we have the situation where int ... You could argue that all that memory won't be used for arrays. ... merely that the language isn't going to ...
    (comp.lang.c)
  • Re: <Help> Simple Pause Needed.
    ... before arrays, since arrays are error-prone, but I suppose your ... void f(int a, int b); ... It does not matter whether you pass by reference or by value. ... cin>> continue; ...
    (comp.lang.cpp)