Из AVR220:
Note: 1. SIZE = Number of bytes to sort
Table 2. “bubble” Performance Figures (1)
Code Size (Words): 12 + return
Average Execution Time (Cycles): 5 x (SIZE-1) +11.5 x (SIZE(SIZE-1)) + return
Коэффициент 11.5 в выражении выше - это среднее число итераций (24-1)/2, когда попарной перестановке подвергается половина массива. При наихудших условиях (переставляются все элементы - например, когда входной массив отсортирован в обратном порядке) этот коэффициент станет равным (24-1)=23, что потребует 23^3 такта на основной цикл.
Вот код из AVR220:
bubble:
mov ZL,endL
mov ZH,endH ;init Z pointer
mov cnt2,cnt1 ;counter2 <- counter1
i_loop: ld A,Z ;get first byte, A (n)
ld B,-Z ;decrement Z and get second byte, B (n-1)
cp A,B ;compare A with B
brlo L1 ;if A not lower
st Z,A ; store swapped
std Z+1,B
L1: dec cnt2
brne i_loop ;end inner loop
dec cnt1
brne bubble ;end outer loop
ret
AVR (13.09.2006 22:20, просмотров: 1) ответил jaga-jaga на скорость сортировки пузырьком не пропорциональна ли квадрату числа элементов массива?
, ссылка)