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

• Поиск элемента в упорядоченном наборе данных с помощью половинного деления
• Простейшая сортировка путём циклического нахождения максимума («сортировка выбором»)
• Понятие о вычислительной сложности: количество операций (сравнения, чтения, записи) как функция от общего числа элементов
• Вычислительная сложность сортировки выбором
• Сортировка вставками. Сложность для динамических (список) и статических (массив) структур данных
• Слияние двух отсортированных последовательностей. Сортировка бинарным и естественным слиянием. Оценка сложности.

• «Быстрая» сортировка

Домашнее задание

1. Прочитать про алгоритмы сортировки (например, в Википедии)

2. Реализовать любой алгоритм сортировки

   •    1 # Метод поиска наименьшего
        2 for i in xrange(len(A)-1):
        3   for j in xrange(i,len(A)):
        4     if A[i]>A[j]:
        5       A[i],A[j]=A[j],A[i]
     

3. Реализовать любой «эффективный» алгоритм сортировки (имеющий сложность порядка N*log(N))

   • sort_a.py

4. (простая олимпиадная задача) Дано очень много (N>10000000) натуральных чисел в диапазоне 1..100. Вывести их в отсортированном виде за число действий меньшее, чем N*log(N).

   • Если кто не делал домашнего задания, я не виноват. Это просто сортировка подсчётом (см. соотв. статью в Википедии):

        1 C=[0]*100
        2 for a in A:
        3     C[a]+=1
        4 for i in xrange(100):
        5     for c in xrange(A[i]):
        6         print i
     

5. Написать визуализатор сортировки (похожий на примеры в английской Википедии) с помощью PyGame

   • Не бояться часто перерисовывать весь экран (компьютер работает быстрее)

   • Не забывать делать pygame.display.flip() после каждой перерисовки (иначе её не будет видно)

   • Если компьютер всё равно работает слишком быстро, можно вставить time.sleep(доли_секунды) (из модуля time)

   • Нагляднее всего сортировать random.shuffle() от какого-нибудь range() и представлять массив в виде шеренги прямоугольников пропорциональной высоты

   • Для красоты можно менять и цвет, но это не так-то просто

     • Пример модуля визуализации: sortG.py. С использованием цветовой модели HSV всё оказалось крайне просто!

     • Пример сортировки выбором с использованием модуля визуализации: sort_s.py

Условные обозначения

• — тема по Linux

• ­— необязательная тема

• — теоретическое задание

• — тема для самостоятельного изучения

CategoryClass CategoryVmsh