Перейти на главную   
  helloworld.ru - документация и книги по программированию  
helloworld.ru - документация и книги по программированию    
    главная     хостинг     создание сайтов    
Поиск по сайту:  
Смотрите также
Языки программирования
C#
MS Visual C++
Borland C++
C++ Builder
Visual Basic
Quick Basic
Turbo Pascal
Delphi
JavaScript
Java
PHP
Perl
Assembler
AutoLisp
Fortran
Python
1C

Интернет-технологии
HTML
VRML
HTTP
CGI
FTP
Proxy
DNS
протоколы TCP/IP
Apache

Web-дизайн
HTML
Дизайн
VRML
PhotoShop
Cookie
CGI
SSI
CSS
ASP
PHP
Perl

Программирование игр
DirectDraw
DirectSound
Direct3D
OpenGL
3D-графика
Графика под DOS

Алгоритмы
Численные методы
Обработка данных

Системное программирование
Драйверы

Базы данных
MySQL
SQL

Другое

Хостинг


Друзья
demaker.ru
Реклама

Лучший хостинг. Аренда серверов




helloworld.ru

Мгновенный Python


Перевод: Михаил Александрович Беланов
(belanov@starcity.tcnet.ru)


Это минимальный экспресс - курс программирования на языке Python (или Пайтон). Для более глубокого изучения ищите документацию на посвящённом ему WEB-сайте, http://www.python.org , особенно на странице "Tutorial" Если вы не понимаете, почему вы должны интересоваться языком Python, то посмотрите там же страницу "Comparison" , где даётся сравнение Python с другими языками.

1. Основы


Для начала рассматривайте Python как псевдокод. Это почти правда. Переменные как-будто не имеют типов - поэтому их не требуется их объявлять. Они возникают, когда вы присваиваете им значения, и исчезают, когда вы больше их не используете. (Типы переменных определяются автоматически при выполнении программы). Присваивание осуществляется оператором = , а равенство проверяется оператором == . Вы можете присвоить значения нескольким переменным зараз:


	x, y, z = 1, 2, 3
	first, second = second, first	
(прим.перев.: сначала вычисляются все выражения в правой части равенства, слева направо, потом эти значения по очереди присваиваются переменным, перечисленным в левой части)

	a = b = 123
	
Блоки операторов обозначаются отступами, и только отступами (никаких "операторных скобок" вроде BEGIN - END или фигурных скобок). Вот некоторые обычные управляющие структуры:

	if  (x > 10) and (x < 20) :
		print "икссс хороший"
if 10 < x < 20 : print "икссс хороший"
for i in [1, 2, 3, 4, 5] : print "это - номер цикла: ", i
x = 10 while x > 0 : print "x всё ещё положительный"
Первые два примера эквивалентны.
Переменная цикла (индекс) в примере цикла for принимает все возможные значения из списка (list), (который записывается как в примере). Чтобы сделать "обыкновенный" цикл (т.е. со счётчиком количества выполнений), используйте встроенную функцию range() .

	#Печатает все значения от 0 до 99 включительно:
	for value in range (100) :
		print value
(Строка программы, начинающаяся с "#", является комментарием и игнорируется интерпретатором).

Хорошо, теперь вы знаете достаточно (в теории), чтобы записать любой алгоритм на Python. Давайте добавим некоторый элементарный интерфейс пользователя. Чтобы он мог вводить данные (по приглашению программы), используйте функцию input :

	x = input ("Введи сюда число:")
		print "Квадрат этого числа составляет ", x * x

Функция input показывает заданное приглашение (которое может быть пустым), позволяя пользователю ввести любое допустимое в Python значение. В данном примере мы ожидаем, что будет введено число. Но если будет введено что-то другое (скажем, строка), то случится "крах" программы. Чтобы избежать этого, нам понадобится какой-то контроль ошибок. Я не хочу углубляться в это. Достаточно сказать, что если вы хотите, чтобы то, что ввёл пользователь, было запасено в программе буквально, в виде строки символов, то используйте вместо input функцию raw_input .
Замечание. Если вы хотите, чтобы по функции input вводилась строка символов, то пользователь должен в явном виде указывать кавычки вокруг неё. В Python для строк может использоваться пара как одинарных, так и двойных кавычек.

Итак, у нас есть управляющие структуры, ввод-вывод, теперь мы хотим иметь какие-то интересные структуры данных (то есть типы всё же есть). Наиболее важными из них являются списки (list) и словари (dictionary). Списки записываются в квадратных скобках и, естественно, могут быть вложенными:


	name = ["Cleese", "John"]
	x = [[1, 2, 3], [y, z], [[ ]] ]

Одним из привлекательных качеств списков является то, что вы можете обращаться к их элементам не только по отдельности, но и по группам, используя индексацию (indexing) и сечения (slicing). Индексация, как и во многих других языках, производится добавлением к имени списка индекса в квадратных скобках (учтите, что первый элемент имеет индекс 0).

	print name [1], name [0]
	Печатает: "John Cleese"
	name [0] = "Smith"

Сечения напоминают индексы, однако вы указываете начальный и конечный индекс, через ":", получая в результате подсписок:

	x = ["мусор", "мусор", "мусор", "яйца", "и", "мусор"]
	print x [3:5]
	Печатает список: ["яйца", "и"]

Обратите внимание, что верхняя граница диапазона индексов не включительная. Если одна из границ диапазона опущена, то подразумеваются все элементы в том направлении. Например, выражение spisok [:3] означает "каждый элемент списка spisok с первого и до третьего, не включительно". (Вы можете возразить, что индекс 3 на самом деле означает четвёртый элемент, поскольку счёт идёт с 0. Действительно ...). С другой стороны, выражение spisok [3:] означает "все элементы списка, начиная с имеющего индекс 3, включительно, и до конца списка, включая последний". Действительно интересный результат можно получить, применяя отрицательный индекс: spisok [-3] это третий элемент с конца. Говоря об индексах, нужно упомянуть, что встроенная функция len даёт длину списка.

Теперь насчёт словарей. Говоря попросту, они похожи на списки, только элементы в них не упорядочены. Как вы можете делать индексацию в них? Для этого каждый элемент имеет ключ (key), или "имя", по которому его можно найти точно так же, как в обычном словаре. Вот несколько примеров словарей:

	{"Alice" : 23452532, "Gennady" : 252336, "Clarice" : 2352525}
	person={'имя' : "Robin", 'фам.' : "Hood", 'занятие' : "партизан"}

Теперь чтобы узнать, чем занимается человек, перечисленный в словаре person, мы используем выражение вида person ['занятие']. Если мы хотим изменить фамилию человека, мы пишем:

	person ['фамилия'] = "of Locksley"

Просто, не так ли? Как и списки, словари могут содержать в себе другие словари. Или списки, кстати. И, естественно, списки могут содержать в себе словари. Это позволяет вам создавать довольно сложные структуры данных.

2. Функции


Следующий шаг: абстракция . Мы хотим присвоить имя куску программного кода и затем вызывать его, задавая параметры. Другими словами, мы хотим определять функции (или процедуры). Это легко. Для определения функции используйте ключевое слово def , как в примере:


	def square (x) :
		return x*x

	print square (2)
	Печатает: 4

Для тех из вас, кто понимает, что это такое: все параметры функций в Python передаются по ссылке (как, например, в Java). Для тех, кто не понимает: не заботьтесь об этом. Python имеет такие привлекательные особенности, как именованные аргументы функций и значения для аргументов по умолчанию. Более подробно об этом см в Разделе 4.7 "Tutorial" -а, или в пункте 10.4 "Семинара"

Если вы имеете общее представление о том, как пользоваться функциями, то это в основном и всё, что вам надо знать об их использовании в Python (Да, ещё: ключевое слово return останавливает работу функции и возвращает указанное значение в качестве её результата). Важно, однако, знать, что Python функции являются значениями. Поэтому, если вы имеете функцию, скажем, square, то вы можете написать:

	queeble = square
	print queeble (2)
	Печатает: 4

Вызывая функцию без аргументов, не забывайте писать её имя со скобками, т.е. doit (), а не doit. В последнем случае будет, как показано выше, возвращена сама функция как значение (это бывает нужно для задания методов для объектов, о чём см. ниже).

3. Объекты и всё, что к ним относится


Я предполагаю, что вы знаете, как действует объектно-ориентированное программирование. (В противном случае этот раздел для вас будет не слишком полезен, но это неважно. Можно начать программировать и без объектов). В Python вы определяете класс, используя (вот сюрприз) ключевое слово class . Например:


	class Basket :
	#создаём класс Basket ("корзина") с
	#методами add("поместить что-то в корзину")
	# и print_me ("распечатать всё содержимое
	#корзины").Не забывайте использовать
	#аргумент "self"
		def __init__(self, contents=NONE):
			self.contents = contents or []
def add (self, element): self.contents.append (element)
def print_me (self): result = "" for element in self.contents: result = result + " " + `element` print "Содержит:" + result

Здесь новым является то, что:

  1. Все методы (функции, заданные для объекта) имеют дополнительный аргумент, находящийся в начале списка аргументов - а именно self ( "сам" ). Он имеет специальное значение - обозначает сам объект определяемого класса.
  2. Методы вызываются в программе так: Объект.Метод (Аргументы) .
  3. Некоторые имена методов, такие как __init__ , предопределены и имеют специальное значение. Так, __init__ - это имя конструктора класса, т.е. функции, которая автоматически вызывается каждый раз, когда вы создаёте экземпляр класса (т.е. переменную).
  4. Некоторые аргументы являются необязательными и им даётся значение по умолчанию (как было упомянуто выше, в рассказе о функциях). Значение по умолчанию задаётся следующим образом:
    	def f (x=100):
    		...
    
    Здесь функция f может быть вызвана с одним параметром или без параметров. Если она вызвана без параметров, то по умолчанию параметру x присваивается значение 100.
  5. "Логика коротких заключений" (short cirquit logic). Это умно. См. ниже.
  6. Кавычки с обратным наклоном преобразуют объект в его строковое представление (так что если element содержит число 1, то `element` это строка "1", в то время как 'element' это строка со словом element).
  7. Знак сложения + используется для конкатенации списков, а также и строк, поскольку они в действительности являются списками символов (это означает, что вы можете использовать для строк индексацию, сечения и функцию len . Потрясно, правда?.
В Python никакие методы классов не являются защищёнными (приватными и т.п.). Инкапсуляция в основном является вопросом стиля программирования.

Теперь о "логике коротких заключений" ...
Все значения в Python могут использоваться как логические. Те, которые "пусты" (как 0, [] или "" и None ) представляют логическое значение "ложь" , а большинство других (напр., [0], 1, "Hello, comrade") представляют логическое значение "истина" . Поэтому значения логических выражений вроде a and b ("a И b") вычисляются следующим образом: сначала проверяется, является ли a истиной. Если нет, то просто возвращается a. Если да, то возвращается b (которое будет представлять истиностное значение выражения). Аналогично, для значения выражения a or b ("a ИЛИ b") имеем: если a истинно, то возвращается a. Если нет, то возвращается b.

Этот позволяет операторам and и or действовать наподобие булевых операторов "и" и "или", которые они призваны представлять, но он также даёт способ короткой записи условных выражений. Например, выражение:


	if a:
		print a
	else:
		print b

можно записать короче:
	print a or b
Фактически, подобное сокращение представляет собой нечто вроде идиомы в Python, поэтому вам надо к нему привыкнуть. Мы уже использовали его в методе Basket.__init__. Аргумент contents имеет значение по умолчанию None (ничего), которое помимо прочего означает логическую "ложь" . Поэтому, чтобы проверить, что contents имеет какое-то значение, мы могли бы написать:
	if contents :
		self.contents = contents
	else:
		self.contents = []

Теперь вы, конечно, знаете, что есть лучший способ. А почему просто мы не присваиваем с самого начала значение по умолчанию [] параметру contents? В этом случае Python присвоил бы всем нашим "корзинам" ( экземплярам объекта Basket) одно и то же значение по умолчанию, пустой список []. Когда мы стали бы заполнять один список, все остальные стали бы содержать те же элементы, и уже не имели бы значения по умолчанию. Чтобы лучше уяснить этот момент, прочитайте в документации по Python объяснение разницы между идентичностью (identity) и равенством (equity). Другой способ записи вышеприведённого фрагмента:

	def __init__ (self, contents=[]) :
			self.contents = contents [:]

Вы можете сообразить, как это работает? Вместо того, чтобы везде использовать один и тот же пустой список, мы с помощью выражения contents [:] делаем его копию. (Мы просто делаем сечение списка, включая в него все элементы списка. Это сечение и является нужной нам копией). Итак, чтобы создать экземпляр объекта Basket и использовать его (т.е. вызывать некоторые его методы), мы можем написать примерно следующее:


	b = Basket (['яблоко', 'апельсин'])
	b.add ("лимон")
	b.print_me ()
	Печатает: яблоко апельсин лимон

Есть и другие магические методы, кроме __init__ . Одним таким методом является __str__ , который задаёт, как будет выглядеть объект, когда он рассматривается как строка. Мы можем использовать его для нашей "корзины" вместо метода print_me:
	def __str__ (self) :
		result = ""
		for element in self.contents :
			result = result + " " + element
		return "Старая дырявая корзина содержит:" + result

Теперь, если мы хотим распечатать содержимое "корзины" b, мы пишем в программе:
	print b
Потрясно? Образование подкласса осуществляется следующим образом:
	class SpamBasket (Basket) :
		# ...
	(вводим новый класс "мусорная корзина"
		как подкласс класса "корзина").

Python допускает множественное наследование, поэтому вы можете указать в круглых скобках сразу несколько суперклассов, разделяя их запятыми. Экземпляр класса создаётся так:
	x = Basket ()
Конструкторы, как я уже сказал, задаются с помощью специальной функции-члена класса __init__ . Предположим, класс SpamBasket имеет конструктор __init__ (self, type), где параметр type будет обозначать тип содержимого в "мусорной корзине". Тогда мы можем создать новую "мусорную корзину" так:
	y = SpamBasket ("яблоки")
Больше о чудесах объектно-ориентированного программирования на Python вы сможете узнать в "Tutorial", Раздел 9 (или "Семинар", Глава 9 ).

4. Хитрость для ума Джедая


(Этот раздел включён потому, что он кажется мне впечатляющим. Но он определённо не является необходимым для того, чтобы начать программирование на Python).

Вам нравятся идеи, пугающие ум? Тогда, если у вас хватит смелости, попытайтесь понять эссе Гвидо ван Россума о метаклассах на зарубежном языке . Если, однако, вы предпочтёте не свихнуться, то вас может удовлетворить описанная здесь маленькая хитрость. Python использует не лексические, как обычно, а динамические пространства имён. Это означает, что если у вас есть функция вроде:

	def orange_juice () :
		return x*2

где переменная (в данном случае x) не связана с аргументом и не получает значения внутри функции, то Python использует то значение, которое она имела в момент вызова функции. В данном случае:

	x = 3
	orange_juice ()
	Возвращает: 6

	x = 1
	orange_juice ()

	Возвращает: 2

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

	x = 4
	def apple_juice (x = x) :
		return x*2

Здесь аргументу x даётся значение по умолчанию, которое совпадает со значением одноимённой переменной x, каким оно было во время определения функции. Таким образом, если вызывать функцию без аргумента, то получится следующее:

	x = 3
	apple_juice ()
	Возвращает: 8
	x = 1
	apple_juice ()
	Возвращает: 8

Итак, значение x не изменяется. Если бы это было всё, чего вы хотели, то мы могли бы с тем же успехом написать:
	def tomato_juice () :
		x = 4
		return x*2

или даже:
	def carrot_juice () :
		return 8

Однако идея состоит в том, что значение x берётся из программного окружения функции и сохраняется таким, каким оно было в момент определения функции. Как это может быть полезно? Рассмотрим следующий пример - функция, которая комбинирует две другие функции. Мы хотим, чтобы функция работала примерно так:

	from math import sin, cos
	sincos = compose (sin, cos)
	x = sincos (3)
где compose - функция, которую мы хотим создать, а x имеет значение -0.836021861538, которое равно значению выражения sin(cos(3)). Теперь, как мы будем делать это? Ясно, что функция compose берёт в качестве параметров две функции, а возвращает ещё одну функцию, которая в свою очередь, берёт один параметр. Следовательно, схема решения может быть такой:
	def compose (fun1, fun2) :
		def inner (x) :
			# ...задаём функцию, которая будет
			# возвращаемым значением для compose
		return inner

Мы могли бы попытаться поместить в тело функции inner оператор return fun1 (fun2 (x)) и остановиться на этом. Нельзя, однако. Такая функция вела бы себя очень странно. Вообразите следующий сценарий:
	from math import sin, cos
	def fun1 (x) :
		return x + " comrade!"
	def fun2 (x) :
		return "Hello, "
	sincos = compose (sin, cos) #используя неправильную версию

Каково теперь значение x? Правильно, "Hello, comrade!". Почему так? Потому, что в момент вызова, функция compose берёт значения функций fun1 и fun2 из своего программного окружения, а не те fun1 и fun2, которые присутствовали в программе в момент создания функции. Всё, что нам нужно сделать, чтобы получить работающее решение, это применить ранее описанный мною приём:

	def compose (fun1, fun2)
		def inner (x, fun1=fun1, fun2=fun2) :
			return fun1 (fun2 (x))
		return inner

Теперь мы только можем надеяться, что никто не вызовет результирующую функцию с более чем одним аргументом, так как это может катастрофические последствия для неё. И, кстати, нам не требуется вводить имя для функции inner - раз она содержит только одно выражение, то мы можем использовать анонимную функцию, которая объявляется, используя ключевое слово lambda вместо имени:

	def compose (f1, f2) :
		return lambda x, f1=f1, f2=f2 : f1 (f2 (x))

Кратко, но всё же понятно. Вам полюбить этот стиль(шутка).

5. А теперь ...


Напоследок упомянем ещё несколько вещей. Большинство полезных функций и классов помещены в модули, которые фактически представляют собой текстовые файлы, содержащие программный код на языке Python. Вы можете импортировать их в свою программу и использовать. Например, чтобы использовать метод split из стандартного модуля string , вы можете сделать следующее:

	import string
	x = string.split (y)

или ...
	from string import split
	x = split (y)

Более подробно о модулях стандартной библиотеки, см. http://www.python.org/doc/lib . Там есть очень много полезного. Если вы хотите, чтобы ваша программа могла работать и как импортируемый модуль, и как независимая программа, то вы можете добавить в её конце строчку вида:

	if __name__ == "__main__": go ()

Это - способ проверить, работает ли программа в качестве выполняемого скрипта (т.е. не будучи импортирована в другой скрипт) - в этом случае будет вызвана функция go. Разумеется, вместо неё вы можете вставить после ":" любой программный код. И для тех из вас, кто хочет создавать скрипты для UNIX: чтобы скрипт работал как независимая программа, его первой строчкой должен быть следующий управляющий комментарий:


	#!/usr/bin/env python

Наконец, кратко упомянем важное понятие: исключения (exception).

Некоторые операции, такие как попытка деления на 0 или чтения из несуществующего файла, могут создавать состояние ошибки, или исключение. Вы даже можете делать свои собственные исключения и возбуждать (raise) их в подходящий момент. Если исключение никак не обрабатывается в программе, то она завершает свою работу с выдачей сообщения об ошибке. Вы можете избежать такого конца, применив оператор try/except . Например:

	def safe_division (a, b):	# безопасное деление a на b
		try :
			return a/b
		except ZeroDivisionError: # стандартное исключение
			#"деление на 0"
			return None

ZeroDivisionError - это имя стандартного исключения ("Деление на 0"). В данном примере вы могли бы перед делением вставить проверку того, что b не равно 0. Но во многих случаях такая стратегия неприменима. И. кроме того, если бы у нас не было бы секции try в теле функции safe_division ("безопасное деление"), так что по справедливости нам пришлось бы назвать её unsafe_division ("опасное деление"), то мы всё равно смогли бы обработать это исключение следующим образом:
	try:
		unsafe_division (a, b)
	except ZeroDivisionError:
		print "Деление на 0 в функции unsafe_division"

В случаях, когда у вас обычно не должна возникать некоторая проблема, но в принципе она всё же может случиться, использование обработки исключений избавит вас от трудоёмкого тестирования и.т.п.

Ну вот и всё. Надеюсь, вы научились чему-то. Теперь идите и вступайте в игру . И помните девиз обучения языку Python: "Use the source, Luke" (пользуйся источниками, Василий Иванович) (перевод: изучайте всякий текст на языке Python, который попадёт вам в руки). Для начала, вот вам пример. Это хорошо известный алгоритм "быстрой сортировки" Хоара.

(Прим. перев. Для тех, кто не знает - я прилагаю к программе комментарий с описанием этого алгоритма, взятым из известной брошюрки Д. Кнута. Я добавил эту программу к статье в виде Приложения и, кроме того, вы можете загрузить qsort.py - отдельный файл с текстом программы. Запуск на выполнение - командой python qsort.py)

Одно примечание к этому программному примеру. Переменная done ("выполнено") контролирует, завершилось ли разбиение (partition) текущего подсписка относительно разбивающего элемента (pivot) , т.е. все ли элементы подсписка перемещены. Поэтому когда любой из двух внутренних циклов хочет завершить всю последовательность взаимных перестановок элементов, он присваивает done значение 1 и прерывает себя с помощью break . Почему внутренние циклы должны использовать вспомогательную переменную done? Потому, что когда первый внутренний цикл завершается по break , то начнёт или нет работу второй внутренний цикл зависит от того, завершился ли главный цикл, то есть от того, было ли done присвоено значение 1:

	while not done:
		while not done:
			#циклы, пока не выполнится break

		while not done:
			#выполняется, только если в
			#первом цикле done
			#не присвоено значение 1
Эквивалентный, может быть, более ясный, но менее красивый вариант:
	while not done:
		while 1:
			#циклы, пока не выполнится break

		if not done:
			while 1:
				#выполняется, только если
				#done не было присвоено значение 1

Единственная причина, по которой я использовал переменную done в первом цикле - это желание сохранить симметрию между двумя циклами. Можно изменить порядок их следования в программе, а алгоритм по-прежнему будет работать. Дополнительные примеры см. на странице "Tidbit" Джо Строута (Joe Strout) .

Приложение. Пример программы QuickSort


Прим. перев.

1) Здесь приводится пример программы с функцией сортировки по алгоритму "быстрой сортировки " Хоара. Поскольку, не зная суть метода, понять программу трудно, то привожу его описание, которое можно найти в известной книжке Д.Кнута и др., используя обозначения из этого программного примера.

Этот пример - исключительно учебный, т.к. сортировка запрограммирована просто по определению метода, без дополнительных приёмов повышения эффективности. И, кроме того, в Python и так есть стандартный метод sort, который используется так: Список_итп.sort (ФСравн) , где ФСравн - необязательная пользовательская функция сравнения элементов. Если функцию не указать, то будет использована стандартная функция cmp() , которая даёт "естественный порядок" элементов. Например:


	a = [2, 5, 1, 3]
	a.sort ()
	print a
	Печатает: [1, 2, 3, 5]

Алгоритм "быстрой сортировки" (Quick Sort) Чарльза Хоара (Hoar)


Дано:
список list, индексы первого и последнего упорядочиваемых элементов - start и end.
Переменные:
bottom - меньший индекс сравниваемого элемента ("нижнего")
top - больший индекс сравниваемого элемента ("верхнего")
pivot - значение разделяющего элемента
partition - вспомогательная функция, делящая список на два подсписка, в одном из которых все элементы меньше pivot, а в другом - больше.

Выбирается произвольный элемент списка (в данном примере - последний, хотя это плохой выбор, если список уже частично упорядочен). Он называется разделяющим элементом, т.к. используется, чтобы разделить список на две части, так что в одной части элементы будут меньше разделяющего, а в другой больше. Последовательно перебираются все элементы сразу с нижнего и верхнего конца. Если значение нижнего элемента больше pivot, то он пересылается на место верхнего (значение которого уже сохранено). Если верхний элемент больше pivot, то он пересылается на место нижнего. Когда индексы верхнего и нижнего элемента совпадут, список окажется разделённым на две части - элементы с меньшим индексом, чем он стал у разделяющего (split), будут по величине не больше его, а остальные - не меньше. Следовательно, неупорядоченность останется только в пределах этих частей. Рекурсивно применяя этот алгоритм к полученным частям списка, получаем в итоге части, состоящие из одного элемента, т.е. упорядоченный список.
2) В начале программы присутствует текстовая константа, которая нигде не используется. Это не ошибка, а необязательная, но рекомендуемая в Python "строка документирования" для идентификации модуля (класса, функции). Чтобы можно было испытать программу, выделите содержащий её фрагмент этого документа (начиная со строки #!/usr/bin/env python ) и сохраните его в виде неформатированного текстового файла с именем вроде qsort.py (py - тип файла для программ на Python).

#!/usr/bin/env python

# Written by Magnus Lie Hetland 

"Everybody's favourite sorting algorithm... :)"

def partition(list, start, end):
    pivot = list[end]	# Пусть последний элем. будет разделяющим,
    bottom = start-1	# Начинаем извне разделяемой части списка
    top = end		# Аналогично

    done = 0
    while not done:	# Пока не все элем. разделены ...

        while not done:	# Пока мы не найдём
				# неупорядоченный элемент ...
            bottom = bottom+1	# ... Двигаем нижний индекс вверх.

            if bottom == top:	# Если он совпадёт с верхним ...
                done = 1	# ... то всё сделано.
                break

            if list[bottom] > pivot:	# Не является ли нижний эл.
					#неупорядоченным?
                list[top] = list[bottom]# Тогда перемещаем его
				# на место верхнего ...
                break		# ... и начинаем поиск сверху.

        while not done:	# Пока не найдём неупорядоченный эл. ...
            top = top-1	# ... двигаем верхний индекс вниз.

            if top == bottom:	# Если он совпал с нижним ...
                done = 1	# ... то всё сделано.
                break

            if list[top] < pivot:	# Является ли верхний
					# элем. неупорядоченным?
                list[bottom] = list[top]# Если да, то перемещаем
			# его на место нижнего ...
                break	# ...и начинаем поиск снизу.

    list[top] = pivot	# Помещаем разделяющий элемент на место.
    return top	# И возвращаем его индекс
		# (точку разделения подсписков).


def quicksort(list,start,end):
    if start < end:	# Если есть хотя бы
				# два элемента ...
        split = partition(list, start, end)	# ...то разделяем на
						# два подсписка и ...
        quicksort(list, start, split-1)	# ...сортируем обе половины.
        quicksort(list, split+1, end)
    else:
        return


if __name__=="__main__":# Если этот скрипт выполняется как
			# независимая программа:
    import sys
    list = sys.argv[1:]	# Получаем аргументы командной строки
    start = 0
    end = len(list)-1
    quicksort(list,start,end)	# Сортируем весь список аргументов
    import string
    print string.join(list)	# Распечатываем сортированный список.
    sys.exit (0)	# Выход из программы.












helloworld.ru © 2001-2016
Все права защищены
Rambler's Top100 TopList Rambler's Top100