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

UptoLike

ВУЗ: 

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

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

Рубрика: 

ня относят Algol – 68 и APL; они обладают дополнительными средствами опи-
сания обработки данных. По другой классификации языки программирования
делятся на вычислительные и языки символьной обработки. К последним отно-
сятся ЛИСП, ПРОЛОГ, РЕФАЛ. С прикладной точки зрения ФОРТРАН, АЛ-
ГОЛ- 60, ПАСКАЛЬ ориентированы на научные и инженерные расчеты, КО-
БОЛ – типичный язык обработки экономической информации, СИМУЛА – 67 –
язык имитационного моделирования.
4.2 Сортировка
Пусть задан файл φ, состоящий из записей: φ (1),…,φ(n). Каждой записи
поставим в соответствии ключ k
i
, i=1…n.Обычно ключ – это какое-либо отде-
льное поле или комбинация полей записи (некоторый признак записи). Будем
предполагать, что на множестве ключей задано отношение линейного порядка
(следования) с обычными свойствами. Задача сортировки файла ставится так:
найти перестановку записей µ (1),…,µ (n) такую, чтобы их ключи располага-
лись в неубывающем порядке: k
µ(1)
≤ …≤ k
µ(n)
. Во многих случаях не требуется
реально иметь перестановку, а достаточно, например, составить список индек-
сов (адресов) элементов перестановки в исходном файле. Составление списка
индексного списка называют индексный сортировкой. Впрочем, имея индекс-
ный список. Нетрудно произвести собственно сортировку.
Пример – Дан массив чисел (4, 5, 3, 8, 1, 9, 3, 2). Обычная сортировка: 1,
2, 3, 5, 4, 5, 8,9; индексная сортировка: 5, 8, 3, 7, 1, 2, 4, 6.
Имеется много алгоритмов сортировок /6/.
4.2.1 «Пузырьковая сортировка»
Название ассоциирует перемещение «малых» элементов со «всплытием».
Итак, пусть S – числовой массив а (1), …,а (n). Говорят, элементы а (i), а(j) об-
разуют инверсию, если i < j и а (i) > а(j). Тогда алгоритм «пузырьковой сорти-
ровки» состоит в последовательных просмотрах от конца к началу массива S и
обмена местами соседних элементов с инверсией.
Вход: массив S(1), …, S(n).
Вывод: массив S(1) ≤ S … < S(n).
Процедура Рus(S,n)
1 for i ←2, to n do
2 for j ← n to I do
3 if a(j – 1) > a(j) then swap(A(j-1),A(j))
End {Pus}
Трудоемкость этого алгоритма равна О(n
2
), то есть при любых S и n он
решает задачу за сn
2
операций сравнений и обменов, где с – константа, не зави-
сящая от n.
Пузырьковая сортировка не требует для реализации дополнительной па-
мяти, но временные характеристики – низкие. На практике используется редко. 
ня относят Algol – 68 и APL; они обладают дополнительными средствами опи-
сания обработки данных. По другой классификации языки программирования
делятся на вычислительные и языки символьной обработки. К последним отно-
сятся ЛИСП, ПРОЛОГ, РЕФАЛ. С прикладной точки зрения ФОРТРАН, АЛ-
ГОЛ- 60, ПАСКАЛЬ ориентированы на научные и инженерные расчеты, КО-
БОЛ – типичный язык обработки экономической информации, СИМУЛА – 67 –
язык имитационного моделирования.

       4.2 Сортировка

       Пусть задан файл φ, состоящий из записей: φ (1),…,φ(n). Каждой записи
поставим в соответствии ключ ki, i=1…n.Обычно ключ – это какое-либо отде-
льное поле или комбинация полей записи (некоторый признак записи). Будем
предполагать, что на множестве ключей задано отношение линейного порядка
(следования) с обычными свойствами. Задача сортировки файла ставится так:
найти перестановку записей µ (1),…,µ (n) такую, чтобы их ключи располага-
лись в неубывающем порядке: k µ(1) ≤ …≤ k µ(n). Во многих случаях не требуется
реально иметь перестановку, а достаточно, например, составить список индек-
сов (адресов) элементов перестановки в исходном файле. Составление списка
индексного списка называют индексный сортировкой. Впрочем, имея индекс-
ный список. Нетрудно произвести собственно сортировку.
       Пример – Дан массив чисел (4, 5, 3, 8, 1, 9, 3, 2). Обычная сортировка: 1,
2, 3, 5, 4, 5, 8,9; индексная сортировка: 5, 8, 3, 7, 1, 2, 4, 6.
       Имеется много алгоритмов сортировок /6/.

                      4.2.1 «Пузырьковая сортировка»

      Название ассоциирует перемещение «малых» элементов со «всплытием».
Итак, пусть S – числовой массив а (1), …,а (n). Говорят, элементы а (i), а(j) об-
разуют инверсию, если i < j и а (i) > а(j). Тогда алгоритм «пузырьковой сорти-
ровки» состоит в последовательных просмотрах от конца к началу массива S и
обмена местами соседних элементов с инверсией.
      Вход: массив S(1), …, S(n).
      Вывод: массив S(1) ≤ S … < S(n).
      Процедура Рus(S,n)
      1 for i ←2, to n do
      2 for j ← n to I do
      3 if a(j – 1) > a(j) then swap(A(j-1),A(j))
      End {Pus}
      Трудоемкость этого алгоритма равна О(n2), то есть при любых S и n он
решает задачу за сn2 операций сравнений и обменов, где с – константа, не зави-
сящая от n.
      Пузырьковая сортировка не требует для реализации дополнительной па-
мяти, но временные характеристики – низкие. На практике используется редко.

Страницы