Лабораторная работа 4.
Сортировка.

Задание

Контрольные вопросы и задания

Несколько замечаний перед тем, как приступить к выполнению задания...

Задание

  1. Изучите теорию... смотри здесь и здесь

  1. Задача: Напишите программу, которая сортирует  3 последовательности: отсортированную, случайно сгенерированную (при помощи встроенных средств соответствующей системы программирования) и отсортированную в обратном порядке, тремя различными методами сортировки (согласно своему варианту). Подсчитайте время выполнения в каждом случае и выведите эту информацию на экран в виде таблички для анализа методов.

    Указание
    1. Для проверки работы методов используйте небольшие N, например 10, 20. А для решения задачи используйте большие N, например 50 000, 100 000.
    2. Для проверки работы п/п сортировки - напишите функцию Chek(a:TMass):boolean - возвращающая истину когда a - отсортирован, и ложь в противном случае.

    Входные данные: вводится с клавиатуры
    N - число элементов последовательностей;

    Выходные данные: выводятся в файл output.txt

    вывести количество элементов
    вывести случайную последовательность
    метод1: та же последовательность, но отсортированная методом1
    метод2: та же последовательность, но отсортированная методом2
    метод3: та же последовательность, но отсортированная методом3
    вывести таблицу след вида:

    Метод       отсортированная случайная отсортированная в обратном порядке
    метод1 время выполнения время выполнения время выполнения
    метод2 время выполнения время выполнения время выполнения
    метод3 время выполнения время выполнения время выполнения

    ячейки заполненные курсивом - заполнить своими результатами!

     

    Вариант 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
    Задачи 1
    2
    6    		 1
    3
    6    		 1
    4
    6    		 1
    5
    6    		 1
    2
    6    		 1
    3
    6    		 1
    4
    6    		 1
    5
    6    		 1
    2
    6    		 1
    3
    6    		 1
    4
    6    		 1
    5
    6    		 1
    2
    6    		 1
    3
    6    		 1
    4
    6    		 1
    5
    6    		 1
    2
    6    		 1
    3
    6    		 1
    4
    6    		 1
    5
    6

    1)    Обменная сортировка (метод пузырька);

    2)    Сортировка простыми вставками;

    3)    Сортировка выбором;

    4)    Сортировка слиянием;

    5)    Метод Шелла;

    6)    Быстрая сортировка;

     

Контрольные вопросы и задания

  1. Что такое сортировка?
  2. Что такое внутренняя и внешняя сортировка?
  3. Что такое эффективность алгоритма?
  4. Какая из перечисленных видов сортировки является наиболее (не)эффективной?
  5. В чем суть метода сортировки простыми вставками?
  6. В чем суть метода сортировки простым выбором?
  7. В чем суть метода быстрой сортировки?
  8. В чем суть метода сортировки Шелла?