Сэджвикtemplate <class Item>

int partition(Item[], int l, int r)
{
int l = l - 1, j = r; Item v = a[r];
for (;;)
{
while(a[++i] < v) ;
while(v < a[--j]) if (j == l)
break;
if (i >= j) break;
exch(a[i], a[j]);
}
exch(a[i], a[r]);
return i;
}

algolist.manual.rutemplate<class T>
void quickSortR(T* a, long N) {
// На входе - массив a[], a[N] - его последний элемент.

long i = 0, j = N; // поставить указатели на исходные места
T temp, p;

p = a[ N>>1 ]; // центральный элемент

// процедура разделения
do {
while ( a[i] < p ) i++;
while ( a[j] > p ) j--;

if (i <= j) {
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
}
} while ( i<=j );


// рекурсивные вызовы, если есть, что сортировать
if ( j > 0 ) quickSortR(a, j);
if ( N > i ) quickSortR(a+i, N-i);
}

Премия Дейкстры2000 — Лэсли Лэмпорт (Leslie Lamport) за работу о logical clocks
2001 — Майкл Фишер, Нэнси Линч, Майкл С. Пэтерсон (Michael J. Fischer, Nancy Lynch, Michael S. Paterson) за доказательство невозможности прийти к консенсусу, используя асинхронную передачу информации
2002 — Эдсгер Вибе Дейкстра за работу, которая ввела понятие саморегулируемости
2003 — Морис Херлихи, (Maurice Herlihy) за работу о разрешимости задачи о консенсусе в системах с совместно используемой памятью
2004 — Роберт Галлагер, Пьер Хамблет, Филип Спира (Robert G. Gallager, Pierre A. Humblet, Philip M. Spira) за распределенный алгоритм нахождения минимального остовного дерева
2005 — Маршал Пиз, Роберт Шостак, Лэсли Лэмпорт (Marshal Pease, Robert Shostak, Leslie Lamport) за работу о Византийском соглашении
2006 — Джон Мелло-Крамми, Майкл Л. Скотт (John M. Mellor-Crummey), Michael L. Scott) за алгоритм взаимного исключения
2007 — Синтия Дворк, Нэнси Линч, Лэрри Стокмайер (Cynthia Dwork, Nancy Lynch, Larry Stockmeyer) за работу о решении задачи о консенсусе в частично синхронных системах
2008 — Барух Авербух, Дэвид Пелег (Baruch Awerbuch, David Peleg) за работу о sparse partitions

Премия Кнута1996 — Эндрю Яо
1997 — Лесли Вэлиант (Leslie Valiant)
1999 — Ласло Ловас (László Lovász)
2000 — Джеффри Ульман (Jeffrey Ullman)
2002 — Христос Пападимитриу (Christos Papadimitriou)
2003 — Миклош Айтаи (Miklos Ajtai)
2005 — Михалис Яннакакис (Mihalis Yannakakis)
2007 — Нэнси Линч (Nancy Lynch)
2008 — Фолькер Штрассен (Volker Strassen)]

Премия Гёделя1993 Ласло Бабаи, Шафи Гольдвассер, Сильвио Микали, Шломо Моран и Чарльз Ракофф (László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran, Charles Rackoff) за разработку интерактивные системы доказательств
1994 Йохан Хостад (Johan Håstad) за доказательство принадлежности функции чётности (на boolean circuits) к экспоненциальному классу сложности
1995 Нил Иммермэн, Роберт Шелепчени (Neil Immerman, Róbert Szelepcsényi) за теорему Иммермэна-Шелепчени (теория сложности вычислений)
1996 Марк Джеррам, Элистер Синклер (Mark Jerrum, Alistair Sinclair) за исследования цепей Маркова и аппроксимацию перманента матриц
1997 Джозеф Хэлперн, Йорам Мосес (Joseph Halpern, Yoram Moses) за формальное определение понятия «знание» в распределённых средах
1998 Сейносуке Тода (Seinosuke Toda) за теорему Тода, которая показала связь между классами сложности PP и PH
1999 Питер Шор (Peter Shor) за алгоритм Шора для факторизации чисел за полиномиальное количество времени на квантовом компьютере
2000 Мойше Варди, Пьер Вольпер (Moshe Y. Vardi, Pierre Wolper) за исследование проверки моделей с помощью конечных автоматов
2001 Санджив Арора, Уриель Фейге, Шафи Гольдвассер, Карстен Лунд, Ласло Ловас, Раджив Мотвани, Шмуель Сафра, Мадху Судан и Марио Шегеди (Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, Mario Szegedy) за теорему PCP и её приложение
2002 Джеро Сенизергуес (Géraud Sénizergues) за доказательство разрешимости эквивалентности детерминированных автоматов с магазинной памятью
2003 Йоав Фрейнд и Роберт Шапире (Yoav Freund, Robert Schapire) за алгоритм AdaBoost
2004 Морис Херлихи, Майк Сакс, Нир Шавит и Фотиос Захароглу (Maurice Herlihy, Mike Saks, Nir Shavit, Fotios Zaharoglou) за приложение топологии в теории распределённых вычислений
2005 Нога Алон, Йосси Матиас, Марио Шегеди (Noga Alon, Yossi Matias, Mario Szegedy) за основополагающие исследования в области потоковых алгоритмов
2006 Маниндра Агравал, Нирадж Кайал, Нитин Саксена (Manindra Agrawal, Neeraj Kayal, Nitin Saxena) за тест простоты — тест Агравала-Каяла-Саксены
2007 Александр Разборов,[2] Стивен Рудик (Alexander Razborov, Steven Rudich) за «естественные доказательства»[3]
2008 Шангуа Тенг, Дэниел Спилмэн, Стивен Рудик (Shanghua Teng, Daniel Spielman, Steven Rudich) за «сглаженный анализ» алгоритмов

Премия имени Грейс Мюррей Хоппер1971 Дональд Кнут
1972 Paul H. Dirksen, Paul H. Cress
1973 Lawrence M. Breed, Richard H. Lathwell, Roger Moore
1974 George N. Baird
1975 Allen L. Scherr
1976 Edward H. Shortliffe
1977 не присуждалась
1978 Raymond Kurzweil
1979 Stephen Wozniak
1980 Robert M. Metcalfe
1981 Daniel S. Bricklin
1982 Brian K. Reid
1983 не присуждалась
1984 Daniel Henry Holmes Ingalls, Jr.
1985 Cordell Green
1986 William N. Joy
1987 Джон Остераут
1988 Guy L. Steele
1989 W. Daniel Hillis
1990 Ричард Столлман [1]
1991 Feng-hsiung Hsu
1992 не присуждалась
1993 Бьярне Строуструп
1994 не присуждалась
1995 не присуждалась
1996 Shafrira Goldwasser
1997 не присуждалась
1998 не присуждалась
1999 Wen-mei Hwu
2000 Lydia Kavraki
2001 George Necula
2002 Ramakrishnan Srikant
2003 Stephen W. Keckler
2004 Jennifer Rexford [2]
2005 Omer Reingold [3]
2006 Daniel Klein
2007 Vern Paxson

Премия Лёбнера1991 Джозеф Вайнтрауб PC Therapist
1992 Джозеф Вайнтрауб PC Therapist
1993 Джозеф Вайнтрауб PC Therapist
1994 Thomas Whalen TIPS
1995 Джозеф Вайнтрауб PC Therapist
1996 Jason Hutchens HeX
1997 David Levy Converse
1998 Robby Garner Albert One
1999 Robby Garner Albert One
2000 Ричард Воллес A.L.I.C.E.
2001 Ричард Воллес A.L.I.C.E.
2002 Kevin Copple Ella
2003 Juergen Pirner Jabberwock
2004 Ричард Воллес A.L.I.C.E.
2005 Ролло Карпентер George
2006 Ролло Карпентер Joan
2007 Robert Medeksza Ultra Hal
2008 Fred Roberts Elbot

Премия Тьюринга1966 Алан Дж. Перлис За его влияние в области обобщенных техник программирования и построения компиляторов
1967 Морис Винсент Уилкс Профессор Уилкс более всего известен как проектировщик EDSAC, первого компьютера, допускающего внутреннее хранение программ. Построенный в 1949, EDSAC использовал память на линиях задержки. Он также известен, в соавторстве с Виллером и Гиллом как автор книги «Preparation of Programs for Electronic Digital Computers», 1951 года, в которой вводится важнейшее понятие библиотеки
1968 Ричард Хэмминг За работы в области численных методов, систем автоматического кодирования, кодов определения и корректировки ошибок
1969 Марвин Минский За пионерские работы по проблеме искусственного интеллекта
1970 Джеймс Харди Уилкинсон За его исследования в области численного анализа, способствовавшие использованию высокоскоростных цифровых компьютеров, приобретшие особое значение в свете его работ по вычислениям в линейной алгебре и «обратному» анализу ошибок
1971 Джон Мак-Карти Лекция доктора Мак-Карти «Современное состояние исследований по искусственному интеллекту» освещает состояние дел в области, которая обязана многими существенными успехами его работам
1972 Эдсгер Дейкстра Эдсгеру Дейкстре принадлежит значительный вклад в конце 1950-х годов в разработку языка АЛГОЛ, язык программирования высокого уровня, ставший воплощением ясности и математической строгости. Он один из ярчайших представителей науки и искусства языков программирования во всей их общности, а также человек во многом способствовавший пониманию их структуры, представления и реализации. Его публикации в течение пятнадцати лет охватывают широкий спектр тем от теоретических статей по теории графов до базовых руководств, описаний и философских размышлений в области языков программирования
1973 Чарльз Бахман За его выдающийся вклад в технологии баз данных
1974 Дональд Кнут За его огромный вклад в анализ алгоритмов, разработку языков программирования, и в особенности за создание широко известной серии книг под общим названием «Искусство программирования»
1975 Аллен Ньюэлл и Герберт Саймон Их общие усилия в течение двадцати лет, вначале совместно с Дж. К. Шоу, в составе корпорации RAND, впоследствии вместе с профессорско-преподавательским составом и студенческими группами университета Carnegie Mellon, ознаменовались фундаментальным вкладом в искусственный интеллект, психологию механизмов человеческого восприятия и обработку списков
1976 Майкл Рабин и Дана Скотт За их общую статью под названием «Конечные автоматы и проблема разрешимости для них», в которой была предложена идея недетерминированного автомата, концепции, доказавшей впоследствии свою исключительную ценность. Их, ставшая классической, статья послужила источником вдохновения для многих последующих работ в этой области
1977 Джон Бэкус За его глубокий, продолжительный и оказавший большое влияние вклад в проектирование практических высокоуровневых программных систем, в частности за его работу над языком FORTRAN, и его оригинальную публикацию по формализации спецификаций языков программирования
1978 Роберт Флойд За его несомненное влияние на методологию создания эффективного и надёжного программного обеспечения и за его помощь в становлении таких областей компьютерных наук как теория парсинга, семантика языков программирования, автоматическая верификация программ, автоматический синтез программ, и анализ алгоритмов
1979 Айверсон, Кеннет За его пионерскую работу в области языков программирования и математической записи, имеющую результатом то, что сейчас известно среди специалистов как APL, за его вклад в реализацию интерактивных систем, использование APL в образовательных целях, а также в теорию и практику языков программирования
1980 Ч. Энтони Р. Хоар За его фундаментальный вклад в определение и разработку языков программирования
1981 Эдгар Кодд За его фундаментальный и продолжительный вклад в теорию и практику систем управления базами данных, в особенности реляционного типа
1982 Стивен Артур Кук За существенный прогресс, достигнутый им в понимании сложности вычислений. Его работа положила основу теории NP-полноты. Исследнование свойств и границ этого класса стало одним из важнейших направлений теории вычислительных систем за последние десять лет
1983 Кен Томпсон и Денис М. Ритчи За разработку общей теории операционных систем и в частности за создание Unix
1984 Никлаус Вирт За разработку серии инновационных компьютерных языков, ЭЙЛЕР, ALGOL-W, МОДУЛА и ПАСКАЛЬ
1985 Ричард М. Карп За его продолжительный вклад в теорию алгоритмов, в том числе за разработку эффективных алгоритмов для потоков на сетях и других комбинаторных оптимизационных задач, сопоставление вычислений полиномиальной сложности с интуитивным понятием эффективности, и, самое главное, за вклад в теорию NP-полноты
1986 Джон Хопкрофт и Роберт Тарьян За фундаментальные достижения в области разработки и анализа алгоритмов и структур данных
1987 Джон Кок За выдающийся вклад в проектирование и теорию компиляторов, архитектуру больших систем и разработку RISC-компьютеров
1988 Айвен Сазерленд За его пионерский и дальновидный вклад в компьютерную графику, начиная от изобретения Sketchpadа, но не заканчивающегося им
1989 Уильям Кэхэн За его фундаментальный вклад в численный анализ. Один из первых экспертов в вычислениях с плавающей запятой. Кэхэн также посвятил себя задаче «сделать мир безопасным для численных расчётов»
1990 Фернандо Х. Корбато За его пионерскую работу по созданию концепции и управлению разработками по созданию общецелевых, крупномасштабных компьютерных систем с разделением времени и ресурсов CTSS и Multics
1991 Робин Милнер За три различных полноценных достижения: 1) LCF прувер, автоматизирующий доказательства в логике вычислимых функций Скотта, по-видимому первый, инструмент автоматизированного конструирования доказательств, построенный на теоретическом фундаменте и при этом полезный на практике; 2) ML, первый язык программирования использующий полиморфный вывод типов вместе с типизированным механизмом обработкой ошибок; 3) CCS, общая теория конкурентных вычислений. Вдобавок, он сформулировал и развил полную абстракцию, теорию о связи между операционной и денотационной семантиками
1992 Батлер В. Лэмпсон За вклад в разработку распределённых, персональных вычислительных сред и технологию их реализации: рабочие станции, сети, операционные системы, программные системы, дисплеи, безопасность и обмен документами
1993 Юрис Хартманис и Ричард Э. Стернс В дань их основополагающим работам, обеспечившим базу теории сложности вычислений.
1994 Эдвард Фейгенбаум и Радж Редди За первопроходческие разработки и создание крупномасштабных систем искусственного интеллекта и демонстрацию практической важности и потенциальной коммерческой выгоды от технологий использующих искусственный интеллект
1995 Мануэль Блюм В дань его работам по основаниям теории сложности вычислений и её применению к криптографии и верификации программ
1996 Амир Пнуели За плодотворную работу по внедрению темпоральной логики в вычислительные науки, и за выдающийся вклад в верификацию программ и систем
1997 Дуглас Энгельбарт За вдохновляющее предвидение будущего развития интерактивных вычислений и изобретение ключевых технологий помогающих это предвидение реализовать
1998 Джим Грей За основополагающие идеи в области баз данных, исследования обработки транзакций и техническое лидерство в реализации систем.
1999 Фредерик Ф. Брукс, Мл. За исторически значимый вклад в компьютерную архитектуру, операционные системы, и проектирование программного обеспечения.
2000 Эндрю Чи-Чи Яо В дань его фундаментальному вкладу в теорию вычислений, включающему, основанную на понятии сложности вычисления, теорию генерации псевдо-случайных чисел, криптографии, и коммуникационной сложности
2001 Уле-Йохан Даль и Кристен Нигаард За идеи, фундаментальные для развития объектно-ориентированного программирования, возникшие в ходе разработки языков программирования Simula I и Simula 67
2002 Рональд Л. Ривест, Шамир, Ади and Леонард М. Адлеман За уникальный вклад по увеличению практической пользы систем шифрования с открытым ключом
2003 Алан Кэй За многочисленные новаторские идеи, которые легли в основу современных объектно-ориентированных языков, руководство командой разработчиков языка Smalltalk и за фундаментальный вклад в развитие области ПК
2004 Винтон Серф и Роберт Кан За пионерскую работу по проблеме межсетевого обмена (англ. internetworking), включая разработку и реализацию основных Интернет-протоколов, TCP/IP и за ведущую роль в области компьютерных сетей
2005 Питер Наур За фундаментальный вклад в проектирование языков программирования и создание языка Алгол 60, а также в проектирование компиляторов, и в искусство и технику компьютерного программирования
2006 Френсис Э. Аллен За новаторский вклад в теорию и практику оптимизации компьютерных программ, послуживший основой для современных оптимизирующих компиляторов и автоматическому распаралелливанию программ
2007 Эдмунд М. Кларк, Аллен Эмерсон и Иосиф Сифакис За их роль в развитии проверки моделей — высоко эффективную технику верификации программ, широко применяемую при разработке как программного так и аппаратного обеспечения[2]
2008 Барбара Лисков За вклад в практические и теоретические основы языков программирования и системного дизайна, в частности в области исследований устойчивости к ошибкам, абстракции данных и распределённых вычислений.

Григо́рий Я́ковлевич Перельма́н — российский математик, автор доказательства гипотезы Пуанкаре - окончил мехмат ЛГУ.
Ю́рий Влади́мирович Матиясе́вич Будучи аспирантом, в 1970 году сделал последний шаг в доказательстве алгоритмической неразрешимости задачи о существовании решений у произвольного диофантового уравнения, известной также как десятая проблема Гильберта, завершив тем самым программу исследований, основную часть которой к тому времени выполнили M. Davis, H. Putnam и J. Robinson.(мехмат ЛГУ)