Что это за алгоритм? Help! Завтра экзамен.

← →
Maximsms (2006-01-15 19:44) [0]

Препод давал моим коллегам некий алгоритм быстрой сортировки,
помогите распознать!

см тут: http://qdb.ru/unknown_quick_sort.gif

← →
TUser © (2006-01-15 19:48) [1]

Книжка акая-нибудь по алгоритмам рядом валяется? А то, что там на этой мукулатуре написано, можно разобрать только зная алгоритм :))

← →
Maximsms (2006-01-15 19:49) [2]

TUser © (15.01.06 19:48) [1]

в том то и беда. что не нахожу я в книжке такого алгоритма.
классичекий алгоритм быстрой сортировки - другой.

← →
isasa © (2006-01-15 19:51) [3]

Мда, это на заборе нарисовано?
Растет интелект населения.
Из быстрых в голову приходит - пузырьковая.

← →
Desdechado © (2006-01-15 19:55) [4]

пузырек - самый медленный

а вообще алгоритмов сортировки - десятки

← →
Maximsms (2006-01-15 19:59) [5]

isasa © (15.01.06 19:51) [3]

пузырёк тут не в тему.

это какой-то быстрый алгоритм.

← →
Maximsms (2006-01-15 20:00) [6]

это не на заборе нарисовано это я просканировал сделанное задание,
за которое поставлен плюс.

← →
TUser © (2006-01-15 20:01) [7]

сотни

А на бумажке этой они похоже использовали что-то типа

while A[i] < Middle do inc (i);
Swap;
while A[j] > Middle doe dec (j);
Swap;

Видишь там одна из переставляемых цифр - такая же, как в прошлый раз. Конечно, это менее оптимально.

← →
ferr © (2006-01-15 20:01) [8]

> это не на заборе нарисовано это я просканировал
>сделанное задание,
> за которое поставлен плюс.

:-)

← →
TUser © (2006-01-15 20:02) [9]

Есть мнение, что плюс поставили зря.

← →
YurikGL © (2006-01-15 20:07) [10]

Берем перовое число, сравниваем с последним. Если больше, то меняем местами, если меньше то сравниваем с предпоследним...
Если произошла замена, то начинаем заново (вроде)

Это в C++ ещё есть целая функция QuickSort. Сейчас посмотрю - у меня вроде где-то было описание, алгоритм и всё такое...

← →
Maximsms (2006-01-15 20:24) [13]

это не quicksort!!!!!!!
c quicksort я знаком, это нечто другое.

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

Использование “стандартных” алгоритмов сортировки одномерных массивов.
Во всех примерах, относящихся к одномерным массивам, будем использовать следующий тип данных: type list=array[1..N] of <скалярный тип>;
Конкретный тип элемента в большинстве описываемых алгоритмов может быть как любым числовым, так и символьным или даже строковым. Последний тип скалярным не является, но к элементам этого типа применимы все операции сравнения, с помощью которых обычно (но не всегда !!!) и производится сортировка.
Пусть в задаче данные необходимо отсортировать один раз. Тогда выбирать следует тот из известных вам алгоритмов сортировки, на реализацию которого лично у вас уйдет меньше всего времени и отлаживать который тоже не придется. В таком случае ребята обычно реализуют так называемый “пузырьковую” сортировку или сортировку прямым выбором. Конечно, размерность массива при этом должна быть не намного более 1000 элементов, в противном случае время работы программы может оказаться неоправданно большим, так как количество только операций сравнения у обоих упомянутых алгоритмов равно N(N — 1)/2.
Если же размерность массива велика или сортировку требуется проводить на каждом шаге некоторого цикла, то проще всего использовать алгоритм так называемой “быстрой” сортировки [1-4]. Этот алгоритм на практике выполняется за не более Nlog2N операций сравнения и зачастую еще меньшее число операций присваивания, хотя теоретическая оценка для худшего случая является квадратичной по N. В языке программирования C он реализован в виде функции qsort, входящей в библиотеку stdlib. В полной поставке среды программирования Турбо Паскаль данный алгоритм можно найти в файле EXAMPLES\DOS\qsort.pas. Нередко приведенный в указанном файле текст процедуры сортировки не требуется изменять вообще, но иногда незначительные переделки необходимы, поэтому полезно разобраться в особенностях данной реализации алгоритма сортировки. Рассмотрим возможную модификацию этой процедуры, выполненную для задачи Кировской открытой командной олимпиады по программированию 2001 г. “Предусмотрительное жюри”.
{задача}
В командных соревнованиях по программированию временем решения задачи считается время в минутах от начала тура до момента посылки правильного решения этой задачи на проверку. Жюри старается расположить задачи в таком порядке, чтобы для команды, решившей по порядку все задачи общее время решения было максимальным, если ориентировочное время, которое требуется потратить на решение каждой из задач известно. В самом деле, если на тур предлагается две задачи, и на решение первой команда тратит 10 минут, а на решение второй — 20, то время решения будет равно 40 минутам (первую задачу команда сдает на 10-й минуте тура, вторую — на 30-й, 10+30=40). Если же задачи расположить в обратном порядке, то время будет равно 50 (задачи будут сданы на 20-й и 30-й минутах). Помогите членам жюри расположить задачи в желаемом порядке.
{\задача}
Очевидно, что задачи следует предлагать в порядке невозрастания ожидаемых временных затрат на каждую из них. То есть требуется произвести сортировку временных характеристик имеющихся задач и переставить согласно полученному порядку исходные номера задач. Проще всего делать это одновременно, незначительно модифицируя стандартную процедуру (изменения, внесенные в реализацию алгоритма сортировки, выделены жирным шрифтом):
const nn=…{максимальное количество задач}; type rr=record t,k:integer; end; list=array[1..nn] of rr; var time:list; i,n:integer; procedure QuickSort(var a: List; Lo, Hi: Integer); procedure Sort(l, r: Integer); var i, j, x: integer; y: rr; begin i := l; j := r; x := a[(l+r) DIV 2].t; repeat while a[i].t > x do i := i + 1; while x > a[j].t do j := j - 1; if i <= j then begin y := a[i]; a[i] := a[j]; a[j] := y; i := i + 1; j := j - 1 end until i > j; if l < j then Sort(l, j); if i < r then Sort(i, r) end; begin {QuickSort}; Sort(Lo,Hi) end; begin {решение задачи с помощью модифицированной процедуры QuickSort} read(n); for i:=1 to n do begin read(time[i].t); time[i].k:=i end; QuickSort(time,1,n); {сортировали по временам, а печатаем индексы} for i:=1 to n do write(time[i].k:8) end.
В заключение данного раздела приведем таблицу, в которой для известных универсальных алгоритмов сортировки приведены порядки для количества выполняемых тем или иным алгоритмом в худшем случае операций сравнения и присваивания.

Maximsms, не увидел сообщения. Извиняюсь.

Что это за алгоритм? Help! Завтра экзамен. Найти похожие ветки