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

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

  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 (last edited 2012-01-18 10:07:44 by FrBrGeorge)