[sort] Проблема с сортировкой массива объектов

[CyberDude]

Условие
Есть определённый массив игроков - гонщиков, у каждого элемента массива есть свойство point и player, где:

• point - количество пройденных поинтов;

• player - порядковый номер игрока.

Со временем массив изменяется и количество поинтов у игроков увеличивается.

Задача
Нужно сортировать массив так, чтобы каждый игрок имел такой идентификатор в массиве, который соответствовал бы его положению в гонке.


Решение
Я использовал для решения задачи метод "sort()" для этого, но результат работы меня весьма удивил.

Привожу код:

array.sort(sorting);
 
function sorting (a:Object, b:Object):int
{
	var response:int = a.point-b.point;
	if (response < 0) response = -1;
	else if (response > 0) response = 1;
	return response;
}

Привожу trace вывод изменений массива (сортировка в данном случае по убыванию, но это не суть):
1. [{"point":0,"player":3},{"point":0,"player":4},{"point":0,"player":2},{"point":0,"player":0},{"point":0,"player":5},{"point":0,"player":6},{"point":1,"player":1}]
2. [{"point":0,"player":2},{"point":0,"player":4},{"point":0,"player":6},{"point":0,"player":3},{"point":0,"player":5},{"point":1,"player":0},{"point":1,"player":1}]
3. [{"point":0,"player":6},{"point":0,"player":4},{"point":0,"player":5},{"point":0,"player":2},{"point":1,"player":3},{"point":1,"player":0},{"point":1," player":1}]
4. [{"point":0,"player":6},{"point":0,"player":4},{"point":0,"player":5},{"point":1,"player":2},{"point":1,"player":3},{"point":1,"player":0},{"point":1," player":1}]
5. [{"point":0,"player":6},{"point":0,"player":4},{"point":1,"player":5},{"point":1,"player":2},{"point":1,"player":3},{"point":1,"player":0},{"point":1," player":1}]
6. [{"point":0,"player":6},{"point":1,"player":4},{"point":1,"player":5},{"point":1,"player":2},{"point":1,"player":3},{"point":1,"player":0},{"point":1," player":1}]
7. [{"point":1,"player":2},{"point":1,"player":4},{"point":1,"player":5},{"point":1,"player":6},{"point":1,"player":3},{"point":1,"player":0},{"point":1," player":1}]
8. [{"point":1,"player":6},{"point":1,"player":4},{"point":1,"player":5},{"point":1,"player":2},{"point":1,"player":3},{"point":1,"player":0},{"point":2," player":1}]
9. [{"point":1,"player":2},{"point":1,"player":4},{"point":1,"player":5},{"point":1,"player":6},{"point":1,"player":0},{"point":2,"player":3},{"point":2," player":1}]
10. [{"point":1,"player":6},{"point":1,"player":4},{"point":1,"player":5},{"point":1,"player":2},{"point":2,"player":0},{"point":2,"player":3},{"point":2," player":1}]
11. [{"point":1,"player":2},{"point":1,"player":4},{"point":1,"player":6},{"point":2,"player":0},{"point":2,"player":5},{"point":2,"player":3},{"point":2," player":1}]
12. [{"point":1,"player":2},{"point":1,"player":6},{"point":2,"player":4},{"point":2,"player":0},{"point":2,"player":5},{"point":2,"player":3},{"point":2," player":1}]
13. [{"point":1,"player":6},{"point":2,"player":0},{"point":2,"player":4},{"point":2,"player":2},{"point":2,"player":5},{"point":2,"player":3},{"point":2," player":1}]

Суть проблемы

Справка Adobe
Возвращенное значение -1 означает, что первый параметр, a, стоит перед вторым, b.
Возвращенное значение 1 указывает, что второй параметр, b, стоит перед первым, a.
Возвращенное значение 0 говорит о том, что элементы равны в контексте сортировки.

Не понятно, почему элементы которые не меняли параметр point, поменяли своё положение в массиссиве. Я почему то думал что элемент массива с свойством player = 0, "передвинется" в начало массива, "подвинув назад" те элементы, у которых значение меньше. Красным выделил один из случаев.

Прошу помочь мне разобраться в чём тут дело и как разрешить данную проблему, мне нужно чтобы равные по параметрам элементы массива не менялись местами как показанно в trace выводе.

П.С.
Возможно методом sort() воспользоватся не получится (как и sortOn() скорее всего), тогда как быть? Писать сортировку вручную?

[expl]

Если что, стабильная сортировка (элементы с одинаковыми значениями не меняют своего положения), портируется с Java впринципе, нормально:
http://www.vogella.de/articles/JavaA...t/article.html
По поводу функции sorting - есть некоторые сомнения в правильности, но мало времени разбираться

Еще стабильности можно достичь, добавив к объекту какое-нибудь фиктивное поле с фиктивным, не меняющимся значением и учитывать его в сортировке.

[Krusty]

Потому что 0-это значит, что два элемента равны в контексте сортировки, и поэтому их можно расположить в любом порядке, что логично.
Что sort и делает.
если хотите сохранения позиции, просто в случае
a.point==b.point проверяйте старую позицию в функции sorting

[CyberDude]

Сообщение от Krusty

Потому что 0-это значит, что два элемента равны в контексте сортировки, и поэтому их можно расположить в любом порядке, что логично.
Что sort и делает.
если хотите сохранения позиции, просто в случае
a.point==b.point проверяйте старую позицию в функции sorting

Если честно, не понял, как это всё сделать. Если не сложно, не могли бы вы показать реально работающий пример?

[expl]

Сортировка сначала по точке, потом по индексу игрока (по идее, этого достаточно, даже без стабильной сортировки)

function sorting (a:Object, b:Object):int
{
	if (a.point == b.point)
        {
              return a.player - b.player
         }
	return a.point - b.point;
}

Альтернативное решение:

function sorting (a:Object, b:Object):int
{
	return (a.point * 100500 + a.player) - (b.point * 100500 + b.player);
}

Но последнее будет работать неправильно при отрицательных значениях и при a.player >= 100500.

[CyberDude]

Сообщение от expl

function sorting (a:Object, b:Object):int
{
	if (a.point == b.point)
        {
              return a.player - b.player
         }
	return a.point - b.point;
}

Мне больше нравится. Очень не плохой выход, и именно к месту! Спасибо за то что вникли в задачу.

Завтра на работе попробую

[Krusty]

ЗЫ. Ваши соображения, что элемент должен оставаться на месте, работали бы в случае сортировки "пузырьком" итп, а ее уже давным-давно никто не использует.

[CyberDude]

Сообщение от Krusty

ЗЫ. Ваши соображения, что элемент должен оставаться на месте, работали бы в случае сортировки "пузырьком" итп, а ее уже давным-давно никто не использует.

Да, я понимаю что в пузырьковом это работает. Но я не знаю к сожалению алгоритма работы метода sort

[expl]

ЗЫ. Ваши соображения, что элемент должен оставаться на месте, работали бы в случае сортировки "пузырьком" итп, а ее уже давным-давно никто не использует.

Не только пузырёк стабилен.
Сортировка слиянием - одна из простых и эффективных стабильных сортировок (вверху ссылку давал)
И сложность у неё как у быстрой сортировки - n log n, хотя сама по себе в пару раз медленнее работает.

[Krusty]

в sort, скорее всего, сидит не один вариант алгоритма, так как любой из алгоритмов сортировки порядка N * logN есть баланс между скоростью(а различия могут быть существенны) и расходом памяти.
Так что на ее поведение, не описанное в документации, точно полагаться не стоит.