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

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Сортировка файла методом слияния
   5 '''
   6 
   7 import os
   8 
   9 def fsplit(File):
  10     '''Поделить файл File на несколько отсортированных файлов File0…FileN
  11     (хотя бы по одной строке в файле).
  12     Возвращает количество файлов'''
  13     f,o,n=open(File,"r"),"",0
  14     tf=open(File+str(n),"w")
  15     for s in f:
  16         tf.write(o)
  17         if o>s:
  18             tf.close()
  19             n+=1
  20             tf=open(File+str(n),"w")
  21         o=s
  22     tf.write(o)
  23     tf.close()
  24     return n+1
  25 
  26 def fjoin(F1, F2, F3):
  27     '''Слить два упорядоченных файла F1 и F2 в файл F3'''
  28     F=F3+"_"                # Временный файл
  29     f1, f2, f = open(F1,"r"), open(F2,"r"), open(F,"w")
  30     s1, s2 = f1.readline(), f2.readline()
  31     while s1 or s2:         # Какой-то из файлов непуст
  32         if s1 and (not s2 or s1 <= s2):
  33             f.write(s1)
  34             s1=f1.readline()
  35         else:
  36             f.write(s2)
  37             s2=f2.readline()
  38     f1.close(),f2.close(),f.close()
  39     os.rename(F,F3)
  40 
  41 def joinsort(File):
  42     '''Сортировка файла слиянием с хранением промежуточных файлов'''
  43     n=N=fsplit(File)
  44     while n>1:
  45         # Если файлов нечётное число, заведём ему пустую пару
  46         if n%2:
  47             open(File+str(n),"w").close()
  48             n+=1
  49         # Сольём файлы попарно
  50         for i in xrange(0,n,2):
  51             fjoin(File+str(i), File+str(i+1), File+str(i/2))
  52         n/=2
  53     os.rename(File+"0", File)
  54     # Удалим все временные файлы
  55     for i in xrange(1,N):
  56         os.unlink(File+str(i))
  57 
  58 joinsort("file.data")