прикреплённый файл:joinsort.py к странице LecturesVMSH/Python/2012-12-14

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Сортировка файла методом слияния.
   5 Хранение промежуточных результатов в двух файлах
   6 '''
   7 
   8 import os, pickle
   9 
  10 def joinsort(F1):
  11     '''Слияние двух файлов, состоящих из последовательностей упорядоченных строк,
  12     не менее одной строки в каждой. Результат — два новых файла.
  13     Первый содержит объеденённые попарно упорядоченные чётные последовательности
  14     исходных файлов, второй — нечётные. После чего исходные файлы заменяются новыми.
  15     Процесс повторяется, пока второй файл не окажется пустым'''
  16 
  17     F = F1, F1+"2", F1+"A", F1+"B"
  18     # Для начала сольём исходный файл с пустым
  19     open(F[1],"w").close()
  20     n = -1
  21     while n:
  22         f = open(F[0],"r"), open(F[1],"r"), open(F[2], "w"), open(F[3],"w")
  23         s, n = [f[0].readline(), f[1].readline(), ""], 0
  24         while s[0] or s[1]:
  25             # Не закончилась ли последовательность?
  26             if s[2] > max(s[1],s[0]):
  27                 s[2], n = "", n+1
  28             # Строка из какого файла меньшая, но непустая?
  29             k = s[1] and (not s[0] or s[0] >= s[1] >= s[2]) and 1 or 0
  30             f[2+n%2].write(s[k])
  31             s[2], s[k] = s[k], f[k].readline()
  32         os.rename(F[2], F[0]); os.rename(F[3], F[1])
  33     os.remove(F[1])
  34 
  35 if __name__=="__main__":
  36     joinsort("file.data")