Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Алгоритм пирамидальной сортировки

Задание к лабораторной работе | Методические указания к выполнению задания | Структуры BST - деревьев | Задание к лабораторной работе | Структуры сбалансированных деревьев | Задание к лабораторной работе | Методические указания к выполнению задания | Функции хеширования | Разрешение коллизий и структуры хеш-таблиц | Задание к лабораторной работе |


Читайте также:
  1. Алгоритм анализа иллюстрации
  2. Алгоритм вставки элемента в 2-3 - дерево
  3. Алгоритм вставки элемента в AVL-дерево
  4. Алгоритм захисту БД MS Access
  5. Алгоритм катетеризации мочевого пузыря.
  6. Алгоритм построения проекций отрезка прямой линии

Heap_Sort (A, n)

1. A – массив

2. n – размерность массива

3. l =

4. r n

5. Формирование пирамиды

6. while l >1

7. do l l -1

8. Shift (A, l, r)

9. Сортировка

10. while r >1

11. do x A[1]

12. A [1] A[ r ]

13. A [ r ] x

14. r r -1

15 Shift (A, 1, r)

 

Shift (A, l, r)

1. Просеивание в пирамиду

2. i l

3. j 2i

4. x A[i]

5. if j< r and A[j+1]<A[j]

6. then j j+1

7. while j r and A[j]<x

8. do A [i] A [j]

9. i j 

10.  j 2i

11. if j< r and A [j+1]< A [j]

12. then j j+1

13. A [i] x

 

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

QSort (A, l, r)

1. A – массив

2. l,r – левая и правая границы части

3. if l < r

4. then k Partition (A, l, r)

5. QSort (A, l, k)

6. QSort (A, k+1, r)

Partition (A, l, r)

1 x A (l + r)/2

2 i l- 1

3 j r+ 1

4 while TRUE

5 dorepeat j j-1

6 until A [j] x

7 repeat i i+1

8 until A [i] x

9 if i j

10 then t A [i]

11 A [i] A [j]

12 A [j] t

13 else return j

 

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

Itrative_QSort (A, n)

1 A – массив

2 n – размерность массива

3 stack[1..2 n ] – массив для стека

4 stack[1] 1

5 stack[2] n

6 top 1

Repeat

8 l stack[top]

9 r stack[top+1]

10 top top-2

11 if l < r

Then

Repeat

14 i l- 1

15 j r+ 1

16 x A (l + r)/2

Repeat

18 repeat i i+1

19 until A [i] x

20 repeat j j-1

21 until A [j] x

22 if i j

Then

24 t A [i]

25 A [i] A[j]

26 A [j] t

27 until i j

28 if i - l > r - i

29 then top top+2

30 stack[top] l

31 stack[top+1] i - 1

32 l i + 1

Else

34 top top+2

35 stack[top] i + 1

36 stack[top+1] r

37 r i - 1

38 until l r

39 until top = -1


Дата добавления: 2015-11-04; просмотров: 91 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Методические указания к выполнению задания| Итеративный алгоритм поразрядной LSD-сортировки

mybiblioteka.su - 2015-2024 год. (0.01 сек.)