Естественная сортировка слиянием с минимизацией объема дополнительной памяти

Естественная сортировка слиянием с минимизацией объема дополнительной памяти

Предложен алгоритм, требующий объема дополнительной памяти O (logn), с трудоемкостью в худшем случае O (nlog2 n). Предложены также алгоритмы устойчивой нерекурсивной сортировки слиянием, позволяющие учитывать естественную упорядоченность исходного массива данных длиной n при уменьшении объема дополн...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Электронное моделирование
Datum:2011
1. Verfasser: Винничук, С.Д.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2011
Schlagworte:
Вычислительные процессы и системы
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/61791
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Естественная сортировка слиянием с минимизацией объема дополнительной памяти / С.Д. Винничук // Электронное моделирование. — 2011 — Т. 33, № 6. — С. 33-56. — Бібліогр.: 3 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-61791
record_format dspace
spelling Винничук, С.Д.
2014-05-11T15:06:25Z
2014-05-11T15:06:25Z
2011
Естественная сортировка слиянием с минимизацией объема дополнительной памяти / С.Д. Винничук // Электронное моделирование. — 2011 — Т. 33, № 6. — С. 33-56. — Бібліогр.: 3 назв. — рос.
0204-3572
https://nasplib.isofts.kiev.ua/handle/123456789/61791
004.424.5 : 519.683.6
Предложен алгоритм, требующий объема дополнительной памяти O (logn), с трудоемкостью в худшем случае O (nlog2 n). Предложены также алгоритмы устойчивой нерекурсивной сортировки слиянием, позволяющие учитывать естественную упорядоченность исходного массива данных длиной n при уменьшении объема дополнительной памяти до величин n/2 + O (1), n/4 + O (1), n/8 + O (1) и трудоемкости в случае наихудшего расположения элементов порядка O (nlogn).
Запропоновано алгоритм, що потребує обсягу додаткової пам’яті O (logn), з трудомісткістю для гіршого випадку O (nlog2 n). Запропоновано також стійкі нерекурсивні алгоритми сортування злиттям, які дозволяють враховувати природню впорядкованість початкового масиву даних довжиною n при зменшенні обсягу додаткової пам’яті до величин n/2 + O (1), n/4 + O (1), n/8 + O (1) з трудомісткістю для гіршого випадку O (nlogn).
An algorithm has been proposed, which requires additional memory of the order O (logn) with an estimate of the labour input in the worst case of order O (nlog2n). Variants of resistant nonrecursive merge sorting algorithms have been proposed that take into account the natural ordering of the original data array of length n, with a decrease in the volume of additional memory to the values of n/2 + O (1), n/4 + O (1), n/8 + O (1), and labour input in the worst case of elements location of the order O (nlogn).
ru
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
Электронное моделирование
Вычислительные процессы и системы
Естественная сортировка слиянием с минимизацией объема дополнительной памяти
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Естественная сортировка слиянием с минимизацией объема дополнительной памяти
spellingShingle Естественная сортировка слиянием с минимизацией объема дополнительной памяти
Винничук, С.Д.
Вычислительные процессы и системы
title_short Естественная сортировка слиянием с минимизацией объема дополнительной памяти
title_full Естественная сортировка слиянием с минимизацией объема дополнительной памяти
title_fullStr Естественная сортировка слиянием с минимизацией объема дополнительной памяти
title_full_unstemmed Естественная сортировка слиянием с минимизацией объема дополнительной памяти
title_sort естественная сортировка слиянием с минимизацией объема дополнительной памяти
author Винничук, С.Д.
author_facet Винничук, С.Д.
topic Вычислительные процессы и системы
topic_facet Вычислительные процессы и системы
publishDate 2011
language Russian
container_title Электронное моделирование
publisher Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
format Article
description Предложен алгоритм, требующий объема дополнительной памяти O (logn), с трудоемкостью в худшем случае O (nlog2 n). Предложены также алгоритмы устойчивой нерекурсивной сортировки слиянием, позволяющие учитывать естественную упорядоченность исходного массива данных длиной n при уменьшении объема дополнительной памяти до величин n/2 + O (1), n/4 + O (1), n/8 + O (1) и трудоемкости в случае наихудшего расположения элементов порядка O (nlogn). Запропоновано алгоритм, що потребує обсягу додаткової пам’яті O (logn), з трудомісткістю для гіршого випадку O (nlog2 n). Запропоновано також стійкі нерекурсивні алгоритми сортування злиттям, які дозволяють враховувати природню впорядкованість початкового масиву даних довжиною n при зменшенні обсягу додаткової пам’яті до величин n/2 + O (1), n/4 + O (1), n/8 + O (1) з трудомісткістю для гіршого випадку O (nlogn). An algorithm has been proposed, which requires additional memory of the order O (logn) with an estimate of the labour input in the worst case of order O (nlog2n). Variants of resistant nonrecursive merge sorting algorithms have been proposed that take into account the natural ordering of the original data array of length n, with a decrease in the volume of additional memory to the values of n/2 + O (1), n/4 + O (1), n/8 + O (1), and labour input in the worst case of elements location of the order O (nlogn).
issn 0204-3572
url https://nasplib.isofts.kiev.ua/handle/123456789/61791
citation_txt Естественная сортировка слиянием с минимизацией объема дополнительной памяти / С.Д. Винничук // Электронное моделирование. — 2011 — Т. 33, № 6. — С. 33-56. — Бібліогр.: 3 назв. — рос.
work_keys_str_mv AT vinničuksd estestvennaâsortirovkasliâniemsminimizacieiobʺemadopolnitelʹnoipamâti
first_indexed 2025-12-07T17:46:30Z
last_indexed 2025-12-07T17:46:30Z
_version_ 1850872525956841472

Ähnliche Einträge