Быстрый алгоритм сжатия упаковки(не архивация) массива

← →
@!!ex © (2007-12-07 20:29) [0]

Есть массив записей.
Нужно упаковать массив.
В записи есть поле Handle.
Это значит упорядочить его так, чтобы все элементы с Handle=0 лежали в конце массива.
НИчего умнее сортировки придумать не могу...

← →
Efir (2007-12-07 20:31) [1]

Т. е. нужно отсортировать?

← →
@!!ex © (2007-12-07 20:40) [2]

> [1] Efir (07.12.07 20:31)

хм. в принципе да.
Но полюбому это можно реализовать как то быстрее чем обычная сортировка. Ведь элементы делятся только на два типа 0 и не 0.

← →
Efir (2007-12-07 20:52) [3]

Ну тогда наверно можно одним проходом отсортировать.

Это не совсем сортировка в привычном смысле этого слова.
Решается за один проход, путем перемещения в конец, только не циклом for, а while.

← →
Efir (2007-12-07 21:06) [5]

Чё нить типа:
xo - указатель на начало
хк - указатель на конец массива
1) если справа 0, то dec(xk) иначе смотрим слева
2) если слева 0 - меняем местами и inc(xo), dec(xk)
3) если слева не 0 то inc(xo), пока слева не будет 0.

Быстрый алгоритм сжатия упаковки(не архивация) массива Найти похожие ветки