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.


 

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

54057. Межпредметная интеграция как средство активизации учебного процесса 135.5 KB
  В специализированных школах с углубленным изучением иностранного языка межпредметная интеграция должна занимать не последнее место. В этой связи совместные уроки математики и английского языка могут быть очень интересными.
54058. АЛГЕБРА ВЫСКАЗЫВАНИЙ. ОСНОВНЫЕ ОПЕРАЦИИ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ 1.77 MB
  Таблица истинности - это таблица, устанавливающая соответствие между всеми возможными наборами логических переменных, входящих в логическую функцию и значениями функции.
54059. Логика 81.18 KB
  Знаешь ли ты этого человека запутанного в плащ Нет. А между прочим это твой отец. Объект логики –это то на что направлен интерес ученого в логике это мышление на человекомышление. Логика это наука не о всем мышлении а о правильном мышлении о правильном рациональном мышлении которое можно выразить в знаково символической форме –словами.
54061. Ліс. Дерева. Кущі. Ягоди. Розвиток зв’язного мовлення 40 KB
  Мета: Збагачувати словник дітей на основі знань, уявлень про довкілля. Учити перераховувати якості, властивості предметів, намагатись давати їм характеристику, формувати вміння найбільш точно застосовувати слова, що підходять до конкретної ситуації або опису.
54062. Пригоди веселих кошенят 44.5 KB
  Під музичний супровід діти разом із логопедом заходять до музичної зали. Логопед: Доброго ранку доброго дня Хай плещуть долоньки Хай тупають ніжки Хай ротик співає Та сяють усмішки. Піпіпі куди це я потрапила Логопед.
54063. Логопсихокорекція у роботі з дітьми з порушеннями мовлення 67.5 KB
  Ігри і вправи на розвиток емоційної сфери Казка-гра : Про рибака та рибку Логопед читає уривок з казки О. Гра із шишками напруження та розслаблення мязів рук. Гра з бджілкою напруження та розслаблення мязів ніг. Ведмедиця кличе золоту бджілку погратися з ведмежатами.
54064. Програма логопедичної роботи з дітьми старшого дошкільного віку із ЗНМ III-го рівня 65.5 KB
  Учити виділяти назви предметів дій ознак розуміти узагальнювальне значення слів. Учити дітей перетворювати дієслова наказового способу 2ї особи однини в дієслова дійсного способу 3ї особи однини і множинного числа теперішнього часу спи спить сплять спали спала. Учити дітей використовувати в самостійній мові присвійні займенники мій моя моє у поєднанні з іменниками чоловічого і жіночого роду деяких форм словозміни шляхом практичного оволодіння іменниками єдиного і множинного числа дієсловами єдиного і множинного числа...
54065. Конспект логопедичного заняття: «Хто де живе?» 45.5 KB
  Виховання доброзичливості бажання бути справедливим; Корекційно навчальна: Формувати у дітей навички зв’язного мовлення: учити складати розповідь за малюнком за запитанням оцінювати розповіді товаришів; управляти в уживанні іменників – назв приміщень певного призначення складати речення з прийменниками в по у біля поруч; учити давати відповідь на запитання використовуючи прислівники; Хід заняття 1 Організаційний момент Створення емоційного позитивного настрою на занятті Хто де живе Логопед кидає дітям м’яч і починає...