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

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

Quiksort — метод быстрой сортировки
Идея : В основе данного метода положен метод разделение ключей по отношению к выбранному.
Пример :

После первого прохода выбранный элемент становится на свое место.

Улучшение «пузырькового» метода.
1) Если проходить массив не только сверху вниз, но и снизу вверх одновременно, то не только «легкие» элементы  будут «всплывать», но и «тяжелые» «тонуть».
2)Для отмены прохода массива «впустую» нужно в во внешний цикл вставить проверку на отсортированность массива.

Алгоритм

Алгоритм пузырькового метода
(ПСЕВДОКОД)
for i=2 to n
for j=n to i step -1
if A( j-1 ) > A( j ) then
x=A( j-1 )
A( j-1 )=A( j )
A( j )=x
end if
next j
next i

Алгоритм метода Quiksort
(ПСЕВДОКОД)
Sub Sort(L,R)
i=l
j=r
x=A(( l+r ) div 2 )
while A( i ) < x do
i=i+1
end while
while A( j )>x do
j=j-1
end while
if i<=j then
Y=A( i )
A( i )=A( j )
A( j )=Y
while i>j do
if l<j then
sort( l,j )
end if
if i<r then
sort( i,r )
end if
return
sub Quiksort
sort ( 1, n )
return

Число перестановок и сравнений: (n* log( n )).

Задания
Варианты:
1. Составить программу вывода на экран самого большого  (самого малого) элемента массива А.
2. Составить программу сортировки массива А по убыванию величин его элементов.

3. В массиве А находятся элементы. Составить программу, которая сформирует массив В, в  котором расположить элементы масива В в порядке убывания.

4. Дан упорядоченный массив А — числа, расположенные в порядке возрастания, и число а, которое необходимо вставить в массив А, так,  чтобы упорядоченность массива сохранилась.

5. Составить программу для быстрой перестройки данного массива А, в котором элементы расположены в порядке возрастания, так, чтобы  после перестройки эти же элементы оказались расположенными в порядке убывания.

6. Дан массив А, содержащий как отрицательные, так и положительные числа. Составить программу исключения из него  всех отрицательных чисел, а оставшиеся положительные расположить в порядке их  возрастания.

7. Составить программу, которая будет из массива А брать одно число за другим и формировать  из  них массив В, располагая числа в порядке возрастания.

8. Дан список авторов в форме массива А. Составить программу формирования указателя авторов в алфавитном порядке и вывести его на экран.

9. Имеется n абонентов телефонной  станции. Составить программу, в которой формируется  список  по форме: номер телефона, фамилия (номера идут в порядке возрастания).

10. Имеется n слов  различной  длины, все  они занесены в массив А. Составить программу упорядочения слов по возрастанию их длин.

11. Составить программу для сортировки массива А по возрастанию и убыванию модулей его  элементов.

12. В  отсортированный  массив А между  каждой соседней парой элементов вставить число больше левого и меньше правого элемента в массиве и вывести полученный массив на экран.

Лабораторная работа № 9. «СОРТИРОВКА С ПОМОЩЬЮ ДЕРЕВА»

Страницы: 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

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