Q: how to do stable sort in ArrayList?

[Guest]

Hello,

Here is my problem:

I have an ArrayList with duplicate keys. I 'd like to preserve the original
order when sorting the list by using ArrayList.sort(comparer* c). However
when the comparer returns 0 (meaning the two objects are equal), the order of
the two objects are random or not preserved. I understand it's not a stable
sort. I also tried to return just -1 in my compare class when they are equal.
But this created a deadloop inside ArrayList.sort() for unknown reasons.
Does anyone know to how get around this?

Thanks.

David

 

[Markus Stoeger]

I have an ArrayList with duplicate keys. I 'd like to preserve the original
order when sorting the list by using ArrayList.sort(comparer* c). However
when the comparer returns 0 (meaning the two objects are equal), the order of
the two objects are random or not preserved. I understand it's not a stable
sort.

As far as I know there is no class for a stable sorting algorithm in the
framework.

I also tried to return just -1 in my compare class when they are equal.
But this created a deadloop inside ArrayList.sort() for unknown reasons.
Does anyone know to how get around this?

Try to return -1 when they are equal (by value), but return 0 when they
are really equal (by reference). I believe that should work.

Max

 

[Guest]

Hi,

Thanks for quick response.
I am not sure I followed your idea here. In my case, the comparison key is a
floating number. Right now, I am returning -1 when two keys are equal or one
is less than the other.

When should I return 0 in this case?

David

 

[Markus Stoeger]

Hi,

Thanks for quick response.
I am not sure I followed your idea here. In my case, the comparison key is a
floating number. Right now, I am returning -1 when two keys are equal or one
is less than the other.

When should I return 0 in this case?

I tried that out, it didn't work anyway.

Would the following work for you? It sorts the array but remembers the
index of each item. At the end it simply sorts each group of equal
values a second time with the indices as keys.. resulting in a stable sort.

private void stableSort(IComparable[] array) {
int[] indices = new int[array.Length];

for (int i = 0; i < array.Length; i++) {
indices = i;
}

Array.Sort(array, indices);

int a = 0;

while (a < array.Length) {
int b = a+1;

while (b < array.Length && array[a].CompareTo(array) == 0) {
b++;
}

// a is beginning of equal group, b is end of group
if (a+1 != b) {
// sort that again with indices as keys
Array.Sort(indices, array, a, b-a);
}

a = b;
}
}

hth,
Max

 

[Guest]

Hi Max,

Good idea and it worked ! Thanks.

David

Hi,

Thanks for quick response.
I am not sure I followed your idea here. In my case, the comparison key is a
floating number. Right now, I am returning -1 when two keys are equal or one
is less than the other.

When should I return 0 in this case?

I tried that out, it didn't work anyway.

Would the following work for you? It sorts the array but remembers the
index of each item. At the end it simply sorts each group of equal
values a second time with the indices as keys.. resulting in a stable sort.

private void stableSort(IComparable[] array) {
int[] indices = new int[array.Length];

for (int i = 0; i < array.Length; i++) {
indices = i;
}

Array.Sort(array, indices);

int a = 0;

while (a < array.Length) {
int b = a+1;

while (b < array.Length && array[a].CompareTo(array) == 0) {
b++;
}

// a is beginning of equal group, b is end of group
if (a+1 != b) {
// sort that again with indices as keys
Array.Sort(indices, array, a, b-a);
}

a = b;
}
}

hth,
Max