Q: how to do stable sort in ArrayList?

  • Thread starter Thread starter Guest
  • Start date Start date
G

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
 
wdli said:
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.
Click to expand...

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?
Click to expand...

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
 
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
 
wdli said:
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?
Click to expand...

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
 
Hi Max,

Good idea and it worked ! Thanks.

David

Markus Stoeger said:
wdli said:
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?
Click to expand...

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
Click to expand...
 
Back
Top