OberonCore
https://forum.oberoncore.ru/

код для сортировки массивов, который всегда с нами
https://forum.oberoncore.ru/viewtopic.php?f=23&t=6934
Страница 1 из 1

Автор:  arisu [ Пятница, 12 Май, 2023 08:09 ]
Заголовок сообщения:  код для сортировки массивов, который всегда с нами

если вдруг вам в BBCB понадобилось отсортировать массив, и вы сходу не можете/не хотите вспоминать какой-нибудь алгоритм, то вам помогут исходники модуля Kernel. в процедуре `CheckCandidates()` есть реализация Shell Sort, размером в девять строчек, готовая к копипасте. удобство в том, что эта реализация уж точно-точно работает, иначе вся среда бы глючила и рушилась. одна gotcha: может сортировать не более чем `MAX(INTEGER) DIV 3 - 2` элементов.

поскольку оно совсем маленькое, то я даже приведу здесь код:
Код:
VAR h, i, j: INTEGER; p: MY_TYPE_TO_SORT;

(* Shell sort; N is the number of entries to sort; ARR is the array to sort *)
h := 1; REPEAT h := h * 3 + 1 UNTIL h > N;
REPEAT h := h DIV 3; i := h;
   WHILE i < N DO p := ARR[i]; j := i;
      WHILE (j >= h) & (ARR[j - h] > p) DO
         ARR[j] := ARR[j - h]; j := j - h
      END;
      ARR[j] := p; INC(i)
   END
UNTIL h = 1;


но вам этот код не нужен: достаточно просто запомнить, что внутри Kernel есть вполне годный алгоритм сортировки, который можно при нужде скопипастить.


p.s.: если что, то в таком виде эта штука по скорости примерно как Heap Sort, и рвёт хипсорт в клочки на частично или полностью сортированых массивах (потому что шеллсорт адаптивный).

Страница 1 из 1 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/