Методы сортировки массивов

СОДЕРЖАНИЕ:

Введение. 2

1. Задачи сортировки.2

1.1.Общие положения.2

1.2. Постановка задачи сортировки массивов.4

2. Методы сортировки массивов.5

2.1. Простые методы сортировки массивов.5

2.1.1. Сортировка с помощью прямого включения.5

2.1.2.Сортирвка с помощью прямого выбора.8

2.1.3. Сортировка с помощью прямого обмена. 9

2.2. Улучшенные методы сортировки массивов.12

2.2.1.Метод Шелла.12

2.2.2.Сортировка с помощью дерева. 14

2.2.3. Сортировка с помощью разделения. 18

Тесты.. 21

Заключение. 31

Используемая литература. 33

Введение

Около трех с половиной десятилетий минуло с тех пор, как в педвузах введено в качестве учебной дисциплины программирование для ЭВМ. При колоссальной скорости изменений в самом предмете, всегда существенно превышавшей скорость центральных издательских механизмов, специально ориентированные на программы педвузов книги выходили не чаще, чем раз в десятилетие – едва ли не соразмерно скорости смены поколений ЭВМ. Сегодня полки книжных магазинов ломятся от изданий по информатике. Однако преподавателю (а более всего студенту) специальные учебные книги, содержание и направленность которых отвечают заданному учебному плану и программе все-таки очень нужны. Сейчас помимо программирования на некоторых специальностях в педвузах введены и другие более сложные спецкурсы, находящиеся на стыке прикладной (дискретной) математики и информатики.

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

4.1. N^2/2 перемещений.

4.2. N^2/4 перемещений.

4.3. N^2 перемещений.

4.4. N/4 перемещений.

5. Выберите правильный вариант для вставки вместо знака «вопрос» во фрагмент кода сортировки массива прямым включением:

For i:=2toСount doBegin Tmp:=Arr[i]; j:=i-1; ?Begin Arr[j+1]:=Arr[j]; j:=j-1;End; Arr[j+1]:=Tmp;End;

5.1. While(j<0)and(Arr[j]<Tmp)do

5.2. While(j>0)and(Arr[j]>Tmp)do

5.3. While (j>0)and(Arr[j]<Tmp)do

5.4. While(j=0)and(Arr[j]=Tmp)do

6. Алгоритм сортировки массива бинарными включениями

6.1. вставляет i - йэлемент в готовую последовательность, которая пока не отсортирована, для нахождения места для i - гоэлемента используется метод бинарного поиска элемента.

6.2. вставляет i - йэлемент в готовую последовательность, которая уже отсортирована, для нахождения места для i - гоэлемента используется метод бинарного поиска элемента.

6.3. вставляет i - йэлемент в готовую последовательность, которая уже отсортирована, для нахождения места для i - гоэлемента используется метод Шелла поиска элемента.

6.4. вставляет i - йэлемент в пока готовую последовательность, которая пока не отсортирована, для нахождения места для i - гоэлемента используется метод Шелла поиска элемента.

7. При сортировке массива бинарными включениями всего будет произведено

7.1. N × log ₂ N сравнений.

7.2. × log ₂ N сравнений.

7.3. log ₂ (N/ 2 ) сравнений.

7.4. N /2*log ₂ N сравнений.

8. Изменится ли количество пересылок в сортировке массива бинарными включениями по отношению к количеству сравнений

8.1. станет больше

8.2. станет меньше

8.3. не изменится.

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

9.1. бинарным поиском находится позиция вставки, затем все элементы готовой последовательности, находящиеся левее этой позиции, сдвигаются вправо.

9.2. бинарным поиском находится позиция вставки, затем все элементы готовой последовательности, находящиеся правее этой позиции, сдвигаются влево.

9.3. бинарным поиском находится позиция вставки, затем все элементы готовой последовательности, находящиеся правее этой позиции, сдвигаются вправо.

9.4. бинарным поиском находится позиция вставки, затем все элементы готовой последовательности, находящиеся левее этой позиции, сдвигаются влево.

10. В чем состоит идея сортировки массива методом Шелла?

10.1. сортировке подвергаются не все подряд элементы последовательности, а только отстоящие друг от друга на определенном расстоянии большем h.

10.2. сортировке подвергаются не все подряд элементы последовательности, а только отстоящие друг от друга на определенном расстоянии меньшем h.

10.3. сортировке подвергаются не все подряд элементы последовательности, а только отстоящие друг от друга на определенном расстоянии h.

10.4. сортировке подвергаются не все подряд элементы последовательности, а только h элементов.

<

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать