Методы сортировок и их реализации. Беляева И.В - 38 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

Опорный
элемент
Исходный
массив
Опорный
элемент
Неопределеннаячасть
fiгstUnknown
=1
(указывает
на
38)
38
принадлежит
множеству
82
Множество
81
пусто;
12
принадлежит
множеству
81 J
поэтому
меняем
местами
38
и
12
39
принадлежит
множеству
82
Опорный
элемент
81
52
Неопределенная
часть
27
принадлежит
множеству
52
Неопределенная
часть
Неопределенная
часть
27
12
38.
Опорный
элемент
81
16
принадлежит
множеству
81,
27 12
поэтому
меняем
местами
38
и
16
Опорный
элемент
81
52
Множества
51
и
82
определены
27 12 16
39
)~
~
::I:
Ф
Q..:!
о ф
с:
r:::;
0(')
81
Помещаем
опорный
элемент
Полное
16 12 27 39
между
множествами
81
и
82
разбиение
РИСУНОК
18.
Первое
разбиение
массива,
когда
опорным
является
первый
элемент
Прежде
чем
приступить
к
реализации
алгоритма
быстрой
сортировки,
проверим
корректность
алгоритма
разбиения,
используя
его
инварианты.
Инвариант
цикла,
входящего
в
алгоритм,
имеет
следующий
вид.
Все
элементы
множества
S/.
(theArray[first+ 1..last
S/})
меньше
опорного,
а
все
элементы
множества
S2
(theArray [lastSI..
/irstUnknown-1J)
больше
или
равны
опорному
Напомним,
что
для
определения
правильности
алгоритма
с
помощью
его
инвариантов,
необходимо
выполнить
четыре
шага.
37

Страницы