Сортировка массива

[Demonx]

Есть динмаический массив Arr() as integer
....
redim preserve Arr(0 to 999) as integer.....
...
...
Так вот в элементах массива - цифры. Как отсортировать массив по возрастанию?

[Хакер]

Сделать ещё один массив.
И заполнить его сначала единицами потом двойками, потом тройками:

Код: Выделить всё


Dim NmCounter(1 to MAX_NUM) as integer
Dim n as integer
For i = 1 To MAX_NUM
   For j = 1 to 999
     If Arr(j)=i then NmCounter(i)=NmCounter(i)+1
   next j
Next i
For i = 1 to MAX_NUM
   If NmCounter(i)>0 then
       For J = 1 To NmCounter(i)
           Array2(n) = i
            n=n+1       
       NextJ
   End If
next i


1) Код можно заметно сократить если использовать один цикл I

2) Код на работоспобность не проверялся, времени нет, но вроде бы должно работать.

[Sasha_karasov]

На algolist глянь, там очень много есть про сортировку

[Sasha_karasov]

http://algolist.manual.ru вот вспомнил!

[GAGArin]

Хакер
Код конечно прост в реализации, и линено возрастает, но нужен весьма и весьма длинный массив чтобы это окупилось. Для массива 999 элементов банальнейший пузырек и то будет ффективнее (в 32 с лишним раза) не говоря уже о квиксорте например.


Можно его чуток переделать, сохранив простоту, но добавив скорости.

Код: Выделить всё

For i = 1 To MAX_NUM
   For j = 1 to 999
     If Arr(j)=i then NmCounter(i)=NmCounter(i)+1
   next j
Next i

Заменим на:

Код: Выделить всё

For j = 1 to 999
  NmCounter(Arr(j))=NmCounter(Arr(j))+1
next j


Не изменяя вторую часть кода уже повышаем эффективность первой в 32 тысячи раз Причем для Integer'ов вроде должно работать.
Ну один завершающий проход по всему интеджеру придеться оставить. Но это уже судьба Кстати коды (и хакера и переделаный мной) стоит чуток поправить на предмет существования отрицательных чисел, но тут уж просто добавить/вычесть 32768

Вобщем код хороший, для данного конкретного примера, но реализация шокирует. Эффективность снижена почти в Тысячу раз. (считал для 65536 проходов, а не 32768)

65536*1000/(65536+999)=985 Ну еще немножко с этой цифры скосит наличее второго цикла в финальном проходе, но все равно эффективность не в лучшей форме.

Ну и есть еще одна проблемка, памяти код жрет тоже в 50 с лишним раз больше чем мог бы это сделать алгоритм работающий с одним массивом (но тут реализовать подобный код не удасться, а он все же в переделаном варианте весьма быстр) Вобщем на усмотрение автора топика. Чем длиннее сортируемый массив, тем лучше код предложеный Хакером. Для коротких массивов он жрет непозволительно много памяти.

PS Все писал тоже без VB не проверял.