Математическая логика и теория алгоритмов. Стенюшкина В.А. - 78 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

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

Рубрика: 

Рисунок 4.2
4.2.3 Быстрая сортировка
Пусть S(k), k=1..n – одномерный массив и х
∈ S(k) Просматриваем S сле-
ва направо, пока не найдем а
> х, и просматриваем S справа налево, пока не
найдем b
< х. Меняем местами а и b Продолжая этот процесс, придем к после-
довательности, разделенной на две части S1 и S2 такой, что элементы из S1 не
превосходят х, а элементы из S2 не меньше х.
Пример – Массив – 6; 23, 17, 8, , 25, 6, 3, 30, 7
Последовательность: 6, 7, 3, 8, 6
25, 14, 17, 30, 23.
Значение х для массива будем выбирать так: если количество элементов в
S нечетно, то это будет средний элемент, если четно, то из двух средних выби-
рать элемент с меньшим индексом. Итак, мы рассмотрим процедуру разделе-
ния. Теперь опишем процедуру быстрой сортировки. Разобьем S на две части
S1 и S2 как только что было описано. Теперь поступим также с каждой из час-
тей S1 и S2 и так далее, пока каждая из частей не будет содержать ровно 1 эле-
мент. В результате получится отсортированный массив. При реализации этой
процедуры на ЭВМ надо предусмотреть хранение адресов раздваиваемых по-
дмассивов. Если каждый раз продолжать работу с меньшей из полученных час-
тей, отправляя адреса начала и конца второй части на хранение, то потребуется
запоминание не более 2 log(n) адресов (чисел). Можно хранить эти адреса в ви-
де наращиваемого стека, обрабатывается первым. С другой стороны. Следует
иметь в виду, что для «быстрой сортировки» нет гарантированной трудоемкос-
ти типа 0 (n log n), где n – число элементов массива. В иных ситуациях трудое-
1
1
1
1
4
1
1
1
3
17
3
12
9
5
1
8
14
9
4
9
1
4
9
3
14
                                                          1
                             1                                                     1

             1                                4                            1


    9                1               4                9           3                1


9       14       8       1       5        4       9        12 3       17       1       3


                                                          Рисунок 4.2

                                         4.2.3 Быстрая сортировка

     Пусть S(k), k=1..n – одномерный массив и х ∈ S(k) Просматриваем S сле-
ва направо, пока не найдем а > х, и просматриваем S справа налево, пока не
найдем b< х. Меняем местами а и b Продолжая этот процесс, придем к после-
довательности, разделенной на две части S1 и S2 такой, что элементы из S1 не
превосходят х, а элементы из S2 не меньше х.
     Пример – Массив – 6; 23, 17, 8, 14 , 25, 6, 3, 30, 7




       Последовательность: 6, 7, 3, 8, 6 25, 14, 17, 30, 23.
      Значение х для массива будем выбирать так: если количество элементов в
S нечетно, то это будет средний элемент, если четно, то из двух средних выби-
рать элемент с меньшим индексом. Итак, мы рассмотрим процедуру разделе-
ния. Теперь опишем процедуру быстрой сортировки. Разобьем S на две части
S1 и S2 как только что было описано. Теперь поступим также с каждой из час-
тей S1 и S2 и так далее, пока каждая из частей не будет содержать ровно 1 эле-
мент. В результате получится отсортированный массив. При реализации этой
процедуры на ЭВМ надо предусмотреть хранение адресов раздваиваемых по-
дмассивов. Если каждый раз продолжать работу с меньшей из полученных час-
тей, отправляя адреса начала и конца второй части на хранение, то потребуется
запоминание не более 2 log(n) адресов (чисел). Можно хранить эти адреса в ви-
де наращиваемого стека, обрабатывается первым. С другой стороны. Следует
иметь в виду, что для «быстрой сортировки» нет гарантированной трудоемкос-
ти типа 0 (n log n), где n – число элементов массива. В иных ситуациях трудое-

Страницы