Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией
 Скачать 2.67 Mb.
|
|
Анализ пузырьковой и шейкерсортировки. Число сравнений в простой сортировке обменами равно C = (n 2 – n)/2, а минимальное, среднее и максимальное числа пересылок (присваиваний элемен% тов) равны Сортировка массивов Сортировка 80 M min = 0, M avg = 3*(n 2 – n)/2, M max = 3*(n 2 – n)/4. Анализ улучшенных вариантов, особенно шейкер%сортировки, довольно сло% жен. Наименьшее число сравнений здесь равно C min = n–1 . Для улучшенной пу% зырьковой сортировки Кнут (см. [2.7] – прим. перев.) нашел, что среднее число проходов пропорционально величине n – k 1 *n 1/2 , а среднее число сравнений – ве% личине (n 2 – n*(k 2 + ln(n)))/2 . Но нужно отметить, что ни одно из упомянутых улучшений не может повлиять на число обменов; уменьшается только число из% быточных проверок. К несчастью, обмен двух элементов – обычно более затрат% ная операция, чем сравнение ключей; поэтому все наши хитроумные улучшения имеют гораздо меньший эффект, чем интуитивно ожидается. Этот анализ показывает, что сортировка обменами и ее небольшие улучшения хуже, чем и сортировка вставками и сортировка выбором; на самом деле пузырь% ковая сортировка вряд ли чем%нибудь интересна, кроме своего запоминающегося названия. Шейкер%сортировка выгодна в тех случаях, когда элементы уже стоят в почти правильном порядке, – но это редко случается на практике. Можно показать, что среднее расстояние, которое должен пройти каждый из n элементов за время сортировки, равно n/3 позиций. Это число указывает, в ка% ком направлении нужно искать более эффективные методы сортировки. В сущно% сти, все простые методы перемещают элемент на одну позицию на каждом эле% ментарном шаге. Поэтому они всегда требуют порядка n 2 таких шагов. Любое серьезное усовершенствование должно иметь целью увеличение расстояния, на которое перемещаются элементы в каждом прыжке. В дальнейшем будут обсуждаться три эффективных метода, по одному на каж% дый из простых методов сортировки: вставками, выбором и обменами. Таблица 2.4. Таблица 2.4. Таблица 2.4. Таблица 2.4. Таблица 2.4. Пример работы шейкер:сортировки L = 2 3 3 4 4 R = 8 8 7 7 4 dir = ↑ ↓ ↑ ↓ ↑ 44 06 06 06 06 55 44 44 12 12 12 55 55 55 55 55 12 12 12 12 12 44 44 44 44 44 18 42 12 42 18 42 94 42 55 42 44 18 94 94 94 94 94 18 18 18 18 18 55 55 06 06 06 06 06 18 67 67 67 67 67 94 94 94 81 2.3. Эффективные методы сортировки 2.3.1. Сортировка вставками с уменьшающимися расстояниями В 1959 г. Шелл [2.9] предложил способ ускорить сортировку простыми вставками. Проиллюстрируем метод Шелла с помощью нашего стандартного примера с восе% мью элементами (см. табл. 2.5). Сначала каждая группа элементов, отстоящих друг от друга на четыре позиции, сортируется отдельно. Этот процесс называется 4%сор% тировкой. В нашем примере с восемью элементами каждая такая группа состоит в точности из двух элементов. После первого прохода снова рассматриваются груп% пы элементов, но уже отстоящих на две позиции, и снова группы сортируются по отдельности. Этот процесс называется 2%сортировкой. Наконец, на третьем проходе все элементы сортируются обычной сортировкой, или 1%сортировкой. Таблица 2.5. Таблица 2.5. Таблица 2.5. Таблица 2.5. Таблица 2.5. Сортировка вставками с уменьшающимися расстояниями 44 55 12 42 94 18 06 67 После 4%сортировки 44 18 06 42 94 55 12 67 После 2%сортировки 06 18 12 42 44 55 94 67 После 1%сортировки 06 12 18 42 44 55 67 94 Встает резонный вопрос: не превысят ли возможную экономию затраты на вы% полнение нескольких проходов, в каждом из которых сортируются все элементы? Однако каждая сортировка одной группы элементов либо имеет дело с относи% тельно небольшим их числом, либо элементы уже частично отсортированы, так что нужно сделать сравнительно немного перестановок. Очевидно, что метод приводит к отсортированному массиву, и нетрудно по% нять, что на каждом шаге нужно выполнить меньше работы благодаря предыду% щим (так как каждая i %сортировка комбинирует две группы, отсортированные предыдущей 2i %сортировкой). Очевидно также, что допустима любая последова% тельность расстояний, лишь бы последнее из них было равно единице, так как в худшем случае вся работа будет выполняться на последнем проходе. Гораздо менее очевидно, что метод работает еще лучше, если уменьшающиеся расстояния выбирать отличными от степеней двойки. Поэтому построим процедуру для произвольной последовательности рассто% яний. Всего будет T расстояний h 0 , h 1 , , h T–1 , удовлетворяющих условиям h T–1 = 1, h i+1 < h i Эффективные методы сортировки Сортировка 82 Алгоритм описан в процедуре ShellSort [2.9] для T = 4 : PROCEDURE ShellSort; (* ADruS2_Sorts *) CONST T = 4; VAR i, j, k, m, s: INTEGER; x: Item; h: ARRAY T OF INTEGER; BEGIN h[0] := 9; h[1] := 5; h[2] := 3; h[3] := 1; FOR m := 0 TO T–1 DO k := h[m]; FOR i := k TO n–1 DO x := a[i]; j := i–k; WHILE (j >= k) & (x < a[j]) DO a[j+k] := a[j]; j := j–k END; IF (j >= k) OR (x >= a[j]) THEN a[j+k] := x ELSE a[j+k] := a[j]; a[j] := x END END END END ShellSort Анализ сортировки Шелла. Анализ этого алгоритма – очень сложная матема% тическая проблема, полностью еще не решенная. В частности, неизвестно, какая последовательность расстояний дает наилучший результат. Но удивительно то, что расстояния не должны быть кратными друг другу. Тогда исчезнет явление, наблюдаемое в приведенном примере, когда каждый проход сортировки объеди% няет две цепочки, до того никак не «общавшиеся». На самом деле желательно, чтобы различные цепочки «общались» как можно чаще, причем выполняется следующая теорема: если последовательность после k %сортировки подвергается i %сортировке, то она остается k %отсортированной. Кнут в [2.7] (см. с. 105–115 пе% ревода) приводит аргументы в пользу того, что неплохим выбором расстояний яв% ляется последовательность (записанная здесь в обратном порядке) 1, 4, 13, 40, 121, ... где h k–1 = 3h k +1 , h T = 1 , и T = k × ⎣ log 3 (n) ⎦ – 1 . Он также рекомендует последова% тельность 1, 3, 7, 15, 31, ... где h k–1 = 2h k +1, h T = 1 , и T = k × ⎣ log 2 (n) ⎦ – 1 . В последнем случае математическое исследование показывает, что при сортировке n элементов алгоритмом Шелла затраты пропорциональны n 1.2 . Хотя это гораздо лучше, чем n 2 , мы не будем уг% лубляться в этот метод, так как есть алгоритмы еще лучше. 83 2.3.2. Турнирная сортировка Простая сортировка выбором основана на повторном выборе наименьшего ключа среди n элементов, затем среди оставшихся n–1 элементов и т. д. Очевидно, для нахождения наименьшего ключа среди n элементов нужно n–1 сравнений, среди n–1 элементов – n–2 сравнений и т. д., а сумма первых n–1 целых равна (n 2 –n)/2 Как же можно улучшить такую сортировку? Только если после каждого просмот% ра сохранять больше информации, чем всего лишь информацию об одном наименьшем элементе. Например, n/2 сравнений позволяют определить меньший ключ в каждой паре элементов, еще n/4 сравнений дадут меньший ключ в каждой паре из уже найденных меньших ключей, и т. д. Имея только n–1 сравнений, мы можем построить дерево выбора, показанное на рис. 2.3, причем в корне будет ис% комый наименьший ключ [2.2]. Рис. 2.3. Повторные выборы среди двух ключей («турнир ключей») Второй шаг состоит в спуске по пути, соответствующему наименьшему ключу, и в его удалении последовательной заменой либо на пустую позицию («дырку») в самом низу, либо на элемент из другой ветки в промежуточных узлах (см. рис. 2.4 и 2.5). Теперь элементом в корне дерева будет второй наименьший ключ, и его можно удалить. После n таких шагов выбора дерево станет пустым (то есть будет заполнено дырками), и процесс сортировки прекращается. Следует заметить, что на каждом из n шагов выбора требуется только log(n) сравнений. Поэтому вся процедура требует лишь порядка n*log(n) элементарных операций в дополнение к тем n шагам, которые нужны для построения дерева. Это очень существенное Рис. 2.4. Выбор наименьшего ключа Эффективные методы сортировки Сортировка 84 улучшение по сравнению с простыми методами, требующими n 2 шагов, и даже по сравнению с сортировкой Шелла, требующей n 1.2 шагов. Естественно, организовать работу такого алгоритма труднее, поэтому сложность отдельных шагов в турнир% ной сортировке выше: чтобы сохранить всю информацию с предыдущих шагов, нужно работать с некоторой древесной структурой. Нашей следующей задачей будет найти способ эффективно организовать всю эту информацию. Прежде всего важно избавиться от необходимости иметь дело с дырками, кото% рые в итоге заполнят все дерево и потребуют много лишних сравнений. Затем нужно найти способ представить дерево из n элементов в n единицах памяти вме% сто 2n – 1 , как это имеет место на приведенных рисунках. Обе цели были достиг% нуты в алгоритме Heapsort, названном так его изобретателем Вильямсом [2.12]; этот алгоритм представляет собой радикальное улучшение по сравнению с более традиционными подходами к турнирной сортировке. Пирамида (heap) определя% ется как последовательность ключей h L , h L+1 , ... , h R (L ≥ 0) , такая, что h i < h 2i+1 и h i < h 2i+2 для i = L ... R/2–1 Если представить двоичное дерево массивом так, как показано на рис. 2.6, то деревья сортировки на рис. 2.7 и 2.8 тоже суть пирамиды, в частности элемент h 0 пирамиды является ее наименьшим элементом: h 0 = min(h 0 , h 1 , ... , h n–1 ) Пусть дана пирамида с элементами h L+1 ... h R с некоторыми L и R , и пусть нужно добавить новый элемент x так, чтобы получилась расширенная пирамида h L ... h R . Например, возьмем начальную пирамиду h 1 ... h 7 , показанную на Рис. 2.5. Заполнение дырок Рис. 2.6. Массив, представленный в виде двоичного дерева 85 рис. 2.7, и расширим пирамиду влево элементом h 0 = 44 . Новая пирамида получа% ется так: сначала x ставится на вершину древесной структуры, а потом просеива% ется вниз, меняясь местами с наименьшим из двух потомков, который соответ% ственно передвигается вверх. В нашем примере значение 44 сначала меняется местами с 06, затем с 12, так что получается дерево на рис. 2.8. Мы сформулиру% ем алгоритм просеивания в терминах пары индексов i, j , соответствующих эле% ментам, которые обмениваются на каждом шаге просеивания. А читателю пред% лагается убедиться в том, что метод действительно сохраняет инварианты, определяющие пирамиду. Элегантный метод построения пирамиды in situ был предложен Флойдом [2.2]. Метод использует процедуру просеивания sift , представленную ниже. Пусть дан массив h 0 ... h n–1 ; ясно, что элементы h m ... h n–1 (с m = n DIV 2 ) уже образуют пирамиду, так как среди них нет таких пар i , j , чтобы j = 2i+1 или j = 2i+2 . Эти элементы образуют нижний ряд соответствующего двоичного дере% ва (см. рис. 2.6), где никакой упорядоченности не требуется. Затем пирамида расширяется влево, причем за один шаг в нее включается один новый элемент, который ставится на свое правильное место просеиванием. Этот процесс пока% зан в табл. 2.6. PROCEDURE sift (L, R: INTEGER); (* *) VAR i, j: INTEGER; x: Item; BEGIN i := L; j := 2*i+1; x := a[i]; IF (j < R) & (a[j+1] < a[j]) THEN j := j+1 END; WHILE (j <= R) & (a[j] < x) DO a[i] := a[j]; i := j; j := 2*j + 1; IF (j < R) & (a[j+1] < a[j]) THEN j := j+1 END END; a[i] := x END sift Рис. 2.7. Пирамида с семью элементами Рис. 2.8. Просеивание ключа 44 сквозь пирамиду Эффективные методы сортировки Сортировка 86 Следовательно, процесс порождения пирамиды из n элементов h 0 ... h n–1 in situ описывается следующим образом: L := n DIV 2; WHILE L > 0 DO DEC(L); sift(L, n–1) END Чтобы добиться не только частичного, но и полного упорядочения элементов, нужно выполнить n просеиваний, и после каждого из них с вершины пирамиды можно снять очередной (наименьший) элемент. Возникает вопрос: где хранить снимаемые с вершины элементы, и можно ли будет выполнить сортировку in situ. Решение существует: на каждом шаге нужно взять последний элемент пирамиды (скажем, x ), записать элемент с вершины пирамиды в позицию, освободившуюся из%под x , а затем поставить x в правильную позицию просеиванием. Необходимые n–1 шагов иллюстрируются табл. 2.7. Этот процесс можно описать с помощью процедуры sift следующим образом: R := n–1; WHILE R > 0 DO x := a[0]; a[0] := a[R]; a[R] := x; DEC(R); sift(1, R) END Таблица 2.6. Таблица 2.6. Таблица 2.6. Таблица 2.6. Таблица 2.6. Построение пирамиды 44 55 12 42 | 94 18 06 67 44 55 12 | 42 94 18 06 67 44 55 | 06 42 94 18 12 67 44 | 42 06 55 94 18 12 67 06 42 12 55 94 18 44 67 Таблица 2.7. Таблица 2.7. Таблица 2.7. Таблица 2.7. Таблица 2.7. Пример работы сортировки HeapSort 06 42 12 55 94 18 44 67 12 42 18 55 94 67 44 | 06 18 42 44 55 94 67 | 12 06 42 55 44 67 94 | 18 12 06 44 55 94 67 | 42 18 12 06 55 67 94 | 44 42 18 12 06 67 94 | 55 44 42 18 12 06 94 | 67 55 44 42 18 12 06 Из примера в табл. 2.7 видно, что на самом деле здесь получается обратный порядок элементов. Но это легко исправить заменой операций сравнения в про% цедуре sift на противоположные. Таким образом получаем следующую процедуру HeapSort . (Заметим, что в логическом смысле процедура sift является внутренней для HeapSort .) 87 PROCEDURE sift (L, R: INTEGER); (* ADruS2_Sorts *) VAR i, j: INTEGER; x: Item; BEGIN i := L; j := 2*i+1; x := a[i]; IF (j < R) & (a[j] < a[j+1]) THEN j := j+1 END; WHILE (j <= R) & (x < a[j]) DO a[i] := a[j]; i := j; j := 2*j+1; IF (j < R) & (a[j] < a[j+1]) THEN j := j+1 END END; a[i] := x END sift; PROCEDURE HeapSort; VAR L, R: INTEGER; x: Item; BEGIN L := n DIV 2; R := n–1; WHILE L > 0 DO DEC(L); sift(L, R) END; WHILE R > 0 DO x := a[0]; a[0] := a[R]; a[R] := x; DEC(R); sift(L, R) END END HeapSort Анализ сортировки Heapsort. На первый взгляд не очевидно, что этот способ сортировки продемонстрирует хорошую эффективность. Ведь большие элементы сначала просеиваются влево, перед тем как попасть наконец в свои позиции в пра% вом конце массива. Этот метод действительно нельзя рекомендовать для сорти% ровки небольшого числа элементов (как в нашем примере). Однако для больших n сортировка Heapsort очень эффективна, и чем больше n , тем лучше она стано% вится даже в сравнении с сортировкой Шелла. В худшем случае фаза создания пирамиды требует n/2 шагов просеивания, причем на каждом шаге элементы просеиваются через log(n/2), log(n/2+1), ... , log(n–1) позиций, где логарифм (по основанию 2) округляется вниз до ближайше% го целого. Затем фаза сортировки требует n–1 просеиваний, с не более чем log(n–1), log(n–2), ..., 1 пересылок. Кроме того, нужно n–1 пересылок для «складирования» элементов с вершины пирамиды в правом конце массива. Эти рассуждения показывают, что Heapsort требует порядка n × log(n) пересылок даже в наихуд% шем случае. Такое отличное поведение в наихудшем случае является одним из важнейших достоинств алгоритма Heapsort. Отнюдь не ясно, в каких случаях следует ожидать наихудшей (или наилуч% шей) производительности. Похоже, что обычно Heapsort «любит» начальные последовательности, в которых элементы более или менее отсортированы в об% ратном порядке, и в этом смысле алгоритм ведет себя неестественно. Фаза созда% ния пирамиды не требует пересылок, если элементы изначально стоят в обратном порядке. Среднее число пересылок примерно равно n/2 × log(n) , а отклонения от этого значения сравнительно малы. Эффективные методы сортировки Сортировка 88 2.3.3. Быстрая сортировка Обсудив два эффективных метода, основанных на принципах вставки и выбора, введем теперь третий, основанный на принципе обмена. Так как пузырьковая сортировка оказалась в среднем наихудшей среди трех простых алгоритмов, здесь можно ожидать сравнительно заметного улучшения. Однако удивительно, что усовершенствование обменной сортировки, которое мы собираемся обсудить, дает лучший из известных методов сортировки массивов. Производительность здесь настолько высока, что автор этого алгоритма Хоор назвал его быстрой сор тировкой (Quicksort) [2.5], [2.6]. Построение быстрой сортировки исходит из того, что для достижения максималь% ной эффективности желательно выполнять обмены между максимально удален% ными позициями. Пусть даны n элементов, расставленных в обратном порядке. Мож% но отсортировать их всего лишь за n/2 обменов, сначала взяв крайние левый и правый элементы и постепенно продвигаясь внутрь массива с обеих сторон. Естественно, та% кая процедура сработает, только если заранее известно, что элементы стоят в обрат% ном порядке. Тем не менее из этого примера можно извлечь урок. Попробуем реализовать такой алгоритм: случайно выберем любой элемент (назовем его x ); будем просматривать массив слева, пока не найдем элемент a i > x , а затем справа, пока не найдем элемент a j < x . Затем выполним обмен двух найден% ных элементов и будем продолжать такой процесс просмотров и обмена, пока оба просмотра не встретятся где%то в середине массива. В результате получим массив, разделенный на левую часть с ключами, меньшими (или равными) x , и правую часть с ключами, большими (или равными) x . Теперь сформулируем этот процесс разделения (partitioning) в виде процедуры. Заметим, что отношения > и < заменены на ≥ и ≤, которые при отрицании в охране цикла WHILE превращаются в < и >. После такой замены x играет роль барьера для обоих просмотров. PROCEDURE partition; (* *) VAR i, j: INTEGER; w, x: Item; BEGIN i := 0; j := n–1; # x; REPEAT WHILE a[i] < x DO i := i+1 END; WHILE x < a[j] DO j := j–1 END; IF i <= j THEN w := a[i]; a[i] := a[j]; a[j] := w; i := i+1; j := j–1 END UNTIL i > j END partition Например, если в качестве x выбран средний ключ 42, то для массива 44 55 12 42 94 06 18 67 потребуются два обмена 18 ↔ 44 и 6 ↔ 55 , и разделенный массив будем иметь вид 18 06 12 42 94 55 44 67 , 89 а последними значениями индексов будут i = 4 и j = 2 . (Далее описывается инва% риант цикла, то есть совокупность условий, выполняющихся в начале и в конце каждого шага цикла – прим. перев.) Ключи a 0 ... a i–1 меньше или равны ключу x = 42 , а ключи a j+1 ... a n–1 больше или равны x . Следовательно, получились три части: A A A A Ak: 1 ≤ k < i : a k ≤ x A A A A Ak: i ≤ k ≤ j : a k ? x A A A A Ak: j < k ≤ n–1 : x ≤ a k Смысл действий здесь в том, чтобы увеличивать i и уменьшать j , пока не исчез% нет средняя часть. Этот алгоритм очень прост и эффективен, так как важные пере% менные i , j и x могут храниться в быстрых регистрах на протяжении просмотра. Однако он может повести себя плохо, например в случае n одинаковых ключей, когда будет сделано n/2 обменов. Такие избыточные обмены легко устранить, из% менив операторы просмотра следующим образом: WHILE a[i] <= x DO i := i+1 END; WHILE x <= a[j] DO j := j–1 END Но тогда выбранное значение x , которое присутствует в массиве как один из элементов, не сможет больше играть роль барьера для двух просмотров. Тогда в случае массива, в котором все ключи равны, просмотры выйдут за границы мас% сива, если не использовать более сложные условия остановки. Но простота усло% вий стоит того, чтобы заплатить за нее избыточными обменами, которые имеют место сравнительно редко в типичной случайной конфигурации. Небольшая эко% номия возможна, если заменить охрану обмена i ≤ j на i < j . Но это изменение не должно затрагивать двух операторов i := i+1; j := j–1 для которых тогда потребовался бы отдельный условный оператор. Чтобы убе% диться в правильности алгоритма разделения, можно проверить, что отношения порядка являются инвариантами оператора REPEAT . Вначале при i = 0 и j = n–1 они удовлетворяются тривиально, а после выхода по условию i > j из них следует ис% комый результат. Теперь вспомним, что наша цель – не просто разделить исходный массив, но еще и отсортировать его. Однако от разделения до сортировки лишь один неболь% шой шаг: после разделения массива нужно применить тот же процесс к обеим по% лучившимся частям, затем к частям тех частей и т. д., пока каждая часть не будет состоять только из одного элемента. Этот рецепт можно описать следующим об% разом (отметим, что в логическом смысле процедура sort является внутренней для QuickSort ): PROCEDURE sort (L, R: INTEGER); (* ADruS2_Sorts *) VAR i, j: INTEGER; w, x: Item; BEGIN i := L; j := R; x := a[(L+R) DIV 2]; Эффективные методы сортировки Сортировка 90 REPEAT WHILE a[i] < x DO i := i+1 END; WHILE x < a[j] DO j := j–1 END; IF i <= j THEN w := a[i]; a[i] := a[j]; a[j] := w; i := i+1; j := j–1 END UNTIL i > j; IF L < j THEN sort(L, j) END; IF i < R THEN sort(i, R) END END sort; PROCEDURE QuickSort; (* *) BEGIN sort(0, n–1) END QuickSort Процедура sort рекурсивно вызывает сама себя. Такое использование рекур% сии в алгоритмах является очень мощным средством и будет подробно обсуж% даться в главе 3. В некоторых старинных языках программирования рекурсия запрещена по техническим причинам. Поэтому покажем, как тот же самый алго% ритм можно выразить в нерекурсивной форме. Очевидно, решение заключается в том, чтобы выразить рекурсию через итерацию, для чего потребуются дополни% тельные организационные усилия. Ключ к итерационному решению – в том, чтобы организовать некий список запросов на разделение частей массива, которые еще только предстоит выпол% нить. После каждого шага возникают две задачи дальнейшего разделения. Только одну из них можно выполнять непосредственно в следующей итерации; другая сохраняется в упомянутом списке. Конечно, важно, чтобы список запросов обрабатывался в определенном порядке, а именно в обратном порядке. Это озна% чает, что первый сохраненный запрос должен быть выполнен последним, и наобо% рот, то есть список обрабатывается по принципу стека. В следующей нерекурсив% ной версии алгоритма быстрой сортировки каждый запрос представлен просто значениями левой и правой границ сегмента, который нужно разделить. Поэтому вводятся два массива low , high , используемые как стеки с индексом s (указатель вершины стека). Выбор размера стека M будет обсуждаться при анализе алгорит% ма быстрой сортировки. PROCEDURE NonRecursiveQuickSort; (* ADruS2_Sorts *) CONST M = 12; VAR i, j, L, R, s: INTEGER; x, w: Item; low, high: ARRAY M OF INTEGER; (* *) BEGIN s := 0; low[0] := 0; high[0] := n–1; REPEAT (* *) L := low[s]; R := high[s]; DEC(s); REPEAT (* # a[L] ... a[R]*) i := L; j := R; x := a[(L+R) DIV 2]; 91 REPEAT WHILE a[i] < x DO i := i+1 END; WHILE x < a[j] DO j := j–1 END; IF i <= j THEN w := a[i]; a[i] := a[j]; a[j] := w; i := i+1; j := j–1 END UNTIL i > j; IF i < R THEN (* *) INC(s); low[s] := i; high[s] := R END; R := j (* L R # *) UNTIL L >= R UNTIL s < 0 END NonRecursiveQuickSort |