Печатать эту главуПечатать эту главу

§ 18. Сортировка одномерного массива

Упражнения

    

1. Дан линейный массив (вектор) из целых чисел. Написать программу сортировки массива. Данные сгенерировать случайным образом.

    1. Так, чтобы все кратные трем стояли в начале массива, а не кратные в конце.
    2. В порядке возрастания суммы цифр числа.
    3. В порядке убывания количества делителей числа.

2. Дан линейный массив (вектор) из слов. Написать программу сортировки массива. Данные читать из файла.

    1. По количеству букв в слове, в порядке возрастания.
    2. По количеству согласных букв в слове, в порядке убывания.
    3. По количеству различных букв в слове, в порядке возрастания.

3. Дан линейный массив (вектор) из структур. Написать программу сортировки массива. Данные читать из файла. Можно использовать файлы, созданные для упражнения 6 после § 17.

1. В файле хранятся: название страны, столица, площадь (тыс. км2) и количество населения (млн чел.).

Беларусь    Минск         208       9.41

Россия      Москва        17075     143.3

США         Вашингтон     9373      310.2

Канада      Оттава        9985      34.2

Франция     Париж         547       65.4

И т.д.

Отсортировать данные в порядке возрастания площади.

2. В файле хранятся: название производителя стиральной машины, ее модель, мощность и максимальная загрузка белья (кг).

Samsung      WW65K52E69S       2400      6.5

Bosch        WLT24440OE        2300      7

Haier        HW70-BP12758S     1900      7

LG           F12M7NDS0         1700      6

И т.д.

Отсортировать данные в алфавитном порядке по названию производителя.

3. В файле хранятся: название озера, область в которой расположено, его объем (млн м3), площадь (км2), максимальная глубина (м) и прозрачность(м).

Нарочь    Минская       710      79.6     24.8     7.4

Снуды     Витебская     107      22       16.5     6.6

Ричи      Витебская     131.5    12.9     51.9     5.5

Свитязь   Гродненская   7.76     25.2     15       5.2

И т.д.

Отсортировать данные в порядке убывания прозрачности.

4*. Провести исследование методов сортировок (выбором, обменом и вставками). Подготовить отчет в электронных таблицах (можно использовать совместный доступ к таблице). Программы для каждой сортировки скомпилировать в режиме release. Запускать откомпилированные программы из операционной системы, используя файловый менеджер.

Для измерения времени можно использовать int t1 = clock(); из библиотеки ctime, выдает время в миллисекундах. Время замерять до начала работы алгоритма и после окончания работы алгоритма (разница — время работы алгоритма).

Для выполнения работы руководствоваться следующим планом (для каждого алгоритма):

    1. Сгенерировать текстовый файл из 20 000 целых чисел (диапазон чисел: –10000..10000).
    2. Измерить и записать время работы программ для полученного файла.
    3. Сгенерировать текстовый файл из 20 000 целых чисел (диапазон чисел: –100..100).
    4. Измерить и записать время работы программ.
    5. Увеличить количество элементов в пунктах 1 и 3 в два раза (до 40 000). Как изменить время выполнения программы?
    6. Пункты 1—5 выполнить 10 раз.
    7. Отсортировать в обратном порядке уже отсортированный массив для:

7.1. 20000 целых чисел (диапазон чисел –10000..10000). 
7.2.  20000 целых чисел (диапазон чисел –100..100);
7.3. 40000 целых чисел (диапазон чисел –10000..10000;
7.4. 40000 целых чисел (диапазон чисел –100..100).

8. Найти среднее значение времени по всем видам сортировок (от суммы отнять минимальное, максимальное и разделить на 8).
9. Определить минимальное количество элементов, при которых каждая программа будет работать больше 30 секунд.

5*. Определить время работы алгоритма быстрой сортировки для тех же файлов, которые использовались в упражнении 4. Сделать выводы.