inververs
AutoIT Гуру
- Сообщения
- 2,135
- Репутация
- 465
Как утверждает автор, Аллен Бичик, его сортировка в 2 -3 раза быстрее чем быстрая сортировка, в зависимости от списка. Интересно! Написать функцию которая бы сортировала массивы быстрее чем _ArraySort()! :stars:
Попробуем:
Читаем описание алгоритма, или статью здесь и сделаем тоже самое на AutoIT.
Но поскольку код написан на С, которого я совершенно не знаю, есть одно место которое трудно повторить, а именно: if (nodup) recno = 0;
Если кто разбирается в C просьба помоч.
Вот сам код на C
А вот что получилось на AutoIT:
Но из за того что я не понимаю как сделать if (nodup) recno = 0 алгоритм не до конца рабочий. Он отбрасывает все повторяющиеся элементы.
Тестирование:
в сравнении с _arraysort проигрывает на мелких массивов, но начинает лидировать при большом количестве записей, от 100 000.
Вот в картинках принцип работы:
Просьба кому не лень помочь доработать :beer:
Добавлено:
Гифку на кадры можно разложить здесь а то очень быстро рисуется.
Попробуем:
Читаем описание алгоритма, или статью здесь и сделаем тоже самое на AutoIT.
Но поскольку код написан на С, которого я совершенно не знаю, есть одно место которое трудно повторить, а именно: if (nodup) recno = 0;
Если кто разбирается в C просьба помоч.
Вот сам код на C
Код:
/*
** ABCsort на C
** Представленный в данной программе алгоритм сортировки является собственностью
** Аллена Бичика (Allen Beechick) и находится под защитой законодательства США,
** Патент №5218700.
** Использование данного алгоритма без разрешения владельца запрещено законом.
** Автором этой программы является:
** Линн Д. Ярбро (Lynn D. Yarbrough)
** Палм Десерт (Palm Desert), Калифорния
**======================================================================
*/
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
long *RT; /* Таблица записей */
long **LT; /* Таблица символов */
void ABCsort (int keys) { /* Количество используемых ключевых полей */
void process (int, int);
long register i, j, recno;
int register c;
int nodup = noduplicates;
long start, step, stop;
/* Выделяем хранилища под внутренние таблицы */
LT = lmatrix(1, keys, alphamin, alphamax);
RT = lvector(1, N);
/* Инициализация таблицы символов: */
for (j = alphamin; j <= alphamax; j++) {
for (i = 1; i <= keys; i++)
LT[i][j] = 0;
}
/* Обеспечиваем стабильность сортировки */
if ((keys & 1) ^ nodup) {
start = N; stop = 0; step = -1;
} else {
start = 1;
stop = N + 1;
step = 1;
}
/* Этап 1 */
/* Группируем слова по первой букве */
for (recno = start; recno != stop; recno += step) {
c = GetNextField(recno, 1);
RT[recno] = LT[1][c];
LT[1][c] = recno;
}
/* Запускаем процесс уточнения положения записей в списке. */
process(1, keys);
free_lmatrix(LT, 1, keys, alphamin, alphamax);
free_lvector(RT, 1, N);
}
/* ======================================================== */
/* Функция обработки данных после 1-го этапа: */
/* Перегруппировываем слова, переходя от одной буквы к следующей */
void process (int level, int keys) {
long i, newlevel, nextrec, recno;
int nodup = noduplicates;
unsigned char c;
/* Цикл по алфавиту */
for (i = alphamin; i <= alphamax; i++) {
/* Ищем использование i-й буквы */
recno = LT[level][i];
LT[level][i] = 0;
/* Сканируем ветвь для этой буквы */
while (recno != 0) {
/* i-й символ используется только однажды, значит
отсортированная часть массива пополнилась новым элементом */
if (RT[recno] == 0) {
PutCurrRecord(recno);
recno = 0;
continue;
} else {
/* В случае многократного использования i-го символа: */
if (level == keys) {
/* Вывод всех данных на этом уровне: */
while (recno != 0) {
/* Добавляем текущую запись в таблицу индексов */
PutCurrRecord(recno);
recno = RT[recno];
if (nodup) recno = 0;
}
} else {
/* Продолжать уточнять порядок слов:*/
/* опускаемся на уровень вниз */
newlevel = level + 1;
while (recno != 0) {
nextrec = RT[recno];
c = GetNextField(recno, newlevel);
RT[recno] = LT[newlevel][c];
LT[newlevel][c] = recno;
recno = nextrec;
}
/* Продолжаем процесс уточнения */
process(newlevel, keys);
}
}
}
}
}А вот что получилось на AutoIT:
Код:
Global $aWords[] = ['carmen', 'adela', 'beatrix', 'abbey', 'abigale', 'barbara', 'camalia', 'belinda', 'beckie']
Global $alphamin = 97
Global $alphamax = 122
Global $MaxKey = 10 ;Временно
Global $keys_ = UBound($aWords) + 1 ;Если используется нулевой индекс массива, то UBound($aWords) + 1
Global $LT[$MaxKey][$alphamax + 1]
Global $RT[$keys_]
$RT[0] = 'RT'
ABCsort($keys_)
Func ABCsort($keys)
;/* Инициализация таблицы символов: */
For $j = $alphamin To $alphamax
$LT[0][$j] = Chr($j)
For $i = 1 To $MaxKey - 1
$LT[$i][$j] = 0
Next
Next
; /* Обеспечиваем стабильность сортировки */
Local $start = 1
Local $end = $keys - 1
Local $step = 1
;/* Этап 1 */
;/* Группируем слова по первой букве */
For $recno = $start To $end Step $step
$c = GetNextField($recno, 1)
$RT[$recno] = $LT[1][$c]
$LT[1][$c] = $recno
Next
;/* Запускаем процесс уточнения положения записей в списке. */
process(1, $keys);
EndFunc
Func process($level,$keys)
For $i = $alphamin To $alphamax
;/* Ищем использование i-й буквы */
$recno = $LT[$level][$i]
$LT[$level][$i] = 0
;/* Сканируем ветвь для этой буквы */
While $recno
If $RT[$recno] = 0 Then
PutCurrRecord($recno)
$recno = 0
ContinueLoop
Else
If $level = $keys Then
;/* Вывод всех данных на этом уровне: */
While $recno
PutCurrRecord($recno)
$recno = $RT[$recno]
;~ $recno = 0 ;??? if (nodup) recno = 0;
WEnd
Else
;/* Продолжать уточнять порядок слов:*/
$newlevel = $level + 1
While $recno
$nextrec = $RT[$recno]
$c = GetNextField($recno, $newlevel)
$RT[$recno] = $LT[$newlevel][$c]
$LT[$newlevel][$c] = $recno
$recno = $nextrec
WEnd
;/* Продолжаем процесс уточнения */
process($newlevel, $keys)
EndIf
EndIf
WEnd
Next
EndFunc
Func GetNextField($recno,$level)
;Вернем ASCII код номер записи $recno номер буквы $level
$word = $aWords[$recno - 1] ;Если использвуется нулевой индекс массива, то $word = $aWords[$recno - 1]
$char = StringMid($word,$level,1)
$ASCII = Asc($char)
Return $ASCII
EndFunc
Func PutCurrRecord($recno)
$word = $aWords[$recno - 1]
ConsoleWrite($word & @LF)
EndFuncНо из за того что я не понимаю как сделать if (nodup) recno = 0 алгоритм не до конца рабочий. Он отбрасывает все повторяющиеся элементы.
Тестирование:
в сравнении с _arraysort проигрывает на мелких массивов, но начинает лидировать при большом количестве записей, от 100 000.
Вот в картинках принцип работы:
Просьба кому не лень помочь доработать :beer:
Добавлено:
Сообщение автоматически объединено:
Гифку на кадры можно разложить здесь а то очень быстро рисуется.
