ВУЗ:
Составители:
Рубрика:
25
♣ Метод быстрой сортировки заключается в следующем :
I этап . Обозначим через а и b границы сортируемой части массива Х (n).
Вначале a=1, b=n. В массиве Х ищется элемент S , стоящий около середины .
Элементы массива просматриваются поочередно слева направо и справа нале -
во. При переборе элементов слева направо определяется позиция i элемента Х [i]
=> S. При переборе элементов справа налево определяется позиция j элемента
Х [j] <= S. Если элемент Х [i] находится слева от S , а элемент Х [j] – справа, то най -
денные элементы Х [i] и Х [j] меняются местами. Встречный поиск продолжается
до тех пор , пока индексы i и j не пересекутся , т.е. i>j. Например , пусть массив X
состоит из 5 элементов :
5 1 4 2 3.
S=4. При i=1, j=5 переставляются крайние элементы : 3 1 4 2 5.
Встречный поиск будет продолжен при i=2, j=4.
При i=3, j=4 переставляются 3 - й и 4 - й элементы : 3 1 2 4 5.
Текущие значения i и j изменяются на единицу. i=4, j=3.
I этап закончен, так как i>j.
После завершения I этапа все элементы , меньшие или равные среднему,
окажутся слева от границы пересечения индексов i и j , а все элементы , которые
больше или равны среднему, окажутся справа. Однако левая и правая части
массива еще могут быть неотсортированными.
II этап . На втором этапе повторяются действия первого этапа для левой и
правой частей массива. Если j оказывается больше a, то действия первого этапа
реализуются для элементов массива с номерами от a до j . Если i оказывается
меньше b, то действия первого этапа реализуются для элементов массива с но-
мерами от i до b .
В нашем примере после первого этапа i=4, j=3. Значит, на втором уровне
рекурсии сортировке будут подвержены элементы левой части массива с номе-
рами от 1 до 3 : 3 1 2│4 5 и правой части с номерами от 4 до 5 .
На втором уровне рекурсии для левой части массива: 3 1 2 4│5: S=1.
При i=1, j=2 переставляются 1 - й и 2 - й элементы : 1 3 2 4│5.
Текущие значения i и j изменяются на единицу. i=2, j=1.
Второй уровень рекурсии закончен, так как i>j.
После второго уровня рекурсии для левой части массива i =2, j=1. Зна-
чит, на третьем уровне рекурсии сортировке будут подвержены элементы с но-
мерами от 2 до 3 : правой части рассматриваемого участка:1│3 2│4 5.
На третьем уровне рекурсии для левой части массива: 1│3 2│4 5:
S=3. При i=2, j=3 переставляются 2 - й и 3 - й элементы : 1│2 3│4 5.
Текущие значения i и j изменяются на единицу. i=3, j=2.
Третий уровень рекурсии закончен, так как i>j. Дальнейший рекурсивный
вызов не выполняется , так как после данного шага i =3, j=2, т.е. j=a, а i=b.
На втором уровне рекурсии для правой части массива: 1 2 3│4 5:
S=4. При i=4, j=4 переставляются 4 - й и 4 - й элементы : 1 2 3│4 5.
Страницы
- « первая
- ‹ предыдущая
- …
- 23
- 24
- 25
- 26
- 27
- …
- следующая ›
- последняя »
