ITMO University
“Programming Technologies” Department



Главная

Новости
 Новости науки
 Важное
 Почетные доктора
 Инновации
 Культура
 Люди
 Разное
 Скартел-Yota
 Стрим
 Смольный
Учебный процесс
 Образование
 Дипломы
 Курсовые проекты
 Лабораторные работы
 Учебные курсы
 Визуализаторы
 Unimod-проекты
 Семинары
 Стипендии
Наука
 События и факты
 Госконтракты
 Статьи
 Диссертации
 Книги
 Презентации
 Свидетельства
 Сотрудничество
Исследования
 Автоматы
 Верификация
 Геном
 Искусственный интеллект
 Генетические алгоритмы
 Движение
 UniMod
 Роботы и агенты
 Нейронные сети
 ФЦП ИТМО-Аалто
 Разное

О нас
 Премии
 Сертификаты и дипломы
 Соревнования по программированию
 Прорыв
 Автографы
 Рецензии

Беллетристика
 Мотивация
 Мысли
Медиа
 Видео
 Фотографии
 Аудио
 Интервью

English
 Home

 Articles
 Posters
 Automata-Based Programming
 Initiatives
 Projects
 Presentations
 UniMod
 UniMod Projects
 Visualizers


Поиск по сайту

Яndex



    / Visualizers / Development of the order statistic and quantiles search algorithm visualizer based on Vizi technology (версия для печати)


Development of the order statistic and quantiles search algorithm visualizer based on Vizi technology



© 2004 A.A. Vladykin

Saint-Petersburg State University of Information Technologies, Mechanics and Optics

Project documentation (in Russian)
Source code
Visualizer (online)

Annotation

The terms order statistic and quantile are related to the so called selection problem. It can be reduced to the sorting problem and solved for the time of O(nlog2n) at best. However there exists another solution proposed by C. Hoare. It has the average time complexity of O(n), and thus is widely used in practice.

Present work contains the implementation of the last mentioned quick algorithm. On its basis the mechanism of finding k-th quantiles is illustrated. The implementation uses the Vizi technology and represents a Java-applet, which can demonstrate the algorithm step-by-step. This technology uses an automata-based approach to visualizer development.

The documentation includes algorithm details, possible modifications, and source codes of the visualizer.




© 2002—2017 По техническим вопросам сайта: vl.ulyantsev@gmail.com