53474

Оптимизация процедуры Newman_sort, особенности

Доклад

Информатика, кибернетика и программирование

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

Русский

2014-04-01

19.39 KB

1 чел.

Оптимизация процедуры Newman_sort, особенности.

Формирование результирующего упорядоченного массива осуществляется по этапам.На нулевом этапе считаем, чтот исходный массив состоит из кусков , соержащих не менее одного элемента.Сливаясь попарно ,эти куски на первом этапе формируют подмассивы ,как правило,содержание не менее чем два элементе каждый.На втором этапе каждый кусок состоит из нескольких элементов.Таким образом на i-ом этапе каждый кусок содержит не менее 2 (i) элементов.

Основная процедура , реализующая данный вариант слияния называется Newman Sort.При этом для слияния используется вспомогательный массив,равный по длине исходному массиву.В качестве основного и/или вспомогательного подмассивов поочеродно выступают то массив Б, то массив А.

Важную роль в работе процедуры Newman Sort играет и целочисленная переменная k –ый номер очередного элемента в формируемой части вспомогательного массива. После выхода из внутренней процедуры P, если вспомогательный массив упорядочился , то значение k не превосходит n. Вспомогательная логическая переменная z в результате работы процедуры принимает значение true , если в конечном итоге упорядочился массив А и false, если упорядочился массив Б.

Нетрудно также заметить, что основное пространство в процедуре занимает тело процедуры P, в котором операторы от меток К до метки Q осуществляют слияние текущей пары кусков , а последовательность операторов помеченных меткой Q подготавливает слияние следующей пары подмассивов ,если таковая найдется. Слияние во вспомогательный массив завершается, когда номер i-ого элемента из новой части основного массива окажется больше номера j элемента в правой части этого массива.

Сокращение числа вспомогательных ячеек в этой эффективной процедуре можно с помощью ряда интересных подходов для решения дополнительной памяти в процедуре Natural Merge Sort.


 

А также другие работы, которые могут Вас заинтересовать

32620. Розрахунок конструктивної висоти сортувальної гірки на сортувальній станції 571.5 KB
  Профільна висота головної дільниці h1 встановлюється з урахуванням найбільшого використання допустимої швидкості входу Vвх розрахункового бігуна вагою 85 т ωо=05 Н кн. в уповільнювачах 1 ГП при сприятливих умовах скочування: де Vo найбільша швидкість розпуску приймається 25 м с; g′ох розрахунковий параметр для ОХ бігуна м с2; де g прискорення вільного падіння 981 м с2; n кількість осей бігуна ОХ 4; q вага бігуна ОХ 85 т; hωо1 hск1 питома робота сил опору основного і від стрілок та кривих в межах головного дільниці l1...
32621. Докладно описати питання щодо пасажирської технічної станції (ПТС): 1) призначення і класифікація; 2) основні пристрої; 3) основні операції, що виконують на станції; 4) умови застосування; 5) переваги та недоліки окремих ПТС 116.5 KB
  1 ПТС призначаються для переформування ремонту очищення і екіпірування пасажирських составів. Станції бувають крупні 1520 составів за добу і середні 815.20 составів. На технічних парках менше ніж 68 составів.
32622. Аналіз схем двосторонніх станцій с послідовним розташуванням основних парків. Описати системи гіркової автоматики 216.5 KB
  Для комплексної механізації і автоматизації процесу сортування вагонів сортувальні гірки обладнуються локальними системами автоматики ГАЦ ГПЗУ АРС АЗСР ТГЛ пристроями звязку телебачення сигналізації. Під час роботи в маршрутному режимі оператор натисканням кнопки яка відповідає номеру підгіркової колії встановлює маршрут для кожного відчепу перед розпуском його з гірки. Система АСУ РСГ дозволяє регулювати швидкість насуву і розпуску составів швидкість руху відчепів з гірки керувати маршрутами руху відчепів з контролем...
32623. Докладно описати такі питання: визначення спеціальної вантажної станції, спеціалізація спеціальних вантажних станцій,основні операції,які виконують на спеціалізованих вантажних станціях 677.5 KB
  Докладно описати такі питання: визначення спеціальної вантажної станції спеціалізація спеціальних вантажних станційосновні операціїякі виконують на спеціалізованих вантажних станціях. Спеціалізовані вантажні станції це вантажні станції що будуються в пунктах масової переробки однорідних вантажів і забезпечують ритмічність і потоковість обробки масових вантажів і прискорену обробку рухомого складу на станції ефективне використання вантажнорозвантажувальних механізмів і скорочення обсягу роботи сортувальних станцій за рахунок формування...
32624. Дати технічну характеристику колієпроводів 992.5 KB
  Минимальная длина путепроводной развязки в плане определяется в зависимости от радиуса кривой и угла пересечения. Рис 1 К расчету путепроводной развязки в плане. Длина путепроводной развязки в плане должна быть не менее длины развязки в профиле Lnл Lпp Длина путепроводной развязки в профиле зависит от характера подходов. Минимальная длина развязки в профиле: Lпр=lпод0.
32625. Особливості проектування вузлових дільничних станцій (ВДС). Принципи розташування основних пристроїв на дільничних станціях 98 KB
  Докладно описати такі питання: особливості проектування вузлових дільничних станцій ВДС; принципи розташування основних пристроїв на дільничних станціях; розрахунок числа приймальновідправних колій на ВДС При проектировании УУС следует выполнять такие требования: 1 на подходах к станции должны предусматриваться развязки маршрутов в одном или в разных уровнях; 2 расположение главных путей на подходах к станции конструкции горловин должны обеспечивать одновременный прием и отправление поездов со...
32626. Описати принципи і особливості проектування залізничних вузлів великих і столичних міст 559.5 KB
  В генеральной схеме развития узла особенно тщательно должна быть проработана охрана окружающей среды бережного отношения к природным ресурсам минимального использования земель и угодий ценных для других отраслей хозяйства отдыха населения и дальнейшего развития жилищного строительства. При проектировании железнодорожных узлов необходимо руководствоваться следующими принципами: общая эффективность комплексная оптимизация концентрация децентрализация специализация сохранение равновесия и пропорциональности развития отдельных...
32627. Описати принцип роботи системи КГМ-РИЗТ, а також основні системні задачі комплексу, основні достоїнства та недоліки 2.91 MB
  ВАГОННЫЙ ЗАМЕДЛИТЕЛЬ КЛЕЩЕВИДНОНАЖИМНОЙ ПОДЪЕМНЫЙ КНП5 Клещевиднонажимной подъемный двухрельсовый пневматический вагонный замедлитель используется преимущественно на спускной части сортировочных горок при новом строительстве и модернизации. Вагонный замедлитель КНП5 изготавливается пятизвенным шестисекционным. Вагонный замедлитель может имев следующие положения: отторможенное тормозная система занимает нижнее положение. Через вагонный замедлитель может пропускаться ся весь габаритный подвижной состав вагонного и локомотивного...