Итеративный алгоритм поразрядной lsd-сортировки

LSD_Sort (A, n, C)

1. А – массив

2. С – вспомогательный массив для карманов

3. R – основание системы счисления для поразрядной сортировки

4. k – максимальное количество цифр в значениях

5. d – номер текущей цифры

6. k bitsword / bitsdigit bitsword – число битов в ячейке массива А

7. bitsdigit – число битов в цифре

8. for d k down 0

9. do

10. вычисление размеров карманов

11. for j 1 to R+1

12. do count[j] 0

13. for i 1 to n

14. do j digit(A[i], d, R) digit(…) – извлечение d – й цифры

15. count[j+1] count[j+1] + 1

16. for j 2 to R

17. do count[j] count[j] + count[j-1]

18. распределение значений по карманам

19. for j 1 to n

20. do j digit(A[i], d, R)

21. C[count[j]] A[i]

22. count[j] count[j] + 1

23. перенос значений из карманов в массив A

24. for i 1 to n

25. do A[i] C[i]

Приложение В

Алгоритмы операций для BST – дерева

Алгоритм обхода BST – дерева по схеме t→L_t→R_t

t_Lt_ Rt (t)

1t-корень дерева

2S-вспомогательный стек

3 Push(S, t)

4 while Empty(S) = FALSE

5 do t ← Pop(S)

6 доступ к узлу t

7 if right[t] ≠ nil

8 then Push(S, right[t])

9 if left[t] ≠ nil

10 then Push(S, left[t])

Алгоритм обхода BST – дерева по схеме L_t→R_t→t

Lt_ Rt _t(t)

1t-корень дерева/поддерева

2 if t = nil then return

3 Lt_ Rt _t (left[t])

4 Lt_ Rt _t (right[t])

5 доступ к узлу t

Алгоритм обхода BST – дерева по схеме L_t→t→R_t

Lt_t_ Rt (t)

1t-корень дерева/поддерева

2 if t = nil then return

3 Lt_t_ Rt (left[t])

4 доступ к узлу t

5 Lt_t_ Rt (right[t])

Алгоритм обхода BST – дерева по схеме по уровням

Traverse (t)

1t-корень дерева

2Q-вспомогательная очередь

3 Enqueue(Q, t)

4 while Empty(Q) = FALSE

5 do t ← Dequeue(Q)

6 доступ к узлу t

7 if left[t] ≠ nil

8 then Enqueue (Q, left[t])

9 if right[t] ≠ nil

10 then Enqueue (Q, right[t])

Рекурсивный алгоритм поиска элемента в BST – дереве

BST_Search(t, k)

1 t – корень дерева или поддерева

2 k – значение искомого ключа

3 if t = nil

4 then сообщение об ошибке

5 if k = key[t]

6 then return data[t]

7 if k < key[t]

8 then return BST_Search(left[t], k)

9 else return BST_Search(right[t], k)

Итеративный алгоритм поиска элемента в BST – дереве

BST_Iterative_Search(t, k)

1 t – корень дерева

2 k – значение искомого ключа

3 while t ≠ nil and k ≠ key[t]

4 do if k < key[t]

5 then t ← left[t]

6 else t ← right[t]

7 if t = nil

8 then сообщение об ошибке

9 return data[t]

Рекурсивный алгоритм вставки элемента в BST – дерево

BST_Insert(t, k, data, inserted)

1 t – корень дерева или поддерева

2 k –ключ элемента

3 data – данные элемента

4 inserted – возвращаемый признак вставки

4 if k = key[t]

5 then inserted ← FALSE

6 return t

7 if t = nil

8 then inserted ← TRUE

9 return Create_Node(k, data)

10 if k < key[t]

11 then left[t] ← BST_Insert(left[t], k, data, ins)

12 else right[t] ← BST_Insert(right[t], k, data, ins)

13 inserted ← ins

14 return t