Документ взят из кэша поисковой машины. Адрес оригинального документа : http://uneex.lorien.cs.msu.su/LecturesVMSH/2012-01-11
Дата изменения: Unknown
Дата индексирования: Sat Apr 9 23:51:00 2016
Кодировка: UTF-8
LecturesVMSH/2012-01-11 - UNИX

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

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

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

  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))

  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

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

CategoryClass CategoryVmsh

LecturesVMSH/2012-01-11 (последним исправлял пользователь FrBrGeorge 2012-01-18 10:07:44)