Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

x = a(i)
k = i
for j = i + 1 to n
if x > a(j) then
k = j
x = a(k)
endif
next j
a(k) = a(i)
a(i) = x
next i
return
for i := 1 to n — 1 do
begin
x := a[i];
k := i;
for j := i + 1 to n do
if x > a[j] then
begin
k := j;
x := a[k];
end;
a[k] := a[i];
a[i] := x;
end;

Эффективность алгоритма:
Количество сравнений

Количество перемещений, когда массив упорядочен

Количество перемещений когда массив обратно отсортирован

В худшем случае сортировка прямым выбором дает порядок n2, как и для числа сравнений, так и для числа перемещений.
Задания

Создать  группу  из  N  студентов.  Ввести  их:  фамилия,  имя,  год рождения,  оценки  по  предметам: стр. и алг.данных, высш. математика, физика,   программирование,   общий  балл  сдачи  сессии;  Разработать программу   с  использованием  метода  «прямого  выбора»,  которая  бы осуществляла сортировку (согласно варианту) :
1. Фамилий студентов по алфавиту.
2. Фамилий студентов по алфавиту в обратном порядке.
3. Студентов по старшинству (начиная со старшего).
4. Студентов по старшинству (начиная с младшего).
5. Студентов по общему баллу (по возрастанию).
6. Студентов по общему баллу (по убыванию).
7. Студентов по результатам 1-го экзамена (по возрастанию).
8. Студентов по результатам 2-го экзамена (по убыванию).
9. Студентов по результатам 3-го экзамена (по возрастанию).
10. Студентов по результатам 4-го экзамена (по убыванию).
11. Имен в алфавитном порядке.
12. Имен в обратном алфавитном порядке.

Лабораторная работа № 8.»СОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ОБМЕНА»

Цель работы: исследовать и изучить методы сортировки с помощью прямого обмена.

Задача работы: овладеть навыками написания программ для сортировки с помощью прямого обмена на языке программирования ПАСКАЛЬ .

Порядок работы :
изучить описание лабораторной работы;
по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
написать программу на языке ПАСКАЛЬ;
отладить программу;
решить задачу;
оформить отчет.

Краткая теория

Пузырьковая сортировка
Идея : (N-1) раз массив проходится снизу вверх (сверху вниз), при этом элементы попарно сравниваются, если нижний элемент меньше верхнего, то элементы переставляются.
Пример : массив — 4, 3, 7, 2, 1, 6.

Можно улучшить «пузырьковый» метод, если проходить массив элементов и вверх и вниз одновременно.
Количество сравнений :

Количество перемещений :

Пример вычисления «пузырьковым» методом

На примере представлен массив из пяти элементов, это означает, что массив проходится снизу вверх (сверху вниз) 5-1=4 раза. Так же на примере видно, что алгоритм «в пустую» обрабатывает массив начиная уже с третьего шага внутреннего цикла, а 4-й шаг можно уже не выполнять.
Преимущества данного метода :
1) Самый простой алгоритм
2) Простой в реализации
3) Не нужно дополнительных переменных
Недостатки:
1) Долго обрабатывает большие массивы
2) В любом случае количество проходов не уменьшается

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники