#pragma css /css/2013.css
<<BI>>

= Алгоритмы сортировки =

 * ''(0.3 балла)'' Написать программу. Программа получает на вход файл, в котором в одну строку записаны числа через пробел (проверять соответствие файла формату не требуется). Программа сортирует массив алгоритмом быстрой сортировки и пишет элементы массива на экран в порядке возрастания.
 * ''(1 балл)'' Напишите программу. Программа получает на вход файл, в котором в одну строку записаны числа через пробел (проверять соответствие файла формату не требуется). Программа реализует сортировку двумя алгоритмами из списка: пузырьком, слиянием, быстрой сортировкой. Программа измеряет время для сортировки входного массива каждым из реализованных алгоритмов, проверяет, что обе сортировки выдали один и тот же результат, и пишет на экран отсортированный в порядке возрастания элементов массив и получившиеся времена работы. Для оценки времени используйте большие массивы (подберите размер массива так, чтобы была разница между разными алгоритмами сортировки!)
 * ''(1.2 балла)'' Напишите программу. Программа генерирует наборы входных массивов разной длины разными методами: полностью упорядоченный массив, массив, в котором только один элемент стоит не на месте, массив, состоящий из нескольких кусков, каждый из которых упорядочен, массив, в котором элементы идут примерно по возрастанию, -- все те же методы для элементов по убыванию, и массив из полностью случайных элементов. Программа реализует сортировку тремя алгоритмами: пузырьком, слиянием, сортировкой. Программа генерирует каждым методом массивы длины 500, 1000, ... 100000 и для каждого типа массивов для каждой длины пишет время, которое требуется каждому алгоритму сортировки для того, чтобы отсортировать массив. Программа должна иметь параметры командной строки, которые позволяют выбирать диапазоны, в которых меняются длины массивов, выбирать типы массивов, алгоритмы сортировки.

= Структуры данных =
 * ''(0.3 балла)'' Написать программу, реализующую двусвязный список чисел. Реализовать процедуру добавления, удаления элемента из списка, а также поиска.

 * ''(0.7 балла)'' Написать процедуру сортировки двусвязного списка.

 * ''(1 балл)'' Написать программу, "переворачивающую" односвязный список за линейное время с постоянной памятью (первый элемент становится последним, второй - предпоследним и т.д.)

== Подсказки ==

Для работы со временем в питоне есть модуль datetime. Пример работы с этим модулем:

{{{#!python
from datetime import datetime
# класс datetime в модуле datetime можно использовать напрямую,
# но проще создавать объекты этого класса, используя функцию datetime.now()
t1 = datetime.now() # запоминаем нынешнее время в переменную t1
x = range(100500) # долго думаем
t2 = datetime.now() # время после того, как подумали
print t1 # печатаем время начала
print t2 # время конца
print t2 - t1 # печатаем разность между временем начала и конца
}}}